| 词条 | Zero-symmetric graph |
| 释义 |
| align = right | direction = horizontal | width = 200 | image1 = 18-vertex zero-symmetric graph.svg | alt1 = 18-vertex zero-symmetric graph | caption1 = The smallest zero-symmetric graph, with 18 vertices and 27 edges | image2 = Great rhombicuboctahedron.png | alt2 = Truncated cuboctahedron | caption2 = The truncated cuboctahedron, a zero-symmetric polyhedron }}{{Graph families defined by their automorphisms}} In the mathematical field of graph theory, a zero-symmetric graph is a connected graph in which all vertices are symmetric to each other, each vertex has exactly three incident edges, and these three edges are not symmetric to each other. More precisely, it is a connected vertex-transitive cubic graph whose edges are partitioned into three different orbits by the automorphism group.[1] In these graphs, for every two vertices u and v, there is exactly one graph automorphism that takes u into v.[2] The name for this class of graphs was coined by R. M. Foster in a 1966 letter to H. S. M. Coxeter.[3] ExamplesThe smallest zero-symmetric graph is a nonplanar graph with 18 vertices.[4] Its LCF notation is [5,−5]9. Among planar graphs, the truncated cuboctahedral and truncated icosidodecahedral graphs are also zero-symmetric.[5] These examples are all bipartite graphs. However, there exist larger examples of zero-symmetric graphs that are not bipartite.[6] PropertiesEvery finite zero-symmetric graph is a Cayley graph, a property that does not always hold for cubic vertex-transitive graphs more generally and that helps in the solution of combinatorial enumeration tasks concerning zero-symmetric graphs. There are 97687 zero-symmetric graphs on up to 1280 vertices. These graphs form 89% of the cubic Cayley graphs and 88% of all connected vertex-transitive cubic graphs on the same number of vertices.[7] {{Unsolved|mathematics|Does every finite zero-symmetric graph contain a Hamiltonian cycle?}}All known finite connected zero-symmetric graphs contain a Hamiltonian cycle, but it is unknown whether every finite connected zero-symmetric graph is necessarily Hamiltonian.[8] This is a special case of the Lovász conjecture that (with five known exceptions, none of which is zero-symmetric) every finite connected vertex-transitive graph and every finite Cayley graph is Hamiltonian. See also
References1. ^{{citation | last1 = Coxeter | first1 = Harold Scott MacDonald | author1-link = Harold Scott MacDonald Coxeter | last2 = Frucht | first2 = Roberto | author2-link = Roberto Frucht | last3 = Powers | first3 = David L. | isbn = 0-12-194580-4 | mr = 658666 | publisher = Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London | title = Zero-symmetric graphs | year = 1981}} 2. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. 4. 3. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. ix. 4. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, Figure 1.1, p. 5. 5. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, pp. 75 and 80. 6. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. 55. 7. ^{{citation | last1 = Potočnik | first1 = Primož | last2 = Spiga | first2 = Pablo | last3 = Verret | first3 = Gabriel | arxiv = 1201.5317 | doi = 10.1016/j.jsc.2012.09.002 | journal = Journal of Symbolic Computation | mr = 2996891 | pages = 465–477 | title = Cubic vertex-transitive graphs on up to 1280 vertices | volume = 50 | year = 2013}}. 8. ^{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. 10. 3 : Algebraic graph theory|Graph families|Regular graphs |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。