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.The name for this class of graphs was coined by R. M. Foster in a 1966 letter to H. S. M. Coxeter.[1] In the context of group theory, zero-symmetric graphs are also called graphical regular representations of their symmetry groups.[2]
The smallest zero-symmetric graph is a nonplanar graph with 18 vertices.[3] Its LCF notation is [5,−5]9.
Among planar graphs, the truncated cuboctahedral and truncated icosidodecahedral graphs are also zero-symmetric.[4]
These examples are all bipartite graphs. However, there exist larger examples of zero-symmetric graphs that are not bipartite.[5]
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.
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.[6]
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.[7] 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.