4
$\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$
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

| cite | improve this answer | |
$\endgroup$
1
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The OP is interested in the normalised Laplacian, whereas Merris discusses the classical graph Laplacian, I believe. $\endgroup$ – Delio Mugnolo May 8 '16 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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