Graph symmetry II

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.


Continue reading “Graph symmetry II”

Blog at

Up ↑