Bandwidth and density for block graphs
| dc.creator | Hung, Le Tu Quoc | |
| dc.creator | Syslo, Maciej M. | |
| dc.creator | Weaver, Margaret L. | |
| dc.creator | West, Douglas B. | |
| dc.date | 1998-02-05 | |
| dc.date.accessioned | 2026-07-07T05:23:46Z | |
| dc.date.available | 2026-07-07T05:23:46Z | |
| dc.description | 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. | |
| dc.description | 14 pages, 9 included figures. Note: figures did not appear in original upload; resubmission corrects this | |
| dc.identifier | https://arxiv.org/abs/math/9802025 | |
| dc.identifier | http://arxiv.org/abs/math/9802025 | |
| dc.identifier | Discrete Mathematics 189(1998), 163-176 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76575 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C78 | |
| dc.title | Bandwidth and density for block graphs | |
| dc.type | text |