{{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 = <math>2^{n-1}</math> | edges = <math>2^{n-2}n</math> | diameter = <math>\left\lfloor \frac n 2 \right\rfloor</math> | chromatic_number = <math>\begin{cases} 2 & \text{even } n \\ 4 & \text{odd } n \end{cases}</math> | properties = Regular<br>Hamiltonian<br>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<sup>''k'' − 1</sup> 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<sup>''n''</sup> 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<sup>''k'' − 1</sup> vertices and 2<sup>''k'' − 2</sup>''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.<ref>{{harvtxt|Godsil|2004}} provides a proof, and credits the result to Naserasr and Tardif.</ref> 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.<ref>{{harvtxt|Van Dam|Haemers|2010}}.</ref>
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.<ref>{{harvtxt|van Bon|2007}}.</ref>
When ''k'' is odd, the dimension-''k'' folded cube contains as a subgraph a complete binary tree with 2<sup>''k-1''</sup> − 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.<ref>{{harvtxt|Choudam|Nandini|2004}}.</ref>
==Examples== *The folded cube graph of dimension three is a complete graph ''K''<sub>4</sub>. *The folded cube graph of dimension four is the complete bipartite graph ''K''<sub>4,4</sub>. *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.<ref>{{harvtxt|El-Amawy|Latifi|1991}}; {{harvtxt|Varvarigos|1995}}.</ref>
==See also== *Halved cube graph
==Notes== {{reflist}}
==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 | doi-access = free }}. *{{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 | bibcode = 1991ITPDS...2...31E }}. *{{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