Automorphism group of the complete transposition graph

Ganesan, Ashwin

Journal of Algebraic Combinatorics, Tome 42 (2015) no. 3, pp. 793-801.

Résumé

The complete transposition graph is defined to be the graph whose vertices are the elements of the symmetric group $S_n$, and two vertices $\alpha$ and $\beta$ are adjacent in this graph iff there is some transposition $(i,j)$ such that $\alpha=(i,j)\beta$. Thus, the complete transposition graph is the Cayley graph $\mathrm{Cay}(S_n,S)$ of the symmetric group generated by the set $S$ of all transpositions. An open problem in the literature is to determine which Cayley graphs are normal. It was shown recently that the Cayley graph generated by four cyclically adjacent transpositions is non-normal. In the present paper, it is proved that the complete transposition graph is not a normal Cayley graph, for all $n\geq 3$. Furthermore, the automorphism group of the complete transposition graph is shown to equal $$\mathrm{Aut}(\mathrm{Cay}(S_n,S))=(R(S_n)\rtimes\mathrm{Inn}(S_n))\rtimes\mathbb Z_2,$$ where $R(S_n)$ is the right regular representation of $S_n$, $\mathrm{Inn}(S_n)$ is the group of inner automorphisms of $S_n$, and $\mathbb Z_2=\langle h\rangle$, where $h$ is the map $\alpha\mapsto\alpha^{-1}$.

Détail

Classification : 05C25, 05C60, 20B30
Keywords: complete transposition graph, automorphisms of graphs, normal Cayley graphs