Symmetric graph

thumb|200px|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 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 , 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>

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). Such a graph is sometimes also called -transitive

By definition (ignoring and ), a symmetric graph without isolated vertices must also be vertex-transitive. 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. 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 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):

{| class="wikitable"

|-

!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