Effect of different graph operations on spectrum of graph laplacian? - MathOverflow

Effect of different graph operations on spectrum of graph laplacian?

2011-09-29T00:14:53Z

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.

Answer by fkenter for Effect of different graph operations on spectrum of graph laplacian?

2011-09-29T23:47:25Z

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

Answer by Felix Goldberg for Effect of different graph operations on spectrum of graph laplacian?

2012-03-27T12:34:22Z

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.