Timeline for Effect of different graph operations at algebraic connectivity of graph laplacian?
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2016 at 12:47 | comment | added | Delio M. | @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. | |
| Sep 25, 2011 at 13:36 | comment | added | Tyson Williams | @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 and add edges to form the Lollipop graph. The cover time gets worse; it goes from $\Theta(n^2)$ to $\Theta(n^3)$. What is happening to the eigenvalues in this example? | |
| Sep 24, 2011 at 18:36 | vote | accept | j.s. | ||
| Mar 16, 2011 at 17:16 | comment | added | Hsien-Chih Chang 張顯之 | @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.) | |
| Mar 16, 2011 at 2:03 | comment | added | j.s. | 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. | |
| Mar 16, 2011 at 1:18 | history | answered | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |