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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si2.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=65e5840ae0e33aadd5ea8a387817d686" title="Click to view the MathML source">Cay(Sym_n,T_n)class="mathContainer hidden">class="mathCode">, 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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si3.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=d7edeb90c8c25f56256fa986000fa7f7" title="Click to view the MathML source">Aut(Cay(Sym_n,T_n))class="mathContainer hidden">class="mathCode"> is the product of the left translation group and a dihedral group class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=db226b0aceaf3efad29425b0f12b12a4" title="Click to view the MathML source">D_n+1class="mathContainer hidden">class="mathCode"> of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si5.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=16ad57bf31bbeb5f304c548bf2159b00" title="Click to view the MathML source">2(n+1)class="mathContainer hidden">class="mathCode">. The proof uses several properties of the subgraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=14dc85a903f68577759a856ef36d9083" title="Click to view the MathML source">Γclass="mathContainer hidden">class="mathCode"> of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si2.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=65e5840ae0e33aadd5ea8a387817d686" title="Click to view the MathML source">Cay(Sym_n,T_n)class="mathContainer hidden">class="mathCode"> induced by the set class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si8.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=6596234f4714d68d202de035579722fc" title="Click to view the MathML source">T_nclass="mathContainer hidden">class="mathCode">. In particular, class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=14dc85a903f68577759a856ef36d9083" title="Click to view the MathML source">Γclass="mathContainer hidden">class="mathCode"> is a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si10.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=67970063653b8baf007a8e83cb296c87" title="Click to view the MathML source">2(n−2)class="mathContainer hidden">class="mathCode">-regular graph whose automorphism group is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si11.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=50d04492c283d6cbf1a3c0b630d7ee47" title="Click to view the MathML source">D_n+1,class="mathContainer hidden">class="mathCode">class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si6.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=14dc85a903f68577759a856ef36d9083" title="Click to view the MathML source">Γclass="mathContainer hidden">class="mathCode"> has as many as class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si13.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=43317ec0d635a9278a104fbb9338ff15" title="Click to view the MathML source">n+1class="mathContainer hidden">class="mathCode"> maximal cliques of size class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si14.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=b69aa38fd4ceb9812fb0820fe0b6b795" title="Click to view the MathML source">2class="mathContainer hidden">class="mathCode">, and its subgraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si15.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=59c0a99d3d474f688e7d1354dd3986b8" title="Click to view the MathML source">Γ(V)class="mathContainer hidden">class="mathCode"> whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si4.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=db226b0aceaf3efad29425b0f12b12a4" title="Click to view the MathML source">D_n+1class="mathContainer hidden">class="mathCode"> of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si13.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=43317ec0d635a9278a104fbb9338ff15" title="Click to view the MathML source">n+1class="mathContainer hidden">class="mathCode"> with regular Cayley maps on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si18.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=9907ee477e15c6d0824620d26a52ba66" title="Click to view the MathML source">Sym_nclass="mathContainer hidden">class="mathCode"> 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-class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si19.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=b49bd845dda01354d9c4c520140af09b" title="Click to view the MathML source">tclass="mathContainer hidden">class="mathCode">-balanced regular Cayley map on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16302035&_mathId=si18.gif&_user=111111111&_pii=S0012365X16302035&_rdoc=1&_issn=0012365X&md5=9907ee477e15c6d0824620d26a52ba66" title="Click to view the MathML source">Sym_nclass="mathContainer hidden">class="mathCode">.