Symmetric graph
Encyclopedia
In the mathematical
field of graph theory
, a graph
G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism
such that
In other words, a graph is symmetric if its automorphism group
acts transitively
upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive.
By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex transitive
. Since the definition above maps one edge to another, a symmetric graph must also be edge transitive
. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Semi-symmetric graph
s, for example, are edge-transitive and regular
, but not vertex-transitive.
Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree. However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called half-transitive
. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.
A distance-transitive graph
is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.
A t-arc is defined to be a sequence of t+1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A t-transitive graph is a graph such that the automorphism group acts transitively on t-arcs, but not on (t+1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example.
(i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists. The Foster census was begun in the 1930s by Ronald M. Foster
while he was employed by Bell Labs
, and in 1988 (when Foster was 92) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form. The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices (ten of these are also distance-transitive
; the exceptions are as indicated):
Other well known cubic symmetric graphs are the Dyck graph
, the Foster graph
and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph
and the Biggs–Smith graph, are the only cubic distance-transitive graphs.
Non-cubic symmetric graphs include cycle graph
s (of degree 2), complete graph
s (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron
, icosahedron
, cuboctahedron
, and icosidodecahedron
. The Rado graph
forms an example of a symmetric graph with infinitely many vertices and infinite degree.
of a symmetric graph is always equal to the degree
d. In contrast, for vertex-transitive graph
s in general, the vertex-connectivity is bounded below by 2(d+1)/3.
A t-transitive graph of degree 3 or more has girth at least 2(t–1). However, there are no finite t-transitive graphs of degree 3 or more for t ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for t ≥ 6.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism
Graph automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....
- f : V(G) → V(G)
such that
- f(u1) = u2 and f(v1) = v2.
In other words, a graph is symmetric if its automorphism group
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
acts transitively
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
upon ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive.
By definition (ignoring u1 and u2), a symmetric graph without isolated vertices must also be vertex transitive
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
. Since the definition above maps one edge to another, a symmetric graph must also be edge transitive
Edge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
. However, an edge-transitive graph need not be symmetric, since a—b might map to c—d, but not to d—c. Semi-symmetric graph
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....
s, for example, are edge-transitive and regular
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
, but not vertex-transitive.
Every connected symmetric graph must thus be both vertex-transitive and edge-transitive, and the converse is true for graphs of odd degree. However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric. Such graphs are called half-transitive
Half-transitive graph
In the mathematical field of graph theory, a half-transitive graph is a graph that is both vertex-transitive and edge-transitive, but not symmetric...
. The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices. Confusingly, some authors use the term "symmetric graph" to mean a graph which is vertex-transitive and edge-transitive, rather than an arc-transitive graph. Such a definition would include half-transitive graphs, which are excluded under the definition above.
A distance-transitive graph
Distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.A distance transitive...
is one where instead of considering pairs of adjacent vertices (i.e. vertices a distance of 1 apart), the definition covers two pairs of vertices, each the same distance apart. Such graphs are automatically symmetric, by definition.
A t-arc is defined to be a sequence of t+1 vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A t-transitive graph is a graph such that the automorphism group acts transitively on t-arcs, but not on (t+1)-arcs. Since 1-arcs are simply edges, every symmetric graph of degree 3 or more must be t-transitive for some t, and the value of t can be used to further classify symmetric graphs. The cube is 2-transitive, for example.
Examples
Combining the symmetry condition with the restriction that graphs be cubicCubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
(i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists. The Foster census was begun in the 1930s by Ronald M. Foster
R. M. Foster
Ronald Martin Foster , was a Bell Labs mathematician whose work was of significance regarding electronic filters for use on telephone lines...
while he was employed by Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
, and in 1988 (when Foster was 92) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form. The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices (ten of these are also distance-transitive
Distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.A distance transitive...
; the exceptions are as indicated):
| Vertices | Diameter | Girth | Graph | Notes |
|---|---|---|---|---|
| 4 | 1 | 3 | The complete graph Complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:... K4 |
distance-transitive, 2-transitive |
| 6 | 2 | 4 | The complete bipartite graph Complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :... K3,3 |
distance-transitive, 3-transitive |
| 8 | 3 | 4 | The vertices and edges of the cube Cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and... |
distance-transitive, 2-transitive |
| 10 | 2 | 5 | The Petersen graph Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it... |
distance-transitive, 3-transitive |
| 14 | 3 | 6 | The Heawood graph Heawood graph In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:... |
distance-transitive, 4-transitive |
| 16 | 4 | 6 | The Möbius–Kantor graph Möbius–Kantor graph In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor... |
2-transitive |
| 18 | 4 | 6 | The Pappus graph Pappus graph In the mathematical field of graph theory, the Pappus graph is a 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon... |
distance-transitive, 3-transitive |
| 20 | 5 | 5 | The vertices and edges of the dodecahedron | distance-transitive, 2-transitive |
| 20 | 5 | 6 | The Desargues graph Desargues graph In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial... |
distance-transitive, 3-transitive |
| 24 | 4 | 6 | The Nauru graph Nauru graph In the mathematical field of graph theory, the Nauru graph is a symmetric bipartite cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.... (the generalized Petersen graph Generalized Petersen graph In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized... G(12,5)) |
2-transitive |
| 26 | 5 | 6 | The F26A graph F26A graph In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.It has chromatic number 2, chromatic index 3, diameter 5, radius 5 and girth 6... |
1-transitive |
| 28 | 4 | 7 | The Coxeter graph Coxeter graph In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. All the cubic distance-regular graphs are known. The Coxeter graph is one of the 13 such graphs.... |
distance-transitive, 3-transitive |
| 30 | 4 | 8 | The Tutte–Coxeter graph | distance-transitive, 5-transitive |
Other well known cubic symmetric graphs are the Dyck graph
Dyck graph
In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.It is Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index 3, radius 5, diameter 5 and girth 6...
, the Foster graph
Foster graph
In the mathematical field of graph theory, the Foster graph is a 3-regular graph with 90 vertices and 135 edges.The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph.All the cubic...
and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph
Foster graph
In the mathematical field of graph theory, the Foster graph is a 3-regular graph with 90 vertices and 135 edges.The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph.All the cubic...
and the Biggs–Smith graph, are the only cubic distance-transitive graphs.
Non-cubic symmetric graphs include cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
s (of degree 2), complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
s (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron
Octahedron
In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....
, icosahedron
Icosahedron
In geometry, an icosahedron is a regular polyhedron with 20 identical equilateral triangular faces, 30 edges and 12 vertices. It is one of the five Platonic solids....
, cuboctahedron
Cuboctahedron
In geometry, a cuboctahedron is a polyhedron with eight triangular faces and six square faces. A cuboctahedron has 12 identical vertices, with two triangles and two squares meeting at each, and 24 identical edges, each separating a triangle from a square. As such it is a quasiregular polyhedron,...
, and icosidodecahedron
Icosidodecahedron
In geometry, an icosidodecahedron is a polyhedron with twenty triangular faces and twelve pentagonal faces. An icosidodecahedron has 30 identical vertices, with two triangles and two pentagons meeting at each, and 60 identical edges, each separating a triangle from a pentagon...
. The Rado graph
Rado graph
In the mathematical field of graph theory, the Rado graph, also known as the random graph or the Erdős–Renyi graph, is the unique countable graph R such that for any finite graph G and any vertex v of G, any embedding of G − v as an induced subgraph of R can be extended to an...
forms an example of a symmetric graph with infinitely many vertices and infinite degree.
Properties
The vertex-connectivityConnectivity (graph theory)
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements which need to be removed to disconnect the remaining nodes from each other. It is closely related to the theory of network flow problems...
of a symmetric graph is always equal to the degree
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
d. In contrast, for vertex-transitive graph
Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
s in general, the vertex-connectivity is bounded below by 2(d+1)/3.
A t-transitive graph of degree 3 or more has girth at least 2(t–1). However, there are no finite t-transitive graphs of degree 3 or more for t ≥ 8. In the case of the degree being exactly 3 (cubic symmetric graphs), there are none for t ≥ 6.
See also
- Algebraic graph theoryAlgebraic graph theoryAlgebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches...
- Gallery of named graphs
- Regular mapRegular map (graph theory)In mathematics, a regular map is a symmetric tessellation of a closed surface. More precisely, a regular map is a decomposition of a two-dimensional manifold such as a sphere, torus, or Klein bottle into topological disks, such that every flag can be transformed into any other flag by a symmetry...
External links
- Cubic symmetric graphs (The Foster Census). Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
- Trivalent (cubic) symmetric graphs on up to 2048 vertices. Marston Conder, August 2006, retrieved 2009-08-20.