Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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

share|improve this answer
add comment

You can start by looking up the classical 1994 survey by Merris:

http://www.sciencedirect.com/science/article/pii/0024379594904863

There is a lot of newer work that has been published since then, but I think that Merris's paper is still a good introduction.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.