Zero-symmetric Graph on:
[Wikipedia]
[Google]
[Amazon]
In the 
The name for this class of graphs was coined by
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, 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 (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definit ...
taking one vertex to the other. Such a graph is a vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism
:f : G \to G\
such that
:f(v_1) = v_2.\
In other words, a graph is vertex-transitive i ...
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.
The name for this class of graphs was coined by R. M. Foster
Ronald Martin Foster (3 October 1896 – 2 February 1998), was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines. He published an important paper, ''A Reactance Theorem'', (see Foster ...
in a 1966 letter to H. S. M. Coxeter
Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century.
Biography
Coxeter was born in Kensington t ...
. 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. ItsLCF notation
In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle ...
is ,−5sup>9.
Among planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s, the truncated cuboctahedral and truncated icosidodecahedral graph
In geometry, a truncated icosidodecahedron, rhombitruncated icosidodecahedron,Wenninger Model Number 16 great rhombicosidodecahedron,Williams (Section 3-9, p. 94)Cromwell (p. 82) omnitruncated dodecahedron or omnitruncated icosahedronNorman Wooda ...
s are also zero-symmetric.
These examples are all bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
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 LCF notation
In the mathematical field of graph theory, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by H. S. M. Coxeter and Robert Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle. The cycle ...
,6,-6,-6sup>5.
Properties
Every finite zero-symmetric graph is aCayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayle ...
, 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 infini ...
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 mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
, 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 opposi ...
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
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edg ...
, 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)
References
{{reflist Algebraic graph theory Graph families Regular graphs