Geodesic
A Fiedler-like theory for the perturbed Laplacian
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 717-735 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0288-4
Classification : 05C22, 05C50, 15B57
Keywords: perturbed Laplacian matrix; Fiedler vector; algebraic connectivity; graph partitioning 
@article{10_1007_s10587_016_0288_4,
     author = {Rocha, Israel and Trevisan, Vilmar},
     title = {A {Fiedler-like} theory for the perturbed {Laplacian}},
     journal = {Czechoslovak Mathematical Journal},
     pages = {717--735},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0288-4},
     mrnumber = {3556863},
     zbl = {06644029},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0288-4/}
}
TY  - JOUR
AU  - Rocha, Israel
AU  - Trevisan, Vilmar
TI  - A Fiedler-like theory for the perturbed Laplacian
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 717
EP  - 735
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0288-4/
DO  - 10.1007/s10587-016-0288-4
LA  - en
ID  - 10_1007_s10587_016_0288_4
ER  - 
%0 Journal Article
%A Rocha, Israel
%A Trevisan, Vilmar
%T A Fiedler-like theory for the perturbed Laplacian
%J Czechoslovak Mathematical Journal
%D 2016
%P 717-735
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0288-4/
%R 10.1007/s10587-016-0288-4
%G en
%F 10_1007_s10587_016_0288_4
Rocha, Israel; Trevisan, Vilmar. A Fiedler-like theory for the perturbed Laplacian. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 717-735. doi: 10.1007/s10587-016-0288-4

[1] Bapat, R. B., Kirkland, S. J., Pati, S.: The perturbed Laplacian matrix of a graph. Linear Multilinear Algebra 49 (2001), 219-242. | DOI | MR | Zbl

[2] Butler, S.: Eigenvalues and Structures of Graphs. PhD Disssertation, University of California, San Diego (2008). | MR

[3] Cavers, M.: The Normalized Laplacian Matrix and General Randic Index of Graphs. PhD Dissertation, University of Regina, 2010. | MR

[4] Chung, F. R. K.: Spectral Graph Theory. Regional Conference Series in Mathematics 92 American Mathematical Society, Providence (1997). | MR | Zbl

[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. | DOI | MR | Zbl

[6] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. | DOI | MR | Zbl

[7] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | DOI | MR | Zbl

[8] Kirkland, S., Fallat, S.: Perron components and algebraic connectivity for weighted graphs. Linear Multilinear Algebra 44 (1998), 131-148. | DOI | MR | Zbl

[9] Kirkland, S., Neumann, M., Shader, B. L.: Characteristic vertices of weighted trees via Perron values. Linear Multilinear Algebra 40 (1996), 311-325. | DOI | MR | Zbl

[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. | DOI | MR | Zbl

[11] Merris, R.: Characteristic vertices of trees. 22 (1987), Linear Multilinear Algebra 115-131. | DOI | MR | Zbl

[12] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439 (2013), 818-821. | MR | Zbl

Cité par Sources :