In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.
Construction
The folded cube graph of dimension k (containing 2k − 1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of dimension k − 1. (In a hypercube with 2n vertices, a pair of vertices are opposite if the shortest path between them has length n.) It can, equivalently, be formed from a hypercube graph (also) of dimension k, which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices.
Properties
A dimension-k folded cube graph is a k-regular with 2k − 1 vertices and 2k − 2k edges.
The chromatic number of the dimension-k folded cube graph is two when k is even (that is, in this case, the graph is bipartite) and four when k is odd.1 The odd girth of a folded cube of odd dimension is k, so for odd k greater than three the folded cube graphs provide a class of triangle-free graphs with chromatic number four and arbitrarily large odd girth. As a distance-regular graph with odd girth k and diameter (k − 1)/2, the folded cubes of odd dimension are examples of generalized odd graphs.2
When k is odd, the bipartite double cover of the dimension-k folded cube is the dimension-k cube from which it was formed. However, when k is even, the dimension-k cube is a double cover but not the bipartite double cover. In this case, the folded cube is itself already bipartite. Folded cube graphs inherit from their hypercube subgraphs the property of having a Hamiltonian cycle, and from the hypercubes that double cover them the property of being a distance-transitive graph.3
When k is odd, the dimension-k folded cube contains as a subgraph a complete binary tree with 2k − 1 nodes. However, when k is even, this is not possible, because in this case the folded cube is a bipartite graph with equal numbers of vertices on each side of the bipartition, very different from the nearly two-to-one ratio for the bipartition of a complete binary tree.4
Examples
- The folded cube graph of dimension three is a complete graph K4.
- The folded cube graph of dimension four is the complete bipartite graph K4,4.
- The folded cube graph of dimension five is the Clebsch graph.
- The folded cube graph of dimension six is the Kummer graph, i.e. the Levi graph of the Kummer point-plane configuration.
Applications
In parallel computing, folded cube graphs have been studied as a potential network topology, as an alternative to the hypercube. Compared to a hypercube, a folded cube with the same number of nodes has nearly the same vertex degree but only half the diameter. Efficient distributed algorithms (relative to those for a hypercube) are known for broadcasting information in a folded cube.5
See also
Notes
- van Bon, John (2007), "Finite primitive distance-transitive graphs", European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014.
- Choudam, S. A.; Nandini, R. Usha (2004), "Complete binary trees in folded and enhanced cubes", Networks, 43 (4): 266–272, doi:10.1002/net.20002, S2CID 6448906.
- Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs, CentER Discussion Paper Series No. 2010-47, vol. 2010–47, doi:10.2139/ssrn.1596575, SSRN 1596575.
- El-Amawy, A.; Latifi, S. (1991), "Properties and performance of folded hypercubes", IEEE Trans. Parallel Distrib. Syst., 2 (1): 31–42, doi:10.1109/71.80187.
- Godsil, Chris (2004), Interesting graphs and their colourings, CiteSeerX 10.1.1.91.6390.
- Varvarigos, E. (1995), "Efficient routing algorithms for folded-cube networks", Proc. 14th Int. Phoenix Conf. on Computers and Communications, IEEE, pp. 143–151, doi:10.1109/PCCC.1995.472498, ISBN 0-7803-2492-7, S2CID 62407778.
External links
References
Godsil (2004) provides a proof, and credits the result to Naserasr and Tardif. - Godsil, Chris (2004), Interesting graphs and their colourings, CiteSeerX 10.1.1.91.6390 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.6390 ↩
Van Dam & Haemers (2010). - Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs, CentER Discussion Paper Series No. 2010-47, vol. 2010–47, doi:10.2139/ssrn.1596575, SSRN 1596575 https://research.tilburguniversity.edu/en/publications/2478f418-ae83-4ac3-8742-227315874e96 ↩
van Bon (2007). - van Bon, John (2007), "Finite primitive distance-transitive graphs", European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014 https://doi.org/10.1016%2Fj.ejc.2005.04.014 ↩
Choudam & Nandini (2004). - Choudam, S. A.; Nandini, R. Usha (2004), "Complete binary trees in folded and enhanced cubes", Networks, 43 (4): 266–272, doi:10.1002/net.20002, S2CID 6448906 https://doi.org/10.1002%2Fnet.20002 ↩
El-Amawy & Latifi (1991); Varvarigos (1995). - El-Amawy, A.; Latifi, S. (1991), "Properties and performance of folded hypercubes", IEEE Trans. Parallel Distrib. Syst., 2 (1): 31–42, doi:10.1109/71.80187 https://doi.org/10.1109%2F71.80187 ↩