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 hmlsrc">hImg" 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)hContainer hidden">hCode">h id="mml2" overflow="scroll" altimg="si2.gif">hvariant="normal">Cayw>(w>hvariant="normal">Symw>w>nw>,w>Tw>w>nw>)w>h>, 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 hmlsrc">hImg" 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))hContainer hidden">hCode">h id="mml3" overflow="scroll" altimg="si3.gif">Autw>(hvariant="normal">Cayw>(w>hvariant="normal">Symw>w>nw>,w>Tw>w>nw>)w>)w>h> is the product of the left translation group and a dihedral group hmlsrc">hImg" 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+1hContainer hidden">hCode">h id="mml4" overflow="scroll" altimg="si4.gif">w>hvariant="sans-serif">Dw>w>n+1w>h> of order hmlsrc">hImg" 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)hContainer hidden">hCode">h id="mml5" overflow="scroll" altimg="si5.gif">2w>(n+1)w>h>. The proof uses several properties of the subgraph hmlsrc">hImg" 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">ΓhContainer hidden">hCode">h id="mml6" overflow="scroll" altimg="si6.gif">Γh> of hmlsrc">hImg" 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)hContainer hidden">hCode">h id="mml7" overflow="scroll" altimg="si2.gif">hvariant="normal">Cayw>(w>hvariant="normal">Symw>w>nw>,w>Tw>w>nw>)w>h> induced by the set hmlsrc">hImg" 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_nhContainer hidden">hCode">h id="mml8" overflow="scroll" altimg="si8.gif">w>Tw>w>nw>h>. In particular, hmlsrc">hImg" 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">ΓhContainer hidden">hCode">h id="mml9" overflow="scroll" altimg="si6.gif">Γh> is a hmlsrc">hImg" 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)hContainer hidden">hCode">h id="mml10" overflow="scroll" altimg="si10.gif">2w>(n−2)w>h>-regular graph whose automorphism group is hmlsrc">hImg" 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,hContainer hidden">hCode">h id="mml11" overflow="scroll" altimg="si11.gif">w>hvariant="sans-serif">Dw>w>n+1w>,h>hmlsrc">hImg" 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">ΓhContainer hidden">hCode">h id="mml12" overflow="scroll" altimg="si6.gif">Γh> has as many as hmlsrc">hImg" 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+1hContainer hidden">hCode">h id="mml13" overflow="scroll" altimg="si13.gif">n+1h> maximal cliques of size hmlsrc">hImg" 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">2hContainer hidden">hCode">h id="mml14" overflow="scroll" altimg="si14.gif">2h>, and its subgraph hmlsrc">hImg" 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)hContainer hidden">hCode">h id="mml15" overflow="scroll" altimg="si15.gif">Γw>(V)w>h> whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of hmlsrc">hImg" 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+1hContainer hidden">hCode">h id="mml16" overflow="scroll" altimg="si4.gif">w>hvariant="sans-serif">Dw>w>n+1w>h> of order hmlsrc">hImg" 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+1hContainer hidden">hCode">h id="mml17" overflow="scroll" altimg="si13.gif">n+1h> with regular Cayley maps on hmlsrc">hImg" 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_nhContainer hidden">hCode">h id="mml18" overflow="scroll" altimg="si18.gif">w>Symw>w>nw>h> 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-hmlsrc">hImg" 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">thContainer hidden">hCode">h id="mml19" overflow="scroll" altimg="si19.gif">th>-balanced regular Cayley map on hmlsrc">hImg" 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_nhContainer hidden">hCode">h id="mml20" overflow="scroll" altimg="si18.gif">w>Symw>w>nw>h>.