Loading...
research article
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.
Type
research article
Web of Science ID
WOS:000289496500013
Authors
Publication date
2011
Publisher
Published in
Volume
435
Issue
1
Start page
186
End page
192
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 25, 2011
Use this identifier to reference this record