Maximum spectral gaps of graphs

Abstract

The spread of a graph $G$ is the difference $\hat{I}{»}_1-\hat{I}{»}_n$ between the largest and smallest eigenvalues of its adjacency matrix. Breen, Riasanovsky, Tait and Urschel recently determined the graph on $n$ vertices with maximum spread for sufficiently large $n$. In this paper, we study a related question of maximizing the difference $\hat{I}{»}_{i+1}-\hat{I}{»}_{n-j}$ for a given pair $(i,j)$ over all graphs on $n$ vertices. We give upper bounds for all pairs $(i,j)$, exhibit an infinite family of pairs where the bound is tight, and show that for the pair $(1,0)$ the extremal example is unique. These results contribute to a line of inquiry pioneered by Nikiforov aiming to maximize different linear combinations of eigenvalues over all graphs on $n$ vertices.

12 pages, 5 figures