Automorphism group of the modified bubble-sort graph

2014/09/21 by Ashwin Ganesan, Ganesan, Ashwin
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR) #cs.DM #math.CO #math.GR

paper · pdf · doi:10.48550/arxiv.1409.5959

arxiv created 2015/05/09 · arxiv updated 2015/05/12

Abstract

The modified bubble-sort graph of dimension n is the Cayley graph of S_n generated by n cyclically adjacent transpositions. In the present paper, it is shown that the automorphism group of the modified bubble sort graph of dimension n is S_n × D_2n, for all n ≥ 5. Thus, a complete structural description of the automorphism group of the modified bubble-sort graph is obtained. A similar direct product decomposition is seen to hold for arbitrary normal Cayley graphs generated by transposition sets.

Related

• Automorphism groups of Cayley graphs generated by general transposition sets
• Automorphism groups of graphs
• Automorphisms of Cayley graphs generated by transposition sets
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps
• On the Decycling Number of Bubble-sort Star Graphs