Abstract

A caterpillar is a tree in which the removal of all pendant vertices makes it a path. Let d ≥ 3 and n > 2 (d - 1) be given. Let p = [p1, p2, ..., pd - 1] with p1 ≥ 1, p2 ≥ 1, ..., pd - 1 ≥ 1. Let C (p) be the caterpillar obtained from the stars Sp1, Sp2, ..., Spd - 1 and the path Pd - 1 by identifying the root of Spi with the i-vertex of Pd - 1. LetC = fenced(C (p) : p1 + p2 + ⋯ + pd - 1 = n - d + 1) .We prove that the algebraic connectivity of C (p) ∈ C is bounded above byfrac(1, 2) fenced(4 + σ - sqrt(σ2 + 4 σ + 8)), σ = 2 cos frac((d - 2) π, d - 1) .Moreover, we prove that if d is even then C (over(p, ∼)),over(p, ∼) = fenced(1, ..., 1, over(p, ∼)frac(d, 2), 1, ..., 1), over(p, ∼)frac(d, 2) = n - 2 d + 3,is the unique caterpillar in C attaining the upper bound and that if d is odd then the upper bound cannot be achieved. Finally, for 1 ≤ k ≤ ⌊ frac(d - 1, 2) ⌋, we give a total ordering by algebraic connectivity onCk = fenced(C fenced(1, ..., 1, pk, 1, ..., 1, pd - k, 1, ..., 1) ∈ C : pk ≤ pd - k) . © 2009 Elsevier Inc. All rights reserved.