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.

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.