On the Spectrum of the Generalised Petersen Graphs

Abstract

We show that the gap between the two greatest eigenvalues of the generalised Petersen graphs $P(n,k)$ tends to zero as $n\to \infty$. Moreover, we provide explicit upper bounds on the size of this gap. It follows that these graphs have poor expansion properties for large values of $n$. We also show that a positive proportion of the eigenvalues of $P(n,k)$ tend to the valency.

10 pages; feedback welcome