Algebraic connectivity of trees

From MaRDI portal





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 \textit{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.




Cited in
(52)








This page was built for publication: Algebraic connectivity of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729804)