Folded cube graph

Construction of the Clebsch graph by adding a perfect matching to a four-dimensional hypercube.

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. Equivalently, it can be formed from a hypercube graph with twice as many vertices, by identifying together every opposite pair of vertices. The folded cube graph of order k is formed by adding edges to a hypercube graph of order k − 1 or by identifying pairs of vertices in a hypercube graph of order k. It is a k-regular graph with 2^k − 1 vertices and 2^k − 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; when k is even, the order-k cube is a double cover, but not the bipartite double cover, because 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 their hypercube double covers the property of being a symmetric graph.

Examples

• The folded cube graph of order three is a complete graph K₄.
• The folded cube graph of order four is the complete bipartite graph K_4,4.
• The folded cube graph of order five is the Clebsch graph.
• The folded cube graph of order six is the Kummer graph.

References

• Weisstein, Eric W. "Folded Cube Graph". MathWorld.