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 and arc set .
A graph is called edge-transitive if acts transitively on the set of edges of and is called arc-transitive if 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 be a transitive permutation group on a set . The orbits of on are called orbitals. An orbital is called self-paired if for all the element also lies in . This is equivalent to there being an element that interchanges and . For each self-paired orbital we can construct a graph with vertex set and edges for all . The group is an arc-transitive group of automorphisms of . Moreover, all arc-transitive graphs arise in this way.