Automorphism Group of the Derangement Graph

Abstract

In this paper, we prove that the full automorphism group of the derangement graph $\Gamma_n$ ($n\geq3$) is equal to $(R(S_n)\rtimes\hbox{Inn} (S_n))\rtimes Z_2$, where $R(S_n)$ and $\hbox{Inn} (S_n)$ are the right regular representation and the inner automorphism group of $S_n$ respectively, and $Z_2=\langle\varphi\rangle$ with the mapping $\varphi:$ $\sigma^{\varphi}=\sigma^{-1},\,\forall\,\sigma\in S_n.$ Moreover, all orbits on the edge set of $\Gamma_n$ ($n\geq3$) are determined.