| 词条 | Folded cube graph |
| 释义 |
| name = Folded cube graph | image = | image_caption = The order-5 folded cube graph (i.e, the Clebsch graph). | vertices = 2n−1 | edges = 2n−2n | diameter = floor(n/2) | chromatic_number = 2 (for even n), or 4 (when odd). | properties = Regular graph 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. ConstructionThe 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. PropertiesAn order-k folded cube graph is k-regular with 2k − 1 vertices and 2k − 2k edges. The chromatic number of the order-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.[1] The odd girth of a folded cube of odd order 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 order are examples of generalized odd graphs.[2] 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 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.[3] When k is odd, the order-k folded cube contains as a subgraph a complete binary tree with 2k − 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.[4] Examples
ApplicationsIn 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.[5] See also
Notes1. ^{{harvtxt|Godsil|2004}} provides a proof, and credits the result to Naserasr and Tardif. 2. ^{{harvtxt|Van Dam|Haemers|2010}}. 3. ^{{harvtxt|van Bon|2007}}. 4. ^{{harvtxt|Choudam|Nandini|2004}}. 5. ^{{harvtxt|El-Amawy|Latifi|1991}}; {{harvtxt|Varvarigos|1995}}. References
| 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}}.
| 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}}.
| 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}}.
| 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}}.
| last = Godsil | first = Chris | authorlink = Chris Godsil | title = Interesting graphs and their colourings | citeseerx = 10.1.1.91.6390 | year = 2004}}.
| 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}}. External links
2 : Parametric families of graphs|Regular graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。