On algebraic connectivity and spectral integral variations of graphs

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.