Symmetric graph

Last updated January 31, 2025

In the mathematical field of graph theory, a graph $G$ is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices $(u_{1},v_{1})$ and $(u_{2},v_{2})$ of $G$ , there is an automorphism

By definition (ignoring $u 1$ and $u 2$ ), a symmetric graph without isolated vertices must also be vertex-transitive.^[1] 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$ . Star graphs are a simple example of being edge-transitive without being vertex-transitive or symmetric. As a further example, semi-symmetric graphs 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.^[3] However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.^[4] Such graphs are called half-transitive.^[5] The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices.^[1]^[6] 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.^[1]

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.^[1]

Note that conventionally the term "symmetric graph" is not complementary to the term "asymmetric graph," as the latter refers to a graph that has no nontrivial symmetries at all.

Examples

Two basic families of symmetric graphs for any number of vertices are the cycle graphs (of degree 2) and the complete graphs. Further symmetric graphs are formed by the vertices and edges of the regular and quasiregular polyhedra: the cube, octahedron, icosahedron, dodecahedron, cuboctahedron, and icosidodecahedron. Extension of the cube to n dimensions gives the hypercube graphs (with 2ⁿ vertices and degree n). Similarly extension of the octahedron to n dimensions gives the graphs of the cross-polytopes, this family of graphs (with 2n vertices and degree 2n-2) are sometimes referred to as the cocktail party graphs - they are complete graphs with a set of edges making a perfect matching removed. Additional families of symmetric graphs with an even number of vertices 2n, are the evenly split complete bipartite graphs K_n,n and the crown graphs on 2n vertices. Many other symmetric graphs can be classified as circulant graphs (but not all).

The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.

Cubic symmetric graphs

Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. They all have an even number of vertices. The Foster census and its extensions provide such lists.^[7] The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,^[8] and in 1988 (when Foster was 92^[1]) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.^[9] The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices^[10]^[11] (ten of these are also distance-transitive; the exceptions are as indicated):

Vertices	Diameter	Girth	Graph	Notes
4	1	3	The complete graph K₄	distance-transitive, 2-arc-transitive
6	2	4	The complete bipartite graph K_3,3	distance-transitive, 3-arc-transitive
8	3	4	The vertices and edges of the cube	distance-transitive, 2-arc-transitive
10	2	5	The Petersen graph	distance-transitive, 3-arc-transitive
14	3	6	The Heawood graph	distance-transitive, 4-arc-transitive
16	4	6	The Möbius–Kantor graph	2-arc-transitive
18	4	6	The Pappus graph	distance-transitive, 3-arc-transitive
20	5	5	The vertices and edges of the dodecahedron	distance-transitive, 2-arc-transitive
20	5	6	The Desargues graph	distance-transitive, 3-arc-transitive
24	4	6	The Nauru graph (the generalized Petersen graph G(12,5))	2-arc-transitive
26	5	6	The F26A graph ^[11]	1-arc-transitive
28	4	7	The Coxeter graph	distance-transitive, 3-arc-transitive
30	4	8	The Tutte–Coxeter graph	distance-transitive, 5-arc-transitive

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.

Properties

The vertex-connectivity of a symmetric graph is always equal to the degree d.^[3] In contrast, for vertex-transitive graphs in general, the vertex-connectivity is bounded below by 2(d + 1)/3.^[2]

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.

Related Research Articles

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 after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, an automorphism is a permutation of the vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-transitive graph if, given any two vertices $v 1$ and $v 2$ of $G$ , there is an automorphism $f$ such that

In the mathematical field of graph theory, an edge-transitive graph is a graph $G$ such that, given any two edges $e 1$ and $e 2$ of $G$ , there is an automorphism of $G$ that maps $e 1$ to $e 2$ .

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.

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.

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.

In the mathematical field of graph theory, the Pappus graph is a bipartite, 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 theorem" describing the Pappus configuration. All the cubic, distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

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. It can be defined as the generalized Petersen graph G(8,3): that is, it is formed by the vertices of an octagon, connected to the vertices of an eight-point star in which each point of the star is connected to the points three steps away from it.

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.

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.

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.

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.

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges, rediscovered in 2002 and named after Ljubljana.

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. In other words, a graph is half-transitive if its automorphism group acts transitively upon both its vertices and its edges, but not on ordered pairs of linked vertices.

In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges. It is named after W. T. Tutte.

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.

References

1 2 3 4 5 6 Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.
1 2 3 Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory . New York: Springer. p. 59. ISBN 0-387-95220-9.
1 2 3 Babai, L (1996). "Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, R; Grötschel, M; Lovász, L (eds.). Handbook of Combinatorics. Elsevier.
↑ Bouwer, Z. (1970). "Vertex and Edge Transitive, But Not 1-Transitive Graphs". Canad. Math. Bull. 13: 231–237. doi: 10.4153/CMB-1970-047-8 .
↑ Gross, J.L. & Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2.
↑ Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive". Journal of Graph Theory . 5 (2): 201–204. doi:10.1002/jgt.3190050210..
↑ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
↑ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
↑ "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2
↑ Biggs, p. 148
1 2 Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

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 10000 vertices. Marston Conder, 2011.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[biggs-1] 1 2 3 4 5 6 Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.

[godsil-2] 1 2 3 Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory . New York: Springer. p. 59. ISBN 0-387-95220-9.

[babai-3] 1 2 3 Babai, L (1996). "Automorphism groups, isomorphism, reconstruction" (PDF). In Graham, R; Grötschel, M; Lovász, L (eds.). Handbook of Combinatorics. Elsevier.

[4] Bouwer, Z. (1970). "Vertex and Edge Transitive, But Not 1-Transitive Graphs". Canad. Math. Bull. 13: 231–237. doi: 10.4153/CMB-1970-047-8 .

[handbook-5] Gross, J.L. & Yellen, J. (2004). Handbook of Graph Theory. CRC Press. p. 491. ISBN 1-58488-090-2.

[6] Holt, Derek F. (1981). "A graph which is edge transitive but not arc transitive". Journal of Graph Theory . 5 (2): 201–204. doi:10.1002/jgt.3190050210..

[7] Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63

[8] Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.

[9] "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0-919611-19-2

[10] Biggs, p. 148

[F26A-11] 1 2 Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, $t \geq 2$		skew-symmetric
↓
_{(if connected)} vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	_{(if bipartite)} biregular
↑
Cayley graph	←	zero-symmetric		asymmetric