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 of d - 1 vertices and Sp be the star of p + 1 vertices. Let p = [p1, p2,..., pd-1] such that 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. Let n > 2 (d - 1) be given. Let C ={C(p):p1 +p2 +...+pd-1 =n-d+1} and S ={C(p)∈C:pj =pd-j, j =1,2,···,⌊d-1 2⌋}. In this paper, the caterpillars in C and in S having the maximum and the minimum algebraic connectivity are found. Moreover, the algebraic connectivity of a caterpillar in S as the smallest eigenvalue of a 2 × 2 - block tridiagonal matrix of order 2s × 2s if d = 2s + 1 or d = 2s + 2 is characterized.