Abstract

A caterpillar is a tree in which the removal of all pendant vertices makes it a path. Let d ≥ 3 and n ≥ 6 be given. Let Pd - 1 be the path on d - 1 vertices and K1, p be the star of p + 1 vertices. Let p = [p1, p2, ..., pd - 1] such that ∀ i, 1 ≤ i ≤ d - 1, pi. Let C (p) be the caterpillar obtained from d - 1 stars K1, pi and the path Pd - 1 by identifying the root of K1, pi with the i-vertex of Pd - 1. For a given n ≥ 2 (d - 1), let C = {C (p) : ∑i = 1, d - 1 pi = n - d + 1}. In this work, we give the caterpillar in C maximizing the algebraic connectivity. © 2009 Elsevier B.V. All rights reserved.