Cayley Digraph

• A Cayley Digraph is a Directed Graph where each vertex corresponds to an element of and each edge , corresponds to where is a generator of . We overlay multiple such edge types for each element in some generating set .

• If we are considering only subgraphs of a Cayley digraph using generating set , we use the notation . In such a case, the arc set is defined as

• A Cayley Digraph necessarily and sufficiently satisfies the following properties.

  • (Godsil 3.7.4) The digraph using the entire generating set (i.e, ) is necessarily connected because every linear equation in the group has a solution.

  • The digraph has at most one arc from to because the solution is unique.

    That is, another way to formulate the digraph is via the arc set

    Where .

  • Each vertex has exactly one arc of each type starting at and one arc of each type ending at because the products are unique.

  • If two different sequences of arc types starting from lead to the same vertex , then those same arc types starting from any vertex will lead to .

    If , then

• (Godsil 3.1.2) Cayley graphs are vertex transitive.

• (Godsil 3.7.1; Godsil 3.7.2) Let be a group and an inverse-closed subset of . Then the automorphism group contains a regular subgroup isomorphic to .

  Conversely if a group acts regularly on the vertices of , then is a Cayley graph for relative to some inverse closed subset of .

  • Proof: The forward direction follows by considering the permutation . It can be shown that . The left regular permutations form a subgroup isomorphic to .

    The converse is shown as follows. Fix and choose . Because is regular, it is transitive thus, there exists such that .

    Let . These classes (formed via the generators of ) determine subgraphs in the Cayley graph. Inverse closure is provided because is transitive.

• (Godsil 3.7.3) If is an automorphism of , then

• (Godsil 3.8.1) Let be generators of and be the directed Cayley graph of . Also suppose that have and cycles respectively, in their action by left multiplication on . If } is odd and has a partition into disjoint directed cycles, then have the same parity.

  • Proof: Consider a permutation such that if is in one of the directed cycles. Define the partitions as and .

    The permutation defined by fixes every element of and so fixes . Thus for any . is odd then so is . Thus, is an even permutation.

    The result follows by considering that the parity of a permutation on elements with cycles equals the parity of . Here and are both even so share the same parity.

• (Godsil 3.8.2) If is even and , then the directed Cayley graph corresponding to is not Hamiltonian.

  • Proof: If is even, the vertices can be partitioned into an even number of directed cycles, which means there are no Hamiltonian cycles.

• (Godsil e3.9) Let be an Abelian group and an inverse closed subset of . If then has girth of at most .

  • Proof:: Let and . A cycle of length can always be formed as follows assuming
    If then we have at least one element such that . The above cycle can still be formed by replacing with .

• (Godsil e3.10) Let be an inverse-closed subset of . If is Abelian and contains an element such that , then

  • Proof: By (Godsil 3.7.1) contains a regular subgroup . Let be the automorphism defined by . Clearly this preserves adjacency since so it is a graph automorphism.

    is non-trivial because .

    Also . Otherwise for any

    So it is always possible to find an element for which left multiplication does not map to the inverse. Alternatively for all but this contradicts the existence of . Therefore is not a left multiplication and the subgroup formed by gives us our second subgroup. By Lagrange’s Theorem, we get our bound.

Links §

• Algebraic Graph Theory by Godsil and Royle
• A First Course in Abstract Algebra 7th Edition by Fraleigh