Growing well-connected graphs

The algebraic connectivity of a graph is the second smallest eigenvalue of the graph Laplacian, and is a measure of how well-connected the graph is. We study the problem of adding edges (from a set of candidate edges) to a graph so as to maximize its algebraic connectivity. This is a difficult combinatorial optimization, so we seek a heuristic for approximately solving the problem. The standard convex relaxation of the problem can be expressed as a semidefinite program (SDP); for modest sized problems, this yields a cheaply computable upper bound on the optimal value, as well as a heuristic for choosing the edges to be added. We describe a new greedy heuristic for the problem. The heuristic is based on the Fiedler vector, and therefore can be applied to very large graphs.