On the algebraic connectivity of some caterpillars: A sharp upper bound and a total ordering

A caterpillar is a tree in which the removal of all pendant vertices makes it a path. Let d⩾3d⩾3 and n>2(d-1)n>2(d-1) be given. Let p=[p1,p2,…,pd-1]p=[p1,p2,…,pd-1] with p1⩾1,p2⩾1,…,pd-1⩾1p1⩾1,p2⩾1,…,pd-1⩾1. Let C(p)C(p) be the caterpillar obtained from the stars Sp1,Sp2,…,Spd-1Sp1,Sp2,…,Spd-1 and the path Pd-1Pd-1 by identifying the root of SpiSpi with the ii-vertex of Pd-1Pd-1. LetC={C(p):p1+p2+⋯+pd-1=n-d+1}.C=C(p):p1+p2+⋯+pd-1=n-d+1.We prove that the algebraic connectivity of C(p)∈CC(p)∈C is bounded above by124+σ-σ2+4σ+8,σ=2cos(d-2)πd-1.Moreover, we prove that if dd is even then C(p∼),p∼=1,…,1,p∼d2,1,…,1,p∼d2=n-2d+3,is the unique caterpillar in CC attaining the upper bound and that if dd is odd then the upper bound cannot be achieved. Finally, for 1⩽k⩽⌊d-12⌋, we give a total ordering by algebraic connectivity onCk={C(1,…,1,pk,1,…,1,pd-k,1,…,1)∈C:pk⩽pd-k}.Ck=C1,…,1,pk,1,…,1,pd-k,1,…,1∈C:pk⩽pd-k.