The Bandwidth of Caterpillars with Hairs of Length 1 and 2

Abstract

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.