##
**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.

### Keywords:

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

Zbl 0437.15004
PDF
BibTeX
XML
Cite

\textit{R. Grone} and \textit{R. Merris}, Czech. Math. J. 37(112), 660--670 (1987; Zbl 0681.05022)

Full Text:
EuDML

### 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 |

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.