Symmetric graph

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

and [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 u1 and u2), 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.

Graph families defined by their automorphisms
distance-transitive → distance-regular ← strongly regular
↓
symmetric (arc-transitive) ← t-transitive, t ≥ 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

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.

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