Symmetric graph

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

f:V(G)\rightarrow V(G)

such that

f(u_{1})=u_{2}

and

f(v_{1})=v_{2}.

^[1]

In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction).^[2] Such a graph is sometimes also called 1-arc-transitive^[2] or flag-transitive.^[3]

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):

There are only 12 cubic distance-transitive graphs, all given below.

Cubic toroidal graphs are hexagonal regular map of the form {6,3}_b,c, with t=b₂+bc+c₂, having 2t vertices, 3t edges, and t hexagonal cycles.

Generalized Petersen graphs, G{m,n) have 2m vertices, with 7 solutions being symmetric: (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5).

Foster census	Vert.	Edges	Diam	Girth	Aut	{6,3}_b,c	Graph	Notes
F4A	4	6	1	3	24		Complete graph K₄, Möbius ladder M₄ Tetrahedron graph {3,3}, HOG74	distance-transitive, 2-arc-transitive
F6A	6	9	2	4	72	{6,3}_1,1	Utility graph, Complete bipartite graph K_3,3 Möbius ladder M₆, HOG84	distance-transitive, 3-arc-transitive
F8A	8	12	3	4	48	{6,3}_2,0	G(4,1), Cube graph {4,3}, HOG1022	distance-transitive, 2-arc-transitive
F10A	10	15	2	5	120		G(5,2) Petersen graph, HOG462	distance-transitive, 3-arc-transitive
F14A	14	21	3	6	336	{6,3}_2,1	Heawood graph, HOG1154	distance-transitive, 4-arc-transitive
F16A	16	24	4	6	96		G(8,3), Möbius–Kantor graph, HOG1229	2-arc-transitive
F18A	18	27	4	6	216	{6,3}_3,0	Pappus graph, HOG370	distance-transitive, 3-arc-transitive
F20A	20	30	5	5	120		G(10,2), Dodecahedron graph {5,3}, HOG1043	distance-transitive, 2-arc-transitive
F20B	20	30	5	6	240		G(10,3), Desargues graph	distance-transitive, 3-arc-transitive
F24A	24	36	4	6	144	{6,3}_2,2	G(12,5), Nauru graph, HOG1234	2-arc-transitive
F26A	26	39	5	6	78	{6,3}_3,1	F26A graph^[11]	1-arc-transitive
F28A	28	42	4	7	336		Coxeter graph	distance-transitive, 3-arc-transitive
F30A	30	45	4	8	1440		Tutte–Coxeter graph	distance-transitive, 5-arc-transitive
F32A	32	48	5	6	192	{6,3}_4,0	Dyck graph
F38A	38	57			114	{6,3}_3,2
F40A	40	60			480
F42A	42	63			126	{6,3}_4,1
F48A	48	72			288		G(24,5)
F50A	50	75			300	{6,3}_5,0
F54A	54	81			324	{6,3}_3,3
F56A	56	84				{6,3}_4,2
F56B	56	84
F56C	56	84
F60A	60	90
F62A	62	93				{6,3}_5,1
F64A	64	96
F72A	72	108				{6,3}_6,0
F74A	74	111				{6,3}_4,3
F78A	78	117				{6,3}_5,2
F80A	80	120
F84A	84	126
F86A	86	129				{6,3}_6,1
F90A	90	135	8	10	4320		Foster graph	distance-transitive
F96A	96	144				{6,3}_4,4
F96B	96	144
F98A	98	147				{6,3}_5,3
F98B	98	147
F102A	102	153	7	9			Biggs-Smith graph	distance-transitive
F104A	104	156				{6,3}_6,2

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.

References

^ ^a ^b ^c ^d ^e ^f Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.
^ ^a ^b ^c Godsil, Chris; Royle, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. ISBN 0-387-95220-9.
^ ^a ^b ^c 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
^ ^a ^b 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.

[biggs-1] ^ ^a ^b ^c ^d ^e ^f Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge: Cambridge University Press. pp. 118–140. ISBN 0-521-45897-8.

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

[babai-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] 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

Examples

Cubic symmetric graphs

Properties

See also

References

External links