Folded cube graph
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 order k (containing 2k-1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of order 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 order k, which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices.
Properties
An order-k folded cube graph is k-regular with 2k − 1 vertices and 2k − 2k edges.
When k is odd, the bipartite double cover of the order-k folded cube is the order-k cube from which it was formed. However when k is even, the order-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 symmetric graph.
When k is odd, the order-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.[1]
Examples
- The folded cube graph of order three is a complete graph K4.
- The folded cube graph of order four is the complete bipartite graph K4,4.
- The folded cube graph of order five is the Clebsch graph.
- The folded cube graph of order six is the Kummer graph.
Applications
Folded cube graphs have been considered as network topology in parallel computing as an alternative to the hypercube network; compared to a hypercube, a folded cube with the same number of nodes has nearly the same vertex degree but only half the diameter, and efficient distributed algorithms for broadcasting information in a folded cube.[2]
Notes
References
- 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.
- 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.
- 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.