Graphs with Small Bandwidth and Cutwidth

F. R.K. Chung; P. D. Seymour

doi:10.1016/S0167-5060(08)70571-5

Graphs with Small Bandwidth and Cutwidth

F. R.K. Chung, P. D. Seymour

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 + c₁ diameter (G') for any connected subgraph G' of G, and that G does not contain any refinement of the complete binary tree of c₂ 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.

Original language	English (US)
Pages (from-to)	113-119
Number of pages	7
Journal	Annals of Discrete Mathematics
Volume	43
Issue number	C
DOIs	https://doi.org/10.1016/S0167-5060(08)70571-5
State	Published - Jan 1 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0167-5060(08)70571-5

Cite this

@article{c367c809ccc74bdba28f55664ccb361e,

title = "Graphs with Small Bandwidth and Cutwidth",

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.",

author = "Chung, {F. R.K.} and Seymour, {P. D.}",

year = "1989",

month = jan,

day = "1",

doi = "10.1016/S0167-5060(08)70571-5",

language = "English (US)",

volume = "43",

pages = "113--119",

journal = "Annals of Discrete Mathematics",

issn = "0167-5060",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - Graphs with Small Bandwidth and Cutwidth

AU - Chung, F. R.K.

AU - Seymour, P. D.

PY - 1989/1/1

Y1 - 1989/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77957044541&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957044541&partnerID=8YFLogxK

U2 - 10.1016/S0167-5060(08)70571-5

DO - 10.1016/S0167-5060(08)70571-5

M3 - Article

AN - SCOPUS:77957044541

SN - 0167-5060

VL - 43

SP - 113

EP - 119

JO - Annals of Discrete Mathematics

JF - Annals of Discrete Mathematics

IS - C

ER -

Graphs with Small Bandwidth and Cutwidth

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this