Abstract
We give counter-examples to the following conjecture which arose in the study of small bandwidth graphs. “For a graph G, suppose that |V(G')|≤ 1 + c1 diameter (G') for any connected subgraph G' of G, and that G does not contain any refinement of the complete binary tree of c2 levels. Is it true that the bandwidth of G can be bounded above by a constant c depending only on c1and c2?” 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.
Original language | English (US) |
---|---|
Pages (from-to) | 113-119 |
Number of pages | 7 |
Journal | Annals of Discrete Mathematics |
Volume | 43 |
Issue number | C |
DOIs | |
State | Published - Jan 1 1989 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics