Hypercube Graph


The -hypercube graph, also called the
-cube graph and commonly denoted
or
, is the graph
whose vertices are the
symbols
, ...,
where
or 1
and two vertices are adjacency if the symbols differ in exactly one coordinate.
The graph of the -hypercube is given by the graph
Cartesian product of path graphs
.
The above figures show symmetric projections of the -hypercube graphs
with
to 7. Note that the second figure
shows a projection of the usual cube
looking along a space diagonal so that the top
and bottom vertices coincide, and hence only seven of the cube's eight vertices are
visible. In addition, three of the central edges connect to the upper vertex, while
the other three connect to the lower vertex.
Hypercube graphs may be computed in Mathematica using the command HypercubeGraph[n],
and precomputed properties of hypercube graphs are implemented in Mathematica
as GraphData["Hypercube", n
].
Special cases are summarized in the following table.
![]() | ![]() |
0 | singleton graph ![]() |
1 | path
graph ![]() |
2 | square graph ![]() |
3 | cubical graph |
4 | tesseract graph |
All hypercube graphs are Hamiltonian, and any Hamiltonian cycle of a labeled hypercube graph defines a Gray code (Skiena 1990, p. 149).
The numbers of (directed) Hamiltonian paths on an -hypercube graph
for
, 2, ... are 0, 0, 48, 48384, 129480729600,
... (Sloane's A006070; extending the result
of Gardner 1986, pp. 23-24), while the numbers of (directed) Hamiltonian cycles
are 0, 2, 12, 2688, 1813091520, ... (Harary et al. 1988; Sloane's A091299).
Hypercube graphs are distance-transitive, and therefore also distance-regular.
In 1954, Ringel showed that the hypercube graphs admit Hamilton
decompositions whenever
is a power of 2
(Alspach 2010). Alspach et al. (1990) showed that every
for
admits a
Hamilton decomposition.

For , they are also unit-distance
(Gerbracht 2008), as illustrated above for the first few hypercube graphs. This can
be established by induction for the
-hypercube graph
by starting with the unit-distance embedding of the square
graph, translating the embedding by one unit in a direction not chosen in any
of the steps before (only finitely many unit translation vectors have been used,
so there must be a direction not used before), connecting the vertices in the translate
with the corresponding vertices in the original one, and repeating until the
-hypercube graph has been constructed.
The -hypercube graph is isomorphic to the
Hasse diagram for the Boolean
algebra on
elements.