Automorphism groups of Cayley graphs generated by connected transposition sets

Abstract

Let $S$ be a set of transpositions that generates the symmetric group $S_n$, where $n\ge 3$. The transposition graph $T(S)$ is defined to be the graph with vertex set $\{1,\dots ,n\}$ and with vertices $i$ and $j$ being adjacent in $T(S)$ whenever $(i,j)\in S$. We prove that if the girth of the transposition graph $T(S)$ is at least 5, then the automorphism group of the Cayley graph $\Cay(S_n,S)$ is the semidirect product $R(S_n) \rtimes \Aut(S_n,S)$, where $\Aut(S_n,S)$ is the set of automorphisms of $S_n$ that fixes $S$. This strengthens a result of Feng on transposition graphs that are trees. We also prove that if the transposition graph $T(S)$ is a 4-cycle, then the set of automorphisms of the Cayley graph $\Cay(S_4,S)$ that fixes a vertex and each of its neighbors is isomorphic to the Klein 4-group and hence is nontrivial. We thus identify the existence of 4-cycles in the transposition graph as being an important factor in causing a potentially larger automorphism group of the Cayley graph.

Cited by in corpus (8)

• Automorphism group of the complete transposition graph
• Automorphism group of the complete alternating group graph
• Cayley graphs and symmetric interconnection networks
• Automorphisms of Cayley graphs generated by transposition sets
• On restricted edge-connectivity of replacement product graphs
• On the automorphism groups of connected bipartite irreducible graphs
• Automorphism group of the modified bubble-sort graph
• Structure of the automorphism group of the augmented cube graph