# 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. – Kaveh 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. – Hsien-Chih Chang 張顯之 Mar 16 '11 at 1:33
• To me, the motivation seems fairly clear. – Suresh Venkat 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. – Marcin Kotowski 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? – Tyson Williams Sep 25 '11 at 13:36