Automorphism group of the modified bubble-sort graph

Preprint English OPEN
Ganesan, Ashwin (2014)
  • Subject: Mathematics - Combinatorics | Computer Science - Discrete Mathematics | Mathematics - Group Theory

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 \times D_{2n}$, for all $n \ge 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.
  • References (6)

    [1] N. L. Biggs. Algebraic Graph Theory, 2nd Edition. Cambridge University Press, Cambridge, 1993.

    [2] P. J. Cameron. Permutation Groups. London Mathematical Society Student Texts 45, Cambridge University Press, 1999.

    [3] Y-Q. Feng. Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets. Journal of Combinatorial Theory Series B, 96:67- 72, 2006.

    [4] A. Ganesan. Automorphism groups of Cayley graphs generated by connected transposition sets. Discrete Mathematics, 313:2482-2485, 2013.

    [5] C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics vol. 207, Springer, New York, 2001.

    [6] M. Isaacs. Finite Group Theory. AMS, Graduate Studies in Mathematics, Volume 92, 2008.

  • Metrics
    No metrics available
Share - Bookmark