Spectrum of the Transposition graph

Abstract

Transposition graph $T_n$ is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of $T_n$ are integers. However, an explicit description of the spectrum is unknown. In this paper we prove that for any integer $k⩾0$ there exists $n_0$ such that for any $n⩾n_0$ and any $m\in \{0,\dots ,k\}$, $m$ is an eigenvalue of $T_n$. In particular, it is proved that zero is an eigenvalue of $T_n$ for any $n\ne 2$, and one is an eigenvalue of $T_n$ for any odd $n⩾7$ and for any even $n⩾14$. We also present exact values of the third and the fourth largest eigenvalues of $T_n$ with their multiplicities.

References in corpus (1)

• Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph