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 adjacent iff the symbols differ in exactly
one coordinate.
The graph of the
-hypercube is given by the graph
Cartesian product of path graphs
.
The
-hypercube graph is also isomorphic to
the Hasse diagram for the Boolean
algebra on
elements.
The above figures show orthographic projections of some small
-hypercube graphs
using the first two of each vertex's set of
coordinates. Note
that
above is 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 the Wolfram Language using the command HypercubeGraph[n],
and precomputed properties of hypercube graphs are implemented in the Wolfram
Language 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). Hypercube graphs are also graceful (Maheo 1980, Kotzig 1981, Gallian 2018).
The numbers of (directed) Hamiltonian paths on an
-hypercube graph
for
, 2, ... are 0, 0, 48, 48384, 129480729600,
... (OEIS 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; OEIS A091299).
Closed formulas for the numbers
of
-graph
cycles of
are given by
for
odd and
|
(1)
| |||
|
(2)
| |||
|
(3)
|
(E. Weisstein, Nov. 16, 2014).
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
, the hypercube graphs 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.
Determining the domination number
is intrinsically
difficult (Azarija et al. 2017) and as of April 2018, values are known only
up to
(Östergård and Blass 2001,
Bertolo et al. 2004). Azarija et al. (2017) showed that domination
and total domination numbers of the hypercube
graph are related by
.
is planar for
, so has
graph crossing number
for
. Eggleton and Guy (1970) claimed to have
discovered an upper bound for the graph crossing
number of
for
, where
|
(4)
| |||
|
(5)
|
The first few values for
, 4, ... are
0, 8, 56, 352, 1760, 8192, 35712, ... (OEIS A307813).
An an error was subsequently found, but Erdős and Guy (1973) then conjectured that not only was the original bound correct (though not yet proved), but that
(Clancy et al. 2019). While it
is known that
, exact values for larger
are not known (Clancy et al. 2019). However,
upper bounds are directly computable using QuickCross (Haythorpe) which correspond
to the Eggleton and Guy values for
(E. Weisstein,
Apr. 30, 2019). In addition, the Erdős and Guy (1973) conjecture has now
been refuted since it is known that
(Clancy et al. 2019).
hypercube graph