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

摘要

设T为含n个顶点的树,L(T)为其Laplace矩阵. L(T)的次小特征值α(T)称为T的代数连通度. Fiedler给出如下关于α(T)的界的经典结论.α(Pn)≤α(T)≤α(Sn),其中Pn, Sn分别为含有n个顶点的路和星. Merris和Mass独立地证明了:α(T)=α(Sn)当且仅当T=Sn. 通过重新组合由Fiedler向量所赋予的顶点的值,本文给出上述不等式的新证明,并证明了:α(T)=α(Pn)当且仅当T=Pn.%Let T be a tree on n vertices and let L(T) be the Laplacian matrix of T. The second smallest eigenvalue α(T) of L(T) is called the algebraic connectivity of T. A classical result on the bounds for α(T) is given by Fielder [1] as follows:α(Pn)≤α(T)≤α(Sn),where Pn and Sn denote respectively the path and the star on n vertices. In [9] and [8], Merris and Mass proved independently that α(T)=α(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 α(T)), we provide a new proof of above inequality, and also show that α(T)=α(Pn) if and only if T=Pn.