On the algebraic connectivity of some caterpillars: a sharp upper bound and a total ordering (Q1044553)

A caterpillar is a tree in which the removal of all pendant vertices turns it into a path. In this paper, the authors obtain the algebraic connectivity of some special types of caterpillars. Let \(d \geq 3\) and \(n > 2(d-1)\) be given. Let \(\mathbf p = [p_1 , p_2 , \dots, p_{d-1} ]\) with \(p_1\geq 1\), \(p_2\geq 1\), \dots, \(p_{d-1} \geq 1\). Let \(C(\mathbf p)\) be the caterpillar obtained from the stars \(S_{p_1} , S_{p_2}, \dots, S_{p_{d-1}}\) and the path \(p_{d-1}\) by identifying the root of \(S_{p_i}\) with the \(i\)-th vertex of \(p_{d-1}\). Let \(C = \{C(\mathbf p) : p_1 + p_2 + \dots + p_{d-1} = n - d + 1\}.\) The authors obtain some bounds for the algebraic connectivity of \(C(\mathbf p) \in C\). The results are quite interesting. Finding an explicit sharp bound for the algebraic connectivity of caterpillars in \(C\) when \(d\) is odd is stated to be an open problem.