| Title:
|
A Fiedler-like theory for the perturbed Laplacian (English) |
| Author:
|
Rocha, Israel |
| Author:
|
Trevisan, Vilmar |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
717-735 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The perturbed Laplacian matrix of a graph $G$ is defined as $L^{\mkern -15muD}=D-A$, where $D$ is any diagonal matrix and $A$ is a weighted adjacency matrix of $G$. We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use the notion of Perron component for the perturbed Laplacian matrix of a graph and show how its second smallest eigenvalue can be characterized using this definition. (English) |
| Keyword:
|
perturbed Laplacian matrix |
| Keyword:
|
Fiedler vector |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
graph partitioning |
| MSC:
|
05C22 |
| MSC:
|
05C50 |
| MSC:
|
15B57 |
| idZBL:
|
Zbl 06644029 |
| idMR:
|
MR3556863 |
| DOI:
|
10.1007/s10587-016-0288-4 |
| . |
| Date available:
|
2016-10-01T15:19:10Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145867 |
| . |
| Reference:
|
[1] Bapat, R. B., Kirkland, S. J., Pati, S.: The perturbed Laplacian matrix of a graph.Linear Multilinear Algebra 49 (2001), 219-242. Zbl 0984.05056, MR 1888190, 10.1080/03081080108818697 |
| Reference:
|
[2] Butler, S.: Eigenvalues and Structures of Graphs.PhD Disssertation, University of California, San Diego (2008). MR 2711548 |
| Reference:
|
[3] Cavers, M.: The Normalized Laplacian Matrix and General Randic Index of Graphs.PhD Dissertation, University of Regina, 2010. MR 3078627 |
| Reference:
|
[4] Chung, F. R. K.: Spectral Graph Theory.Regional Conference Series in Mathematics 92 American Mathematical Society, Providence (1997). Zbl 0867.05046, MR 1421568 |
| Reference:
|
[5] Chung, F. R. K., Richardson, R. M.: Weighted Laplacians and the sigma function of a graph.Proc. of an AMS-IMS-SIAM joint summer research conf. on Quantum Graphs and Their Applications, Snowbird, 2005 B. Berkolaiko et al. Contemporary Mathematics 415 (2006), 93-107. Zbl 1106.05058, MR 2277610, 10.1090/conm/415/07862 |
| Reference:
|
[6] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321, 10.21136/CMJ.1975.101357 |
| Reference:
|
[7] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| Reference:
|
[8] Kirkland, S., Fallat, S.: Perron components and algebraic connectivity for weighted graphs.Linear Multilinear Algebra 44 (1998), 131-148. Zbl 0926.05026, MR 1674228, 10.1080/03081089808818554 |
| Reference:
|
[9] Kirkland, S., Neumann, M., Shader, B. L.: Characteristic vertices of weighted trees via Perron values.Linear Multilinear Algebra 40 (1996), 311-325. Zbl 0866.05041, MR 1384650, 10.1080/03081089608818448 |
| Reference:
|
[10] Li, H.-H., Li, J.-S., Fan, Y.-Z.: The effect on the second smallest eigenvalue of the normalized Laplacian of a graph by grafting edges.Linear Multilinear Algebra 56 (2008), 627-638. Zbl 1159.05317, MR 2457689, 10.1080/03081080601143090 |
| Reference:
|
[11] Merris, R.: Characteristic vertices of trees.22 (1987), Linear Multilinear Algebra 115-131. Zbl 0636.05021, MR 0936566, 10.1080/03081088708817827 |
| Reference:
|
[12] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory.Linear Algebra Appl. 439 (2013), 818-821. Zbl 1282.05145, MR 3061737 |
| . |
