Cayley graph on symmetric groups with generating block transposition sets

Abstract

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 $\text{N}⋊{\text{D}}_{n+1},$ where $\text{N}$ is the subgroup fixing $S_n$ element-wise and ${\text{D}}_{n+1}$ is a dihedral group of order $2(n+1)$. We conjecture that $\text{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 ${\text{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.

References in corpus (1)

• Upper bound on the block transposition diameter of the symmetric group