Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u₁—v₁ and u₂—v₂ of G, there is an automorphism

${\displaystyle f:V(G)\rightarrow V(G)}$

such that

${\displaystyle f(u_{1})=u_{2}}$ and ${\displaystyle 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₁ and u₂), 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.