Extremal algebraic connectivities of certain caterpillar classes and symmetric caterpillars

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.