In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a zero-symmetric graph is a

connected graph In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...

in which each vertex has exactly three incident edges and, for each two vertices, there is a unique

symmetry Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is Invariant (mathematics), invariant und ...

taking one vertex to the other. Such a graph is a

vertex-transitive graph In the mathematics, mathematical field of graph theory, an Graph automorphism, automorphism is a permutation of the Vertex (graph theory), vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-tr ...

but cannot be an

edge-transitive graph In the mathematical field of graph theory, an edge-transitive graph is a graph such that, given any two edges and of , there is an automorphism of that maps to . In other words, a graph is edge-transitive if its automorphism group acts t ...

: the number of symmetries equals the number of vertices, too few to take every edge to every other edge. Two-edge-orbit GRR

The name for this class of graphs was coined by

R. M. Foster Ronald Martin Foster (3 October 1896 – 2 February 1998), was an American mathematician at Bell Labs whose work was of significance regarding electronic filters for use on telephone lines. He published an important paper, ''A Reactance Theorem' ...

in a 1966 letter to H. S. M. Coxeter. In the context of

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...

, zero-symmetric graphs are also called graphical regular representations of their symmetry groups..

Examples

The smallest zero-symmetric graph is a nonplanar graph with 18 vertices. Its

LCF notation In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Harold Scott MacDonald Coxeter, H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain ...

is ,−5sup>9. Among

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

s, the truncated cuboctahedral and truncated icosidodecahedral graphs are also zero-symmetric. These examples are all

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

s. However, there exist larger examples of zero-symmetric graphs that are not bipartite. 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

,6,-6,-6sup>5.

Properties

Every finite zero-symmetric graph is a

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

, a property that does not always hold for cubic vertex-transitive graphs more generally and that helps in the solution of

combinatorial enumeration Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an inf ...

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. All known finite connected zero-symmetric graphs contain a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, but it is unknown whether every finite connected zero-symmetric graph is necessarily Hamiltonian., p. 10. This is a special case of the

Lovász conjecture In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says: : Every finite connected vertex-transitive graph contains a Hamiltonian path. Originally László Lovász stated the problem in the opp ...

that (with five known exceptions, none of which is zero-symmetric) every finite connected vertex-transitive graph and every finite Cayley graph is Hamiltonian.

References

{{reflist Algebraic graph theory Graph families Regular graphs

Examples

Properties

See also

References