
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 dimension "k" (containing 2"k" − 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 2"n" 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 2"k" − 1 vertices and 2"k" − 2"k" 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. 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 2"k" − 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.
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.