Misplaced Pages

Folded cube graph

Article snapshot taken from[REDACTED] with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Undirected graph derived from a hypercube graph
Folded cube graph
The dimension-5 folded cube graph (i.e, the Clebsch graph).
Vertices 2 n − 1 {\displaystyle 2^{n-1}}
Edges 2 n − 2 n {\displaystyle 2^{n-2}n}
Diameter ⌊ n 2 ⌋ {\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }
Chromatic number { 2 even  n 4 odd  n {\displaystyle {\begin{cases}2&{\text{even }}n\\4&{\text{odd }}n\end{cases}}}
PropertiesRegular
Hamiltonian
Distance-transitive.
Table of graphs and parameters

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 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 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 vertices and 2k 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 − 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

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.

See also

Notes

  1. Godsil (2004) provides a proof, and credits the result to Naserasr and Tardif.
  2. Van Dam & Haemers (2010).
  3. van Bon (2007).
  4. Choudam & Nandini (2004).
  5. El-Amawy & Latifi (1991); Varvarigos (1995).

References

External links

Categories:
Folded cube graph Add topic