Upper bounds on the algebraic connectivity of graphs

Abstract

The algebraic connectivity of a connected graph $G$ is the second smallest eigenvalue of the Laplacian matrix of $G$. In this paper, some new upper bounds on algebraic connectivity are obtained by applying generalized interlacing to an appropriate quotient matrix.