Arc Transitive Graph

• A graph is Arc Transitive if its automorphism group acts transitively on its arcs (i.e., ordered pairs of adjacent vertices).

  • An -arc in a graph is a sequence of vertices such that consecutive vertices are adjacent and .

    A graph is -arc transitive if its automorphism group is transitive on -arcs. That is, the stabilizer on acts transitively on all -arcs with vertices starting at .

    • Let be an arc. We define the head and tail as
    • If and are -arcs, then follows if there is an -arc where and . We say that can be shunted onto .
    • denotes the directed graph with -arcs of as its vertices such that is an arc if and only if can be shunted onto .

  • An -arc transitive graph is also -arc transitive.

    • A -arc transitive graph is a vertex transitive graph.
    • A -arc transitive graph is an arc transitive graph or a symmetric graph.

  • 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). ¹

  • 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.1.3) Tutte’s Theorem If is -arc transitive graph with degree at least and girth , then

• (Godsil 4.1.4) Tutte’s Theorem If is an -arc transitive graph with girth it is bipartite with diameter .

• If is -arc transitive, then is vertex transitive.

• (Godsil 4.2.1) Let and be directed graphs and a homomorphism such that every edge is the image of an edge in . Let be a path in . Then for each such that , there is a path such that

• (Godsil 4.2.2) If is a connected graph with minimum degree two that is not a cycle, then is strongly connected for all .

• (Godsil 4.3.1) Let be a strongly connected digraph and a transitive subgroup in its automorphism group. If there is a vertex such that restricted on is an identity, then is regular.

• A graph is -arc regular if for any two -arcs, there is a unique automorphism mapping the first to the second.

• (Godsil 4.3.2) Let be a connected cubic graph that is -arc transitive but not -arc transitive. Then is -arc regular

• (Godsil 4.3.3) Tutte’s Theorem If is an -arc regular cubic graph then .

• (Godsil 4.3.4) If is an arc transitive cubic graph, and , then divides and is divisible by .

• (Godsil 4.5.3) A connected -arc transitive graph with girth is distance transitive with diameter .

Links §

• Algebraic Graph Theory by Godsil and Royle

Footnotes §

1. Note how (Godsil 3.2.1) and (Godsil 3.2.2) Deal with bipartite and Eulerian graphs. Both are edge transitive but one is vertex transitive while the other not. See graph and matroid duality for more on this. ↩