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.

Continue reading “Graph symmetry II”