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. provides a proof, and credits the result to Naserasr and Tardif. 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..
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..
When k is odd, the dimension-k folded cube contains as a subgraph a complete binary tree with 2k-1 − 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..
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.; .
See also Halved cube graph
Notes
References . . . . . .
External links