Download Wolfram Notebook

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 (Sokolová 1987, Blokhuis et al. 2007). Godsil (2006) 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.).

Folded cube graphs are distance-regular and distance-transitive. The -folded cube graph contains the Möbius ladder as a subgraph for and so is not unit-distance.

For even , the folded -cube graph is bipartite, and either of its halved graphs is a halved folded cube graph. Equivalently, a halved folded cube graph is obtained by identifying complementary vertices in a halved cube graph of dimension (Chan 2020, p. 772).

The following table summarizes special cases.

For odd , the bipartite double graph of the folded -cube graph is the hypercube graph . For even , it consists of two disjoint copies of the folded -cube graph.

See also

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

Explore with Wolfram|Alpha

References

Blokhuis, A.; Brouwer, A. E.; and Haemers, W. H. "On 3-Chromatic Distance-Regular Graphs." Des. Codes Cryptogr. 44, 293-305, 2007.Brouwer, A. E. "Folded 6-Cube and Graphs with the Same Parameters." https://aeb.win.tue.nl/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.Chan, A. "Complex Hadamard Matrices, Instantaneous Uniform Mixing and Cubes." Algebr. Combin. 3, 757-774, 2020. https://doi.org/10.5802/alco.112.Choudam, S. A. and Nandini, R. U. "Complete Binary Trees in Folded and Enhanced Cubes." Networks 43, 266-272, 2004.DistanceRegular.org. "Folded Cubes." https://www.math.mun.ca/distanceregular/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.House of Graphs. Folded Cube Graphs. K2, Tetrahedron K4, K4,4, Clebsch Graph, Kummer Graph, Folded Hypercube 7, and Folded Hypercube 8.Kainen, P. C. "Skewness, Crossing Number and Euler's Bound for Graphs on Surfaces." 4 Jan 2025. https://arxiv.org/abs/2501.02400.Sokolová, M. "The Chromatic Number of Extended Odd Graphs Is Four." Časopis Pest. Mat. 112, 308-311, 1987.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