<p>Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity. </p>

<p>In general, if H is a subgraph of a graph G, by interlacing we know that the i-th largest Laplacian eigenvalue of H is no larger than the i-th largest Laplacian eigenvalue of G. A proof can be found in Proposition 3.2.1 of the book "<a href="http://homepages.cwi.nl/~aeb/math/ipm.pdf">Spectra of graphs</a>" by Brouwer and Haemers. Note that the definition of Laplacian used in the book is not normalized; it has node degrees on the diagonal and -1 (or 0 if there is no edge) in the off-diagonal entries.</p>

CC BY-SA 2.5
2011-03-16T02:03:24.010Z
Thanks Chang. Your answer is really useful for me. But if we use the definition of Laplacian that is not normalized, then many of comparisons seems to be meaningless. For example we have  Algebraic Connectivity(K10)=10  and  Algebraic Connectivity(K20)=20. however, both graphs are fully connected simple graphs. But if we use the normalized Laplacian, then NormalizedAlgebraicConnectivity(K10) = NormalizedAlgebraicConnectivity(K20)=1 and therefore comparison of normalized version seems to be more rational and natural.
j.s.
CC BY-SA 2.5
2011-03-16T17:16:29.217Z
@behnam: I agree with you. But after the normalization, some of the nondecreasing properties may differ. (Say one can ensure a strict decreasing on the largest Laplacian when deleting edges for the unnormalized ones, but not for the normalized ones.)
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-09-25T13:36:45.667Z
@Hsien-Chih Chang "Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity." Are you sure? Do you have a proof? Is the following a counter example? Start with a [path graph](http://en.wikipedia.org/wiki/Path_graph) and add edges to form the [Lollipop graph](http://mathworld.wolfram.com/LollipopGraph.html). The cover time gets worse; it goes from $\Theta(n^2)$ to $\Theta(n^3)$. What is happening to the eigenvalues in this example?
Tyson Williams
CC BY-SA 3.0
2016-10-09T12:47:16.177Z
@TysonWilliams You are very right. This is one of the theoretical aspects where normalized and unnormalized Laplacians do differ. By adding edges, the unnormalized algebraic connectivity always goes up (Fiedler), but there are (not even very tricky) examples showing that edges added in the wrong places might diminish connectivity. This is particularly easy to see if you allow for edge weights.
Delio M.
CC BY-SA 2.5
2011-03-16T01:18:49.590Z
2011-03-16T01:18:49.590Z
Hsien-Chih Chang 張顯之
<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></p>

<p>Does anyone has studied effect of different operations (such as edge contraction) on spectrum of laplacian?
do you know good references?</p>

<p>Remark: 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.pd" 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>

CC BY-SA 2.5
2011-03-16T01:33:33.267Z
I'm also interested in the edge contraction case. I've spend some time previously trying to find references about the relation between eigenvalues and minor operations, with no success.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-03-11T21:54:49.670Z
It would help if you provide some motivation and background. Please see [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) and the site's
[FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science).
Kaveh
CC BY-SA 3.0
2011-09-24T20:12:48.427Z
To me, the motivation seems fairly clear.
Suresh Venkat
CC BY-SA 3.0
2011-09-24T20:50:10.097Z
I second Suresh, knowing how various operations influence the Laplacian is interesting in itself and this problems shows up in various contexts.
Marcin Kotowski
<graph-theory><co.combinatorics><spectral-graph-theory>
Effect of different graph operations at algebraic connectivity of graph laplacian?
j.s.
# Effect of different graph operations at algebraic connectivity of graph laplacian?

(Asked by: username_0 on 2011-03-11)

The [algebraic connectivity](http://en.wikipedia.org/wiki/Algebraic_connectivity) of a graph G is the second-smallest eigenvalue of the [Laplacian matrix](http://en.wikipedia.org/wiki/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?

Remark: 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](http://www.math.ucsd.edu/~fan/research/cb/ch1.pd). In this book Fan Chung has uesed a rescaled version of the Laplacian, eliminating the dependence on the number of vertices.

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory

> **Comments:**
> **username_2**: It would help if you provide some motivation and background. Please see [How to ask a good question?](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) and the site's [FAQ](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science).  
> **username_1**: I'm also interested in the edge contraction case. I've spend some time previously trying to find references about the relation between eigenvalues and minor operations, with no success.  
> **username_3**: To me, the motivation seems fairly clear.  
> **username_4**: I second Suresh, knowing how various operations influence the Laplacian is interesting in itself and this problems shows up in various contexts.  

---

## 1 answers

### Answer by username_1 on 2011-03-16. Score: 5 | Accepted answer

Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity.

In general, if H is a subgraph of a graph G, by interlacing we know that the i-th largest Laplacian eigenvalue of H is no larger than the i-th largest Laplacian eigenvalue of G. A proof can be found in Proposition 3.2.1 of the book "[Spectra of graphs](http://homepages.cwi.nl/~aeb/math/ipm.pdf)" by Brouwer and Haemers. Note that the definition of Laplacian used in the book is not normalized; it has node degrees on the diagonal and -1 (or 0 if there is no edge) in the off-diagonal entries.

> **Comments:**
> **username_0**: Thanks Chang. Your answer is really useful for me. But if we use the definition of Laplacian that is not normalized, then many of comparisons seems to be meaningless. For example we have  Algebraic Connectivity(K10)=10  and  Algebraic Connectivity(K20)=20. however, both graphs are fully connected simple graphs. But if we use the normalized Laplacian, then NormalizedAlgebraicConnectivity(K10) = NormalizedAlgebraicConnectivity(K20)=1 and therefore comparison of normalized version seems to be more rational and natural.  
> **username_1**: @behnam: I agree with you. But after the normalization, some of the nondecreasing properties may differ. (Say one can ensure a strict decreasing on the largest Laplacian when deleting edges for the unnormalized ones, but not for the normalized ones.)  
> **username_5**: @Hsien-Chih Chang "Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity." Are you sure? Do you have a proof? Is the following a counter example? Start with a [path graph](http://en.wikipedia.org/wiki/Path_graph) and add edges to form the [Lollipop graph](http://mathworld.wolfram.com/LollipopGraph.html). The cover time gets worse; it goes from $\Theta(n^2)$ to $\Theta(n^3)$. What is happening to the eigenvalues in this example?  
> **username_6**: @TysonWilliams You are very right. This is one of the theoretical aspects where normalized and unnormalized Laplacians do differ. By adding edges, the unnormalized algebraic connectivity always goes up (Fiedler), but there are (not even very tricky) examples showing that edges added in the wrong places might diminish connectivity. This is particularly easy to see if you allow for edge weights.  

---

