Graphs with small bandwidth and cutwidth

✍ Scribed by F.R.K. Chung; P.D. Seymour

• Book ID: 103059495
• Publisher: Elsevier Science
• Year: 1989
• Tongue: English
• Weight: 442 KB
• Volume: 75
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(89)90083-6

✦ Synopsis

We give counter-examples to the following conjecture which arose in the study of small bandwidth graphs.

"For a graph G, suppose that IV(G')( < 1 + ci . diameter (G') for any connected subgraph G' of G, and that G does not contain any refinement of the complete binary tree of cz levels. Is it true that the bandwidth of G can be bounded above by a constant c depending only on c, and c,?"

On the other hand, we show that if the maximum degree of G is bounded and G does not contain any refinement of a complete binary tree of a specified size, then the cutwidth and the topological bandwidth of G are also bounded.

where D(G) is the diameter of G, that is, the maximum distance among all pairs