s-Arc Transitive Graph

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

• (Godsil 4.1.3) Tutte’s Theorem If is -arc transitive graph with degree at least and girth , then

  • Proof: Assume . contains a cycle of length and a path of length whose end vertices are not adjacent. To see the latter, take vertex in the cycle. It has degree therefore it must be adjacent to a vertex . not in the cycle. The path thus starts at and travels along the cycle.

    No automorphism maps a -arc corresponding to a cycle and a -arc corresponding to a path. Therefore . Any -arc must lie in a cycle.

    Consider and where . Delete and the graph contains a cycle of length at most . The result follows.

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

  • Proof: If has girth , every -arc lies in at most one cycle of length . therefore has diameter at least . Additionally, if , then there is an -arc, lying in the cycle, joining it to a vertex in the cycle. Thus .

    If is not bipartite, it contains an odd cycle. Since the diameter is , the cycle must have length . Two adjacent vertices in the cycle of distance from forms an -arc which clearly forms a cycle of length () which is a contradiction.

• 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 , and it maps the out-neighbors of to the out-neighbors of . Let be a path in . Then for each such that , there is a path such that

  • Proof: Since there always exists such that , what remains is to show that each of the forms a directed path. Since each has a corresponding and . Repeatedly apply the latter to get a path of any length.

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

  • Idea: Treat as a homomorphism from . Clearly, every edge of is an image of an edge in and neighborhoods are also clearly preserved. Thus, edges and paths are also preserved by (Godsil 4.2.1 ). Take as -arcs. Argue by induction. By connectivity of , there is a path joining to . This path is preserved under homomorphism such that and .

    The proof proceeds by induction. The base case for shows that it is possible to shunt onto .

• 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

  • Proof: has degree . Let , and . acts vertex transitively on .

    Suppose is non-trivial on the out-neighbors of . must swap the -arcs following .

    By transitivity, map two -arcs in to arcs that have as the initial -arc. Thus, is also transitive on which is a contradiction.

    Therefore and is regular by (Godsil 4.3.1)

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

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

  • Proof: By (Godsil 4.1.4), the graph has diameter . Therefore, we can map -arcs, to each other by arc transitivity. Therefore, two vertices remain the same distance and thus the graph is distance transitive.

Links §

• Algebraic Graph Theory by Godsil and Royle