-
A graph is Arc Transitive if its automorphism group acts transitively on its arcs (i.e., ordered pairs of adjacent vertices).
-
Arc transitive graphs are necessarily vertex and edge transitive. However, the converse is not necessarily true.
-
(Godsil 3.2.2) If a graph
is vertex and edge transitive, but not arc transitive, the degree of all vertices is even (i.e., it is Eulerian assuming connectivity). 1 -
If
is arc transitive, then the degree of all vertices is odd. -
Proof: Let
and such that . Also let be the orbit on containing . is edge transitive, therefore every arc can be mapped by automorphism to either or . is not arc transitive, therefore and thus is the graph with the edge set The out-degree of
is the same in both and we have that is even.
-
-
(Godsil 4.3.4) If
is an arc transitive cubic graph, and , then divides and is divisible by . -
(Godsil e4.4) Let
be a vertex transitive cubic graph on vertices and . If for then is arc transitive. -
Proof: We show that for any vertex
, its neighbors are preserved under automorphism. This coupled with vertex transitivity are sufficient to show arc transitivity since we can map to any vertex and its neighbors (and thus -arcs) are preserved. By (Godsil 2.4.1), we have
. It suffices, therefore, to show that . By Burnside’s Lemma.
Consider the neighborhood
and the restriction of the automorphism group on . Clearly any permutes these neighbors since preserves adjacency. Thus, the restriction of on must be a subgroup of . Because , the only possibilities for are and . If
, fixes all neighbors while fix none. If , then fixes all neighbors, transpositions fix neighbor, and all other elements fix none. In either case, Burnside’s lemma gives us . -