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.