The folded -cube
graph, perhaps better termed "folded hypercube graph," is a graph obtained
by merging vertices of the -hypercube graph that are antipodal, i.e., lie at a distance (the graph diameter of ). Brouwer et al. 1989 (p. 222)
use the notation
for the folded -cube
graph.
For ,
the folded -cube
graph is regular of degree . It has vertices, edges, and diameter . The chromatic number
is 2 for
even and 4 for
odd (Godsil 2004). Godsil observes that the independence
number of the folded -cube graph is given by
a result which follows from Cvetkovic's eigenvalue bound to establish an upper bound and a direct construction of the independent set by looking at vertices at an odd (resp., even) distance from a fixed vertex when n is odd (resp., even) (S. Wagon, pers. comm.).
Brouwer, A. E. "Folded 6-Cube and Graphs with the Same Parameters." http://www.win.tue.nl/~aeb/drg/graphs/Folded-6-cube.html.Brouwer,
A. E.; Cohen, A. M.; and Neumaier, A. "Halved and Folded Cubes."
§9.2D in Distance-Regular
Graphs. New York: Springer-Verlag, pp. 264-265, 1989.Choudam,
S. A. and Nandini, R. U. "Complete Binary Trees in Folded and Enhanced
Cubes." Networks43, 266-272, 2004.DistanceRegular.org.
"Folded Cubes." http://www.distanceregular.org/indexes/foldedcubes.html.El-Amawy,
A. and Latifi, S. "Properties and Performance of Folded Hypercubes." IEEE
Trans. Parallel Distrib. Syst.2, 31-42, 1991.Godsil, C.
"Folded Cubes" and "Eigenvalues and Folded Cubes." §7.6
and 7.7 in Interesting Graphs and Their Colourings. Unpublished manuscript,
pp. 70-73, 2006.Kainen, P. C. "Skewness, Crossing Number
and Euler's Bound for Graphs on Surfaces." 4 Jan 2025. https://arxiv.org/abs/2501.02400.van
Bon, J. "Finite Primitive Distance-Transitive Graphs." Europ. J. Combin.28,
517-532, 2007.van Dam, E. and Haemers, W. H. "An Odd Characterization
of the Generalized Odd Graphs." CentER Discussion Paper Series, No. 2010-47,
SSRN 1596575. 2010.Varvarigos, E. "Efficient Routing Algorithms
for Folded-Cube Networks." Proc. 14th Int. Phoenix Conf. on Computers and
Communications. IEEE, pp. 143-151, 1995.
-cube
graph, perhaps better termed "folded hypercube graph," is a graph obtained
by merging vertices of the 
-hypercube graph 
that are antipodal, i.e., lie at a distance 
(the graph diameter of 
). Brouwer et al. 1989 (p. 222)
use the notation 
for the folded 
-cube
graph.
,
the folded 
-cube
graph is regular of degree 
. It has 
vertices, 
edges, and diameter 
. The chromatic number
is 2 for 
even and 4 for 
odd (Godsil 2004). Godsil observes that the independence
number of the folded 
-cube graph 
is given by
-folded cube graph contains the Möbius
ladder 
as a subgraph for 
and so is not unit-distance.
-cube graph
-cube graph is the hypercube
graph 
.
