Proof of a conjecture on eigenvalues of transposition graph

Abstract

The transposition graph $Cay(S_n,T_n)$ is the Cayley graph on the symmetric group $S_n$ generated by the set $T_n$ of all transpositions. In this paper, we show that each integer in the interval $\left[-\left(\genfrac{}{}{0ex}{}{\lfloor (2n+1)/3\rfloor }{2}\right),\left(\genfrac{}{}{0ex}{}{\lfloor (2n+1)/3\rfloor }{2}\right)\right]$ is an eigenvalue of $Cay(S_n,T_n)$. This proves a recent conjecture by Kravchuk \cite{Kravchuk}.