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

Abstract

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 Aut$(\mathrm{Cay}({\mathrm{Sym}}_n,T_n))$ is the product of the left translation group by 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 (V)$ 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 ${\mathrm{Sym}}_n$ is also discussed. It is shown that the product of the left translation group by the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\mathrm{Sym}}_n$.