期刊
LINEAR ALGEBRA AND ITS APPLICATIONS
卷 397, 期 -, 页码 209-222出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2004.10.015
关键词
Laplacian matrix; Perron branch; algebraic connectivity; characteristic set; spectral integral variation
Let G be a simple connected graph and L(G) be the Laplacian matrix of G. Let a(G) be the second smallest eigenvalue of L(G). An eigenvector of L(G) corresponding to the eigenvalue a (G) is called a Fiedler vector of G. Let Y be a Fiedler vector of G. A characteristic vertex is a vertex u of G such that Y(u) = 0 and such that there is a vertex w adjacent to u satisfying Y(w) not equal 0. A characteristic edge is an edge {u, v} such that Y(u)Y(v) < 0. The characteristic set S is the collection of all characteristic vertices and characteristic edges of G with respect to Y. A Perron branch at S is a connected component of G \ S with the smallest eigenvalue of the corresponding principal submatrix of L(G) less than or equal to a(G). Suppose that S contains vertices only and that there are t Perron branches of G at S. We show that in this case the multiplicity of a(G) is at least t - 1 and t - 1 of the linearly independent Fiedler vectors can be constructed from the positive eigenvectors of the Perron branches. We also show that the condition for each Fiedler vector Y, the characteristic set contains vertices only is equivalent to the multiplicity of a (G) is exactly t - 1. We characterize the graphs in which spectral integral variation occurs in one place by adding an edge where the changed eigenvalue is the algebraic connectivity. (C) 2004 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据