Extremal graphs for the $k$-th eigenvalue

Abstract

For a simple graph $G$ of order $n$, let ${\lambda }_1(G)\ge \cdots \ge {\lambda }_n(G)$ denote its adjacency eigenvalues. Hong's problem asks for the optimal upper bound for ${\lambda }_k(G)$. A recent theorem of Sivashankar gives, for every $k\ge 3$, \[ λ_k(G)\le \frac{(k-2)\sqrt{k+1}+2}{2k(k-1)}\,n-1, \] with sharp examples arising from maximal real equiangular tight frames. In this paper, we characterize the equality case. We also obtain an explicit combinatorial description of the extremal graphs for ${\lambda }_3$ and ${\lambda }_4$.

Preliminary draft, commments are welcome