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 g e q s l a n t 0

there exists

n_{0}

such that for any

n g e q s l a n t n_{0}

and any

m i n 0, d o t s, k

,

m

is an eigenvalue of

T_{n}

. In particular, it is proved that zero is an eigenvalue of

T_{n}

for any

n e q 2

, and one is an eigenvalue of

T_{n}

for any odd

n g e q s l a n t 7

and for any even

n g e q s l a n t 14

. We also present exact values of the third and the fourth largest eigenvalues of

T_{n}

with their multiplicities.

Cites Work

Uses Software

This page was built for publication: Spectrum of the transposition graph