关于树的代数连通度的Fiedler不等式的新证明

设T为含n个顶点的树，L(T)为其Laplace矩阵，L(T)的次小特征值α(T)称为T的代数连通度，Fiedlcr给出如下关于α(T)的界的经典结论α(Pn)≤α(T)≤α(Sn)，其中Pn，Sn分别为含有n个顶点的路和星．Merris和Mass独立地证明了：α(T)=α(Sn)当且仅当T=Sn．通过重新组合由Fiedler向量所赋予的顶点的值，本给出上述不等式的新证明，并证明了：α(T)=α(Pn)当且仅当T=Pn。

A New Proof of Fiedler′s Inequality on the Algebraic Connectivity of Trees

Let T be a tree on n vertices and let L(T) be the Laplacian matrix of T. The second smallest eigenvalue u(T) of L(T) is called the algebraic connectivity of T. A classical result on the bounds for a(T) is given by Fielder [1] as follows:where Pn and Sn denote respectively the path and the star on n vertices. In [9] and [8], Merris and Mass proved independently that a(T)=a(Sn) if and only if T=Sn In this paper, by recombining the valuation of the vertices which are given by a Fiedler vector (the eigenvector of L(T) corresponding to a(T)), we provide a new proof of above inequality, and also show that a(T) = a(Pn) if and only if T =Pn.