A lower bound for algebraic connectivity based on the connection-graph-stability method

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously published bounds. The connection-graph-stability score for each edge is defined as the sum of the lengths of the shortest paths making use of that edge. We prove that the algebraic connectivity of the graph is bounded below by the size of the graph divided by the maximum connection-graph-stability score assigned to the edges. (C) 2010 Elsevier Inc. All rights reserved.