Folded Cube Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The folded 👁 n
-cube graph, perhaps better termed "folded hypercube graph," is a graph obtained by merging vertices of the 👁 n
-hypercube graph 👁 Q_n
that are antipodal, i.e., lie at a distance 👁 n
(the graph diameter of 👁 Q_n
). Brouwer et al. 1989 (p. 222) use the notation 👁 square _k
for the folded 👁 k
-cube graph.

For 👁 n>2
, the folded 👁 n
-cube graph is regular of degree 👁 n
. It has 👁 2^(n-1)
vertices, 👁 2^(n-2)n
edges, and diameter 👁 |_n/2_|
. The chromatic number is 2 for 👁 n
even and 4 for 👁 n
odd (Godsil 2004). Godsil observes that the independence number of the folded 👁 n
-cube graph 👁 F_n
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.).

Folded cube graphs are distance-regular and distance-transitive. The 👁 n
-folded cube graph contains the Möbius ladder 👁 M_(n-1)
as a subgraph for 👁 n>=4
and so is not unit-distance.

The following table summarizes special cases.

The bipartite double graph of the folded 👁 n
-cube graph is the hypercube graph 👁 Q_n
.

See also

Clebsch Graph, Halved Cube Graph, Hypercube Graph, Kummer Graph

Explore with Wolfram|Alpha

References

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." Networks 43, 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.

Referenced on Wolfram|Alpha

Folded Cube Graph

Cite this as:

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

Subject classifications