5
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The OP is interested in the normalised Laplacian, whereas Merris discusses the classical graph Laplacian, I believe. $\endgroup$ May 8, 2016 at 23:25
1
$\begingroup$

I am going to plug my own work here in case people still stumble on this post: "Deletion-contraction for a unified Laplacian and applications", by F. Aliniaeifard, V. Wang and S. van Willigenburg, describes the effects of edge deletion and contraction on Laplacian eigenvalues. In particular, we note that there is a deletion-contraction recurrence on the level of graph Laplacian characteristic polynomials when we allow for vertex weights, which leads to interlacing eigenvalue theorems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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