A sharp upper bound on the third adjacency eigenvalue of a graph

Abstract

For a graph $G$ of order $n$, let $${\lambda }_1(G)\ge \cdots \ge {\lambda }_n(G)$$ be the eigenvalues of its adjacency matrix. We prove that every graph $G$ on $n\ge 3$ vertices satisfies $${\lambda }_3(G)\le \frac{n}{3}-1,$$ thereby solving a problem of Nikiforov. The bound is best possible whenever $3\mid n$. Our proof is derived from a more general matrix result: if $A=(a_{ij})$ is a real symmetric matrix of order $n$ with $0\le a_{ij}\le 1$ for all off-diagonal entries and $a_{ii}\ge 0$ for all $i$, then $${\lambda }_{n-1}(A)+{\lambda }_n(A)\ge -\frac{2n}{3}.$$ This in particular confirms a conjecture of Leonida and Li.

arXiv comment6 pages. Comments and suggestions are welcome