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?
Remark1: 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.
Remark2: I asked this question before at cstheory.stackexchange, but now I think here is more appropriate for that.
Best Answer
I asked this question a long time ago, the best reference given to me is an interlacing theorem by Chen, et. al. which says that the eigenvalues of the (normalized) Laplacian of a graph $G-e$ are interlaced by the eigenvalues of the graph of $G$.
http://epubs.siam.org/sidma/resource/1/sjdmec/v18/i2/p353_s1