zero-symmetric graph
{{multiple image
| 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 each vertex has exactly three incident edges and, for each two vertices, there is a unique symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge.{{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}}
The name for this class of graphs was coined by R. M. Foster in a 1966 letter to H. S. M. Coxeter.{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. ix. In the context of group theory, zero-symmetric graphs are also called graphical regular representations of their symmetry groups.{{citation
| last1 = Lauri | first1 = Josef
| last2 = Scapellato | first2 = Raffaele
| isbn = 9780521529037
| pages = 66
| publisher = Cambridge University Press
| series = London Mathematical Society Student Texts
| title = Topics in Graph Automorphisms and Reconstruction
| url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA66
| year = 2003}}.
Examples
The smallest zero-symmetric graph is a nonplanar graph with 18 vertices.{{harvtxt|Coxeter|Frucht|Powers|1981}}, Figure 1.1, p. 5. Its LCF notation is [5,−5]9.
Among planar graphs, the truncated cuboctahedral and truncated icosidodecahedral graphs are also zero-symmetric.{{harvtxt|Coxeter|Frucht|Powers|1981}}, pp. 75 and 80.
These examples are all bipartite graphs. However, there exist larger examples of zero-symmetric graphs that are not bipartite.{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. 55.
These examples also have three different symmetry classes (orbits) of edges. However, there exist zero-symmetric graphs with only two orbits of edges.
The smallest such graph has 20 vertices, with LCF notation [6,6,-6,-6]5.{{citation|last1=Conder|first1=Marston D. E.|author1-link=Marston Conder|last2=Pisanski|first2=Tomaž|author2-link=Tomaž Pisanski|last3=Žitnik|first3=Arjana|arxiv=1505.02029|doi=10.26493/1855-3974.1146.f96|issue=2|journal=Ars Mathematica Contemporanea|mr=3646702|pages=383–413|title=Vertex-transitive graphs and their arc-types|volume=12|year=2017}}
Properties
Every 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.{{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}}.
{{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.{{harvtxt|Coxeter|Frucht|Powers|1981}}, p. 10. 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
- Semi-symmetric graph, graphs that have symmetries between every two edges but not between every two vertices (reversing the roles of edges and vertices in the definition of zero-symmetric graphs)