1998/02/05 by Le Tu Quoc Hung, Maciej M. Syslo, Margaret L. Weaver +1
Mathematics · #math.CO #msc:05C78
published as Discrete Mathematics 189(1998), 163-176 · 14 pages, 9 included figures. Note: figures did not appear in original upload; resubmission corrects this
arxiv created 1998/02/05 · arxiv updated 2009/11/30
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.