Halved Folded Cube Graph

The halved folded -cube graph, for even , is obtained by identifying complementary vertices in a halved cube graph. Equivalently, it is either halved graph of the folded cube graph (Chan 2020, p. 772).

Its vertices are pairs of complementary even-weight vectors in . Two distinct pairs are adjacent iff representatives have Hamming distance 2 or . The number of vertices is . For the result is the tetrahedral graph . For even the vertex degree is .

For even , the halved folded -cube graph has distinct adjacency eigenvalues

(1)

where ranges from 0 through and is the floor function (Chan 2020, p. 772). Its least graph eigenvalue is therefore

(2)

and the Hoffman ratio bound gives the chromatic number bounds

(3)

where is the ceiling function. For , 8, and 10, these lower bounds are 16, 8, and 16, respectively. The 6-cube case is the complete graph . The 8-cube and 10-cube cases are strongly regular graphs with parameters and , respectively. In particular, the 10-cube case has graph spectrum (DistanceRegular.org).

Halved folded cube graphs are distance-regular (Chan 2020, p. 772). Translations by even-weight vectors and permutations of coordinates act transitively on ordered vertex pairs at each graph distance, so the graphs are also distance-transitive. They are Cayley graphs on the group of even-weight vectors modulo complementation. The two-coordinate changes generate this group, so the graphs are connected. Their integer graph eigenvalues make them integral graphs. The graphs are implemented in the Wolfram Language as GraphData["HalvedFoldedCube", n] for small even .