On graphs with large third eigenvalue

Abstract

Given a graph $G$, let $\hat{I}{»}_3$ denote the third largest eigenvalue of its adjacency matrix. In this paper, we prove various results towards the conjecture that $\hat{I}{»}_3(G)\le \frac{|V(G)|}{3}$, motivated by a question of Nikiforov. We generalise the known constructions that yield $\hat{I}{»}_3(G)=\frac{|V(G)|}{3}-1$ and prove the inequality holds for $G$ strongly regular, a regular line graph or a Cayley graph on an abelian group. We also consider the extended problem of minimising $\hat{I}{»}_{n-1}$ on weighted graphs and reduce the existence of a minimiser with simple final eigenvalue to a vertex multiplication of a graph on 11 vertices. We prove that the minimal $\hat{I}{»}_{n-1}$ over weighted graphs is at most $O(\sqrt{n})$ from the minimal $\hat{I}{»}_{n-1}$ over unweighted graphs.