A Fiedler-like theory for the perturbed Laplacian

Czechoslovak Mathematical Journal

Israel Rocha¹ 

[1] Vilmar Trevisan, Instituto de Matemática, Universidade Federal do Rio Grande do Sul, Avenida Bento Gonçalves, 9500, Porto Alegre 91501-970, Rio Grande do Sul, Brazil

关键词: perturbed Laplacian matrix;    Fiedler vector;    algebraic connectivity;    graph partitioning;   

DOI  :  

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

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.

【 授权许可】

Unknown