Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_n$.