# A Fiedler-like theory for the perturbed Laplacian

Czechoslovak Mathematical Journal (2016)

- Volume: 66, Issue: 3, page 717-735
- ISSN: 0011-4642

## Access Full Article

top## Abstract

top## How to cite

topRocha, Israel, and Trevisan, Vilmar. "A Fiedler-like theory for the perturbed Laplacian." Czechoslovak Mathematical Journal 66.3 (2016): 717-735. <http://eudml.org/doc/286788>.

@article{Rocha2016,

abstract = {The perturbed Laplacian matrix of a graph $G$ is defined as $L^\{\hspace\{-8.33328pt\}D\}=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.},

author = {Rocha, Israel, Trevisan, Vilmar},

journal = {Czechoslovak Mathematical Journal},

keywords = {perturbed Laplacian matrix; Fiedler vector; algebraic connectivity; graph partitioning},

language = {eng},

number = {3},

pages = {717-735},

publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},

title = {A Fiedler-like theory for the perturbed Laplacian},

url = {http://eudml.org/doc/286788},

volume = {66},

year = {2016},

}

TY - JOUR

AU - Rocha, Israel

AU - Trevisan, Vilmar

TI - A Fiedler-like theory for the perturbed Laplacian

JO - Czechoslovak Mathematical Journal

PY - 2016

PB - Institute of Mathematics, Academy of Sciences of the Czech Republic

VL - 66

IS - 3

SP - 717

EP - 735

AB - The perturbed Laplacian matrix of a graph $G$ is defined as $L^{\hspace{-8.33328pt}D}=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.

LA - eng

KW - perturbed Laplacian matrix; Fiedler vector; algebraic connectivity; graph partitioning

UR - http://eudml.org/doc/286788

ER -

## References

top- Bapat, R. B., Kirkland, S. J., Pati, S., 10.1080/03081080108818697, Linear Multilinear Algebra 49 (2001), 219-242. (2001) Zbl0984.05056MR1888190DOI10.1080/03081080108818697
- Butler, S., Eigenvalues and Structures of Graphs, PhD Disssertation, University of California, San Diego (2008). (2008) MR2711548
- Cavers, M., The Normalized Laplacian Matrix and General Randic Index of Graphs, PhD Dissertation, University of Regina, 2010. MR3078627
- Chung, F. R. K., Spectral Graph Theory, Regional Conference Series in Mathematics 92 American Mathematical Society, Providence (1997). (1997) Zbl0867.05046MR1421568
- Chung, F. R. K., Richardson, R. M., 10.1090/conm/415/07862, 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. (2006) Zbl1106.05058MR2277610DOI10.1090/conm/415/07862
- Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321
- Fiedler, M., Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007
- Kirkland, S., Fallat, S., 10.1080/03081089808818554, Linear Multilinear Algebra 44 (1998), 131-148. (1998) Zbl0926.05026MR1674228DOI10.1080/03081089808818554
- Kirkland, S., Neumann, M., Shader, B. L., 10.1080/03081089608818448, Linear Multilinear Algebra 40 (1996), 311-325. (1996) Zbl0866.05041MR1384650DOI10.1080/03081089608818448
- Li, H.-H., Li, J.-S., Fan, Y.-Z., 10.1080/03081080601143090, Linear Multilinear Algebra 56 (2008), 627-638. (2008) Zbl1159.05317MR2457689DOI10.1080/03081080601143090
- Merris, R., 10.1080/03081088708817827, 22 (1987), Linear Multilinear Algebra 115-131. (1987) Zbl0636.05021MR0936566DOI10.1080/03081088708817827
- Nikiforov, V., The influence of Miroslav Fiedler on spectral graph theory, Linear Algebra Appl. 439 (2013), 818-821. (2013) Zbl1282.05145MR3061737

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.