17 - Symmetric graphs

Summary

The condition of vertex-transitivity is not a very powerful one, as is demonstrated by the fact that we can construct at least one vertex-transitive graph from each finite group, by means of the Cayley graph construction. A vertex-transitive graph is symmetric if and only if each vertex-stabilizer G_v acts transitively on the set of vertices adjacent to v. For example, there are just two distinct 3-regular graphs with 6 vertices; one is K_3,3 and the other is the ladder L₃. Both these graphs are vertex-transitive, and K_3,3 is symmetric, but L₃ is not because there are two ‘kinds’ of edges at each vertex.

Although the property of being symmetric is apparently only slightly stronger than vertex-transitivity, symmetric graphs do have distinctive properties which are not shared by all vertex-transitive graphs. This was first demonstrated by Tutte (1947a) in the case of 3-regular graphs. More recently his results have been extended to graphs of higher degree, and it has become apparent that the results are closely related to fundamental classification theorems in group theory. (See 17a, 17f, 17g.)

We begin by defining a t-arc [α] in a graph Г to be a sequence (α₀, α₁,…, α_t) of t + 1 vertices of Г, with the properties that {α_i−1, α_i} is in EГ for 1 ≤ i ≤ t, and α_i−1 ≠ α_i+1 for 1 ≤ i ≤ t − 1. A t-arc is not quite the same thing as the sequence of vertices underlying a path of length t, because it is convenient to allow repeated vertices.