On the ordering of trees by the Laplacian coefficients

AbstractWe generalize the results from [X.-D. Zhang, X.-P. Lv, Y.-H. Chen, Ordering trees by the Laplacian coefficients, Linear Algebra Appl. (2009), doi:10.1016/j.laa.2009.04.018] on the partial ordering of trees with given diameter. For two n-vertex trees T1 and T2, if ck(T1)⩽ck(T2) holds for all Laplacian coefficients ck,k=0,1,…,n, we say that T1 is dominated by T2 and write T1⪯cT2. We proved that among n vertex trees with fixed diameter d, the caterpillar Cn,d has minimal Laplacian coefficients ck,k=0,1,…,n. The number of incomparable pairs of trees on ⩽18 vertices is presented, as well as infinite families of examples for two other partial orderings of trees, recently proposed by Mohar. For every integer n, we construct a chain {Ti}i=0m of n-vertex trees of length n24, such that T0≅Sn,Tm≅Pn and Ti⪯cTi+1 for all i=0,1,…,m-1. In addition, the characterization of the partial ordering of starlike trees is established by the majorization inequalities of the pendent path lengths. We determine the relations among the extremal trees with fixed maximum degree, and with perfect matching and further support the Laplacian coefficients as a measure of branching