Bandwidth of trees of diameter at most 4

Abstract For a graph G , let γ : V ( G ) → { 1 , … , | V ( G ) | } be a one-to-one function. The bandwidth of γ is the maximum of | γ ( u ) − γ ( v ) | over u v ∈ E ( G ) . The bandwidth of G , denoted b ( G ) , is the minimum bandwidth over all embeddings γ , b ( G ) = min γ { max { | γ ( u ) − γ ( v ) | : u v ∈ E ( G ) } } . In this paper, we show that the bandwidth computation problem for trees of diameter at most 4 can be solved in polynomial time. This naturally complements the result computing the bandwidth for 2-caterpillars.