2014/10/29 by Korchmaros, Annachiara
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1410.8166
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 \rmAut(\Cay) is the product of the right translation group by \textsfN\rtimes \textsfDn+1, where \textsfN is the subgroup fixing Sn element-wise and \textsfDn+1 is a dihedral group of order 2(n+1). We conjecture that \textsfN is trivial. We also prove that the subgraph Γ with vertex-set Sn is a 2(n-2)-regular graph whose automorphism group is \textsfDn+1. Furthermore, Γ has as many as n+1 maximum cliques of size 2. Also, its subgraph Γ(V) whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph.