Effect of different graph operations at algebraic connectivity of graph laplacian?

The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this value reflects how well connected the overall graph is.

for an example, "adding self-loops" does not change laplacian eigenvalues (specially algebraic connectivity) of graph. Because, laplacian(G)= D-A is invariant with respect to adding self-loops.

My question is:

Does anyone has studied effect of different operations (such as edge contraction) on spectrum of laplacian? do you know good references?

Remark: the exact definition of the algebraic connectivity depends on the type of Laplacian used. For this question I prefer to use Fan Chung definition in SPECTRAL GRAPH THEORY. In this book Fan Chung has uesed a rescaled version of the Laplacian, eliminating the dependence on the number of vertices.

• It would help if you provide some motivation and background. Please see How to ask a good question? and the site's FAQ. Mar 11 '11 at 21:54
• I'm also interested in the edge contraction case. I've spend some time previously trying to find references about the relation between eigenvalues and minor operations, with no success. Mar 16 '11 at 1:33
• To me, the motivation seems fairly clear. Sep 24 '11 at 20:12
• I second Suresh, knowing how various operations influence the Laplacian is interesting in itself and this problems shows up in various contexts. Sep 24 '11 at 20:50

• @Hsien-Chih Chang "Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity." Are you sure? Do you have a proof? Is the following a counter example? Start with a path graph and add edges to form the Lollipop graph. The cover time gets worse; it goes from $\Theta(n^2)$ to $\Theta(n^3)$. What is happening to the eigenvalues in this example? Sep 25 '11 at 13:36