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 a k-regular graph 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 a 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 their hypercubes' double covers the property of being a symmetric graph.
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.