文摘
This paper deals with the Cayley graph e5840ae0e33aadd5ea8a387817d686" title="Click to view the MathML source">Cay(Symn,Tn), 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 986000fa7f7" title="Click to view the MathML source">Aut(Cay(Symn,Tn)) is the product of the left translation group and a dihedral group Dn+1 of order bbeb5f304c548bf2159b00" title="Click to view the MathML source">2(n+1). The proof uses several properties of the subgraph Γ of e5840ae0e33aadd5ea8a387817d686" title="Click to view the MathML source">Cay(Symn,Tn) induced by the set Tn. In particular, Γ is a baf007a8e83cb296c87" title="Click to view the MathML source">2(n−2)-regular graph whose automorphism group is e47" title="Click to view the MathML source">Dn+1,Γ has as many as bb9338ff15" title="Click to view the MathML source">n+1 maximal cliques of size 9812fb0820fe0b6b795" title="Click to view the MathML source">2, and its subgraph 986b8" title="Click to view the MathML source">Γ(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 Dn+1 of order bb9338ff15" title="Click to view the MathML source">n+1 with regular Cayley maps on e477e15c6d0824620d26a52ba66" title="Click to view the MathML source">Symn is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-t-balanced regular Cayley map on e477e15c6d0824620d26a52ba66" title="Click to view the MathML source">Symn.