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

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

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