pith. sign in

arxiv: 1205.5199 · v4 · pith:I4A7IB76new · submitted 2012-05-23 · 💻 cs.DM · math.CO

Automorphism groups of Cayley graphs generated by connected transposition sets

classification 💻 cs.DM math.CO
keywords graphtranspositioncayleygroupautomorphismautomorphismsfixesgraphs
0
0 comments X
read the original 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,\ldots,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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.