Folded cube graph

{{short description|Undirected graph derived from a hypercube graph}}

{{Infobox graph

| name = Folded cube graph

| image = 200px

| image_caption = The dimension-5 folded cube graph (i.e, the Clebsch graph).

| vertices = $2^{n-1}$

| edges = $2^{n-2}n$

| diameter = $\left\lfloor \frac n 2 \right\rfloor$

| chromatic_number = $\begin{cases} 2 & \text{even } n \\ 4 & \text{odd } n \end{cases}$

| properties = Regular
Hamiltonian
Distance-transitive.

}}

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ⁿ 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 − 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.{{harvtxt|Godsil|2004}} provides a proof, and credits the result to Naserasr and Tardif. 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.{{harvtxt|Van Dam|Haemers|2010}}.

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.{{harvtxt|van Bon|2007}}.

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.{{harvtxt|Choudam|Nandini|2004}}.

Examples

The folded cube graph of dimension three is a complete graph K₄.
The folded cube graph of dimension four is the complete bipartite graph K_4,4.
The folded cube graph of dimension five is the Clebsch graph.
The folded cube graph of dimension six is the Kummer graph, i.e. the Levi graph of the Kummer point-plane configuration.

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.{{harvtxt|El-Amawy|Latifi|1991}}; {{harvtxt|Varvarigos|1995}}.

Notes

References

{{citation

| last = van Bon | first = John

| doi = 10.1016/j.ejc.2005.04.014

| issue = 2

| journal = European Journal of Combinatorics

| pages = 517–532

| title = Finite primitive distance-transitive graphs

| volume = 28

| year = 2007| doi-access = free

}}.

{{citation

| last1 = Choudam | first1 = S. A.

| last2 = Nandini | first2 = R. Usha

| doi = 10.1002/net.20002

| issue = 4

| journal = Networks

| pages = 266–272

| title = Complete binary trees in folded and enhanced cubes

| volume = 43

| year = 2004| s2cid = 6448906

}}.

{{citation

| last1 = Van Dam | first1 = Edwin

| last2 = Haemers | first2 = Willem H.

| series = CentER Discussion Paper Series No. 2010-47

| title = An Odd Characterization of the Generalized Odd Graphs

| ssrn = 1596575

| year = 2010| volume = 2010-47

| doi = 10.2139/ssrn.1596575

| url = https://research.tilburguniversity.edu/en/publications/2478f418-ae83-4ac3-8742-227315874e96

}}.

{{citation

| last1 = El-Amawy | first1 = A.

| last2 = Latifi | first2 = S.

| doi = 10.1109/71.80187

| issue = 1

| journal = IEEE Trans. Parallel Distrib. Syst.

| pages = 31–42

| title = Properties and performance of folded hypercubes

| volume = 2

| year = 1991}}.

{{citation

| last = Godsil | first = Chris | authorlink = Chris Godsil

| title = Interesting graphs and their colourings

| citeseerx = 10.1.1.91.6390

| year = 2004}}.

{{citation

| last = Varvarigos | first = E.

| contribution = Efficient routing algorithms for folded-cube networks

| doi = 10.1109/PCCC.1995.472498

| pages = 143–151

| publisher = IEEE

| title = Proc. 14th Int. Phoenix Conf. on Computers and Communications

| year = 1995| isbn = 0-7803-2492-7

| s2cid = 62407778

}}.

External links

{{mathworld|title=Folded Cube Graph|urlname=FoldedCubeGraph|mode=cs2}}

Category:Parametric families of graphs

Category:Regular graphs