%0 Journal Article
%T Bandwidth and density for block graphs
%A Le Tu Quoc Hung
%A Maciej M. Syslo
%A Margaret L. Weaver
%A Douglas B. West
%J Mathematics
%D 1998
%I arXiv
%X The bandwidth of a graph G is the minimum of the maximum difference between adjacent labels when the vertices have distinct integer labels. We provide a polynomial algorithm to produce an optimal bandwidth labeling for graphs in a special class of block graphs (graphs in which every block is a clique), namely those where deleting the vertices of degree one produces a path of cliques. The result is best possible in various ways. Furthermore, for two classes of graphs that are ``almost'' caterpillars, the bandwidth problem is NP-complete.
%U http://arxiv.org/abs/math/9802025v1