In my previous post I discussed various measures of symmetry of the vertex set of a graph. The main terms introduced were vertex-transitive, vertex-primitive, vertex-quasiprimitive, vertex-biprimitive and vertex-biquasiprimitive. It was also seen that the class of vertex-transitive graphs was very large and so we often place further symmetry conditions on our graphs so that we can obtain interesting results. In this post I wish to discuss conditions on the symmetry of the edge set ${E\Gamma}$ and arc set ${A\Gamma}$.

A graph ${\Gamma}$ is called edge-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of edges of ${\Gamma}$ and is called arc-transitive if ${\mathrm{Aut}(\Gamma)}$ acts transitively on the set of arcs. As long as there are no isolated vertices (that is vertices with no neighbours) then an arc-transitive graph will also be vertex-transitive and edge-transitive. Such graphs are often called symmetric.

I will first discuss how to construct all arc-transitive graphs. Let ${G}$ be a transitive permutation group on a set ${\Omega}$. The orbits of ${G}$ on ${\Omega\times\Omega}$ are called orbitals. An orbital ${\mathcal{O}}$ is called self-paired if for all ${(\alpha,\beta)\in \mathcal{O}}$ the element ${(\beta,\alpha)}$ also lies in ${\mathcal{O}}$. This is equivalent to there being an element ${g\in G}$ that interchanges ${\alpha}$ and ${\beta}$. For each self-paired orbital we can construct a graph ${\Gamma}$ with vertex set ${\Omega}$ and edges ${\{\alpha,\beta\}}$ for all ${(\alpha,\beta)\in \mathcal{O}}$. The group ${G}$ is an arc-transitive group of automorphisms of ${\Gamma}$. Moreover, all arc-transitive graphs arise in this way.