On a conjecture of Kolokolnikov on algebraic connectivity

Abstract

For a graph $G$, let $\alpha(G)$ be the second smallest eigenvalue of the Laplacian matrix of $G$, also known as the algebraic connectivity. Algebraic connectivity plays an important role in characterizing the connectivity of graphs and convergence properties of networks. Kolokolnikov conjectured that among all graphs on $n$ vertices with exactly $2n-4$ edges, $\alpha(G)\leq 2$ and one of the maximizers is the complete bipartite graph whose two parts have sizes two and $n-2$, respectively. In this paper, we completely resolve this conjecture.