Connected graphs with minimum adjacency spectral gap

Abstract

Let $G$ be a connected graph, and let ${\lambda }_1(G)>{\lambda }_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference ${\lambda }_1(G)-{\lambda }_2(G)$. For integers $r\ge 2$ and $s\ge 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the complete graph $K_r$ and joining one specified vertex of each clique to a path with $s$ internal vertices. Stanić (2013) conjectured that every connected $n$-vertex graph with minimum adjacency spectral gap is a double kite. In this paper, we confirm this conjecture for sufficiently large $n$.