A Fiedler-like theory for the perturbed Laplacian

Rocha, 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 -