On the algebraic connectivity of graphs

Abstract

Algebraic connectivity, or the second smallest eigenvalue of the Laplacian matrix, is a well-studied parameter in spectral graph theory. In this thesis, we present new upper bounds and asymptotic estimates for the algebraic connectivity of regular graphs. They include a generalization of an upper bound given by Kolokolnikov as well as an upper bound valid for specific cubic graphs. Furthermore, we introduce two new graph families, which we call the necklace graphs and the hourglass graphs. We proceed to determine the complete spectrum of general necklace graphs in terms of a matrix involving roots of unity. We then consider a class of regular necklace graphs and derive a first term asymptotic estimate applicable to their algebraic connectivity. We also numerically investigate which algorithm returns graphs with the highest algebraic connectivity amongst those with fixed order and size.