Upper Bounds on Algebraic Connectivity via Convex Optimization

Linear Algebra and its Applications, 418:693-707, October 2006.

• eigbounds_laplacian.pdf

The second smallest eigenvalue of the Laplacian matrix L of a graph is called its algebraic connectivity. We describe a method for obtaining an upper bound on the algebraic connectivity of a family of graphs G. Our method is to maximize the second smallest eigenvalue over the convex hull of the Laplacians of graphs in G, which is a convex optimization problem. By observing that it suffices to optimize over the subset of matrices invariant under the symmetry group of G, we can solve the optimization problem analytically for families of graphs with large enough symmetry groups. The same method can also be used to obtain upper bounds for other concave functions, and lower bounds for convex functions of L (such as the spectral radius).