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 may be formed by adding edges between opposite pairs of vertices in a hypercube graph of order k − 1. It can, equivalently, be formed from a hypercube graph of order k, which has twice as many vertices, by identifying together every opposite pair of vertices.

Properties

An order-k folded cube graph is k-regular with 2k − 1 vertices and 2k − 2k edges.
The chromatic number of the order-k folded cube graph is two when k is even and four when k is odd. The odd girth of a folded cube of odd order 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 /2, the folded cubes of odd order are examples of generalized odd graphs.
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 distance-transitive 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.

Examples

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 are known for broadcasting information in a folded cube.