Halved Cube Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

Let 👁 Y_n
denote the graph with vertex set 👁 V(X_n)
, where 👁 X_n
is the 👁 n
-hypercube and two vertices are adjacent in 👁 Y_n
iff they are at distance 👁 1<=d<=2
in 👁 X_n
. 👁 Y_n
is therefore the graph square of the hypercube graph 👁 Q_(n+1)/2
.

👁 Y_n
is not connected, but it contains two isomorphic components on 👁 2^(n-1)
vertices, each of which is called a halved 👁 n
-cube graph, half cube graph, the halved 👁 n
-cube, or sometimes the 👁 n
-demi-cube graph (Steinerberger 2023). The most common notation is 👁 1/2Q_n
(Godsil 2004), but Steinerberger (2023) uses 👁 Q_((2))^n
.

The halved 👁 n
-cube graph can also be defined as the graph on the binary vectors of length 👁 n
with even weight, where two such vectors are adjacent if and only if their sum has weight two (Godsil 2004), or as the 2nd graph power (i.e., the graph square) of 👁 Q_(n-1)
, where 👁 Q_n
denotes the 👁 n
-hypercube graph.

Embeddings for small-order halved graphs are illustrated above and special cases are summarized in the table below.

The 5-halved cube graph is the graph complement of the Clebsch graph. It has Lovász number 👁 8/3
(Fung 2011, p. 34). Note that Brouwer et al. (1989, pp. 104 and 224) confusingly use the term "Clebsch graph" to refer to the halved 5-cube graph instead of the folded 5-cube graph meant by other authors.

The 6-halved cube graph is a distance-regular graph with intersection array 👁 {15,6,1;1,6,15}
, and therefore also a Taylor graph.

The chromatic numbers of the 👁 n
-halved cube graphs for 👁 n=4
, 5, ... are 4, 8, 8, 8, 8, 13 or 14, [13, 15], 👁 >=15
, 👁 >=15
, ... (Godsil 2004, p. 67; typos corrected). Brouwer agrees that 👁 1/2Q_5
has chromatic number 4 and gives its independence number as 5.

The independence numbers of the 👁 n
-halved cube graphs for 👁 n=1
, 2, ... are 1, 1, 1, 2, 2, 4, 8, 16, 20, 40, 72, 144, ..., where values for 👁 n=9
to 12 are from Godsil (2004, p. 67). This sequence appears identical to the error-correcting coding function 👁 A(n,4)
(OEIS A005864; E. W. Weisstein, Dec. 31, 2015).

The domination numbers of 👁 n
-halved cube graphs for 👁 n=1
, 2, ... are 1, 1, 1, 2, 2, 2, 4, 7, 12, ..., which agrees with OEIS A029866 for known terms (E. Weisstein, Aug. 31, 2016).

See also

16-Cell, Clebsch Graph, Error-Correcting Code, Folded Cube Graph, Halved Graphs, Hypercube Graph

Explore with Wolfram|Alpha

References

Brouwer, A. E. "Clebsch Graph." http://www.win.tue.nl/~aeb/drg/graphs/Clebsch.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, 1989.DistanceRegular.org. "Halved Cubes." http://www.distanceregular.org/indexes/halvedcubes.html.Fung, M. "The Lovász Number of the Keller Graphs." Master thesis. Universiteit Leiden: Mathematisch Instituut, 2011.Godsil, C. "Halved Cubes" and "Chromatic Number of Halved Cubes." §6.3 and 6.4 in Interesting Graphs and Their Colourings. Unpublished manuscript, pp. 66-67, 2004.Sloane, N. J. A. Sequence A005864/M1111 in "The On-Line Encyclopedia of Integer Sequences."Steinerberger, S. "Curvature on Graphs via Equilibrium Measures." J. Graph Th., 1-22, 2023.

Referenced on Wolfram|Alpha

Halved Cube Graph

Cite this as:

Weisstein, Eric W. "Halved Cube Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HalvedCubeGraph.html

Subject classifications