This paper deals with the Cayley graph $\Cay,$ 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. We prove that ${ \rm{ Aut}}(\Cay)$ is the product of the right translation group by $\textsf{ N}\rtimes \textsf{ D}_{ n+1},$ where $\textsf{ N}$ is the subgroup fixing $S_n$ element-wise and $\textsf{ D}_{ n+1}$ is a dihedral group of order $2(n+1)$. We conjecture that $\textsf{ N}$ is trivial. We also prove that the subgraph $\Gamma$ with vertex-set $S_n$ is a $2(n-2)$-regular graph whose automorphism group is $\textsf{ D}_{ n+1}$. Furthermore, $\Gamma$ has as many as $n+1$ maximum cliques of size $2.$ Also, its subgraph $\Gamma(V)$ whose vertices are those in these cliques is a $3$-regular, Hamiltonian, and vertex-transitive graph.
Categories: math.CO