Symmetric graph

File:Petersen1 tiny.svg

The Petersen graph is a (cubic) symmetric graph. Any pair of adjacent vertices can be mapped to another by an automorphism, since any five-vertex ring can be mapped to any other.

In the mathematical field of graph theory, a graph Template:Mvar is symmetric or arc-transitive if, given any two ordered pairs of adjacent vertices <math>(u_1,v_1)</math> and <math>(u_2,v_2)</math> of Template:Mvar, there is an automorphism

<math>f : V(G) \rightarrow V(G)</math>

such that

<math>f(u_1) = u_2</math> and <math>f(v_1) = v_2.</math><ref name="biggs">Template:Cite book</ref>

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).<ref name="godsil">Template:Cite book</ref> Such a graph is sometimes also called Template:Nowrap-transitive<ref name="godsil"/> or flag-transitive.<ref name="babai">Template:Cite book</ref>

By definition (ignoring Template:Math and Template:Math), a symmetric graph without isolated vertices must also be vertex-transitive.<ref name="biggs" /> 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 Template:Mvar might map to Template:Mvar, but not to Template:Mvar. 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.<ref name="babai" /> However, for even degree, there exist connected graphs which are vertex-transitive and edge-transitive, but not symmetric.<ref>Template:Cite journal</ref> Such graphs are called half-transitive.<ref name="handbook">Template:Cite book</ref> The smallest connected half-transitive graph is Holt's graph, with degree 4 and 27 vertices.<ref name="biggs" /><ref>Template:Cite journal.</ref> 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.<ref name="biggs" />

A Template:Nowrap is defined to be a sequence of Template:Math vertices, such that any two consecutive vertices in the sequence are adjacent, and with any repeated vertices being more than 2 steps apart. A Template:Nowrap graph is a graph such that the automorphism group acts transitively on Template:Nowrap, but not on Template:Nowrap. Since Template:Nowrap are simply edges, every symmetric graph of degree 3 or more must be Template:Nowrap for some Template:Mvar, and the value of Template:Mvar can be used to further classify symmetric graphs. The cube is Template:Nowrap, for example.<ref name="biggs" />

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.<ref>Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63</ref> The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs,<ref>Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.</ref> and in 1988 (when Foster was 92<ref name="biggs"/>) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form.<ref>"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) Template:Isbn</ref> The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices<ref>Biggs, p. 148</ref><ref name="F26A">Weisstein, Eric W., "Cubic Symmetric Graph", from Wolfram MathWorld.</ref> (ten of these are also distance-transitive; the exceptions are as indicated):

Vertices	Diameter	Girth	Graph	Notes
4	1	3	The complete graph K4	distance-transitive, 2-arc-transitive
6	2	4	The complete bipartite graph K3,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<ref name="F26A"/>	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.<ref name="babai" /> In contrast, for vertex-transitive graphs in general, the vertex-connectivity is bounded below by 2(d + 1)/3.<ref name="godsil" />

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 theory
• Gallery of named graphs
• Regular map

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.