The Bandwidth of Caterpillars with Hairs of Length 1 and 2
Susan F. Assmann, G. W. Peck, Maciej M. Sysło, Jerzy Żak · SIAM Journal on Algebraic and Discrete Methods · 1981
In this paper we show that the bandwidth of any caterpillar with hairs of length 1 and 2 is given by the maximum over all subcaterpillars of $\lceil (n - 1)/d \rceil$, where n is the number of vertices and d is the diameter of the subcaterpillar. We also give an $n\log n$ algorithm which produces a bandwidth labelling of such a caterpillar.