Effect of different graph operations on spectrum of graph laplacian? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T16:11:24Z http://mathoverflow.net/feeds/question/76711 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76711/effect-of-different-graph-operations-on-spectrum-of-graph-laplacian Effect of different graph operations on spectrum of graph laplacian? b.a 2011-09-29T00:14:53Z 2012-03-27T12:34:22Z <p>The <a href="http://en.wikipedia.org/wiki/Algebraic_connectivity" rel="nofollow">algebraic connectivity</a> of a graph G is the second-smallest eigenvalue of the <a href="http://en.wikipedia.org/wiki/Laplacian_matrix" rel="nofollow">Laplacian matrix</a> 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.</p> <p>for an example, "<strong>adding self-loops</strong>" does not change laplacian eigenvalues (specially algebraic connectivity) of graph. Because, laplacian(G)= D-A is invariant with respect to adding self-loops.</p> <p><em>My question is:</em> Does anyone has studied effect of different operations (such as edge contraction) on spectrum of laplacian? do you know good references?</p> <p>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 <a href="http://www.math.ucsd.edu/~fan/research/cb/ch1.pdf" rel="nofollow">SPECTRAL GRAPH THEORY</a>. In this book Fan Chung has uesed a rescaled version of the Laplacian, eliminating the dependence on the number of vertices.</p> <p>Remark2: I asked this question before at <a href="http://cstheory.stackexchange.com/questions/5439/effect-of-different-graph-operations-at-algebraic-connectivity-of-graph-laplacian" rel="nofollow">cstheory.stackexchange</a>, but now I think here is more appropriate for that.</p> http://mathoverflow.net/questions/76711/effect-of-different-graph-operations-on-spectrum-of-graph-laplacian/76816#76816 Answer by fkenter for Effect of different graph operations on spectrum of graph laplacian? fkenter 2011-09-29T23:47:25Z 2011-09-29T23:47:25Z <p>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\$.</p> <p><a href="http://epubs.siam.org/sidma/resource/1/sjdmec/v18/i2/p353_s1" rel="nofollow">http://epubs.siam.org/sidma/resource/1/sjdmec/v18/i2/p353_s1</a></p> http://mathoverflow.net/questions/76711/effect-of-different-graph-operations-on-spectrum-of-graph-laplacian/92368#92368 Answer by Felix Goldberg for Effect of different graph operations on spectrum of graph laplacian? Felix Goldberg 2012-03-27T12:34:22Z 2012-03-27T12:34:22Z <p>You can start by looking up the classical 1994 survey by Merris:</p> <p><a href="http://www.sciencedirect.com/science/article/pii/0024379594904863" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0024379594904863</a></p> <p>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.</p>