Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

详细信息    查看全文

• 作者：Annachiara Korchmaros^a ; ^{akorchmaros3@gatech.edu" class="auth_mail" title="E-mail the corresponding author} ; Istvá ; n Ková ; cs^b ; ^{istvan.kovacs@upr.si" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Cayley graph ; Symmetric group ; Block transposition ; Graph automorphism ; Cayley map ; Regular map
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 January 2017
• 年：2017
• 卷：340
• 期：1
• 页码：3125-3139
• 全文大小：534 K

文摘

This paper deals with the Cayley graph Cay(Sym_n,T_n)$\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, 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 Aut(Cay(Sym_n,T_n))$\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group D_n+1${\mathsf{D}}_{n+1}$ of order 2(n+1)$2(n+1)$. The proof uses several properties of the subgraph Γ$\Gamma$ of Cay(Sym_n,T_n)$\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set T_n$T_n$. In particular, Γ$\Gamma$ is a 2(n−2)$2(n-2)$-regular graph whose automorphism group is D_n+1,${\mathsf{D}}_{n+1},$Γ$\Gamma$ has as many as n+1$n+1$ maximal cliques of size 2$2$, and its subgraph Γ(V)$\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of D_n+1${\mathsf{D}}_{n+1}$ of order n+1$n+1$ with regular Cayley maps on Sym_n${\text{Sym}}_n$ 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$t$-balanced regular Cayley map on Sym_n${\text{Sym}}_n$.