Algebraic connectivity of trees. (English) Zbl 0681.05022

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.


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


Zbl 0437.15004
Full Text: EuDML


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.