Cayley graph on symmetric groups with generating block transposition sets

الأصل · EN

This paper deals with the Cayley graph, 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 Aut() is the product of the right translation group by N Dₙ₊₁, where N is the subgroup fixing Sₙ element-wise and Dₙ₊₁ is a dihedral group of order 2(n+1). We conjecture that N is trivial. We also prove that the subgraph Γ with vertex-set Sₙ is a 2(n-2)-regular graph whose automorphism group is Dₙ₊₁. 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.