Algebraic connectivity of trees. (English) Zbl 0681.05022

Grone, Robert; Merris, Russell

Czech. Math. J. 37(112), 660-670 (1987).

The Laplacian matrix of a tree T is \(L(T)=(a_{ij})\), where \(a_{ij}=\deg (v_ i)\) if \(i=j\), \(a_{ij}=-1\) if \(v_ i\) \(v_ j\) is an edge of T, and \(a_{ij}=0\) otherwise. L(T) is seen to be a positive semidefinite symmetric matrix whose second smallest eigenvalue a(T) satisfies \(0<a(T)\leq 1\), with \(a(T)=1\) if and only if T is the star \(K_{1,n-1}\). This eigenvalue has been called the algebraic connectivity of T. The set of eigenvectors of L(T) corresponding to a(T) may be interpreted as real-valued functions on V; these are known as characteristics valuations of T. The results obtained here all relate to trees for which there is a characteristic valuation f and vertex v such that \(f(v)=0\) (these have been called Type I trees). From work of M. Fiedler [ibid. 25, 619-633 (1975; Zbl 0437.15004)], it follows that in a Type I tree there is a unique vertex w, called the characteristic vertex of T, for which every characteristic valuation is zero. The multiplicity of a(T) and a method of pruning and grafting of branches of T are obtained from analysis of the branches at w. Obtaining the “orbit- partitioned” form of L(T) from the automorphism group of T, we can separate the spectrum into symmetric and alternating parts. For Type I trees, analysis of the branches at w allows determination of whether a(T) belongs to the symmetric or alternating part of the spectrum.

MSC:

05C05	Trees
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)

Keywords:

symmetric part; Laplacian matrix of a tree; eigenvalue; algebraic connectivity; trees; spectrum; alternating part

Citations:

Zbl 0437.15004

References:

[1]	D. Cvetkovič M. Doob, and H. Sachs: Spectra of Graphs. Academic Press, New York, 1979.
[2]	M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (98), 1973, 298-305. · Zbl 0265.05119
[3]	M. Fiedler: Eigenvalues of acyclic matrices. Czech. Math. J. 25 {100), 1975, 607-618.} · Zbl 0325.15014
[4]	M. Fiedler: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (100), 1975, 619-633. · Zbl 0437.15004
[5]	R. Merris: Characteristic vertices of trees. Linear/Multilinear Algebra, to appear. · Zbl 0636.05021
[6]	C Moler: MATLAB. CSUC CYBER, Los Angeles. · Zbl 1059.68162