Automorphism group of the complete transposition graph

Abstract

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 $\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 4 cyclically adjacent transpositions is not normal. In the present paper, it is proved that the complete transposition graph is not a normal Cayley graph, for all $n\ge 3$. Furthermore, the automorphism group of the complete transposition graph is shown to equal \[ \Aut(\Cay(S_n,S)) = (R(S_n) \rtimes \Inn(S_n)) \rtimes \mathbb{Z}_2, \] where $R(S_n)$ is the right regular representation of $S_n$, $\Inn(S_n)$ is the group of inner automorphisms of $S_n$, and ${\mathbb{Z}}_2=⟨h⟩$, where $h$ is the map $\alpha \mapsto {\alpha }^{-1}$.

Cited by in corpus (9)

• Automorphism group of the complete alternating group graph
• Cayley graphs and symmetric interconnection networks
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• On Cayley representations of central Cayley graphs over almost simple groups
• Automorphism group of the modified bubble-sort graph
• Structure of the automorphism group of the augmented cube graph
• Automorphism groups of a class of cubic Cayley graphs on symmetric groups
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• On the automorphism groups of connected bipartite irreducible graphs