A Fiedler-like theory for the perturbed Laplacian
详细信息 查看全文
- 作者：Israel Rocha ; Vilmar Trevisan
- 关键词：perturbed Laplacian matrix ; Fiedler vector ; algebraic connectivity ; graph partitioning
- 刊名：Czechoslovak Mathematical Journal
- 出版年：2016
- 出版时间：September 2016
- 年：2016
- 卷：66
- 期：3
- 页码：717-735
- 全文大小：204 KB
- 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Mathematics
Analysis
Convex and Discrete Geometry
Ordinary Differential Equations
Mathematical Modeling and IndustrialMathematics - 出版者：Springer Netherlands
- ISSN：1572-9141
- 卷排序：66
文摘
The perturbed Laplacian matrix of a graph G is defined as DL = 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.