Graphs with small bandwidth and cutwidth

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

doi:10.1016/0012-365X(89)90083-6

Graphs with small bandwidth and cutwidth

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

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

44 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 {curly logical or}V(G'){curly logical or}≤1+c₁{dot operator} 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	Discrete Mathematics
Volume	75
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(89)90083-6
State	Published - May 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(89)90083-6

Cite this

@article{aac547cb85d743799a1407e2bd50358a,

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 {curly logical or}V(G'){curly logical or}≤1+c1{dot operator} 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 c1 and 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 = may,

doi = "10.1016/0012-365X(89)90083-6",

language = "English (US)",

volume = "75",

pages = "113--119",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Graphs with small bandwidth and cutwidth

AU - Chung, F. R.K.

AU - Seymour, P. D.

PY - 1989/5

Y1 - 1989/5

N2 - We give counter-examples to the following conjecture which arose in the study of small bandwidth graphs. "For a graph G, suppose that {curly logical or}V(G'){curly logical or}≤1+c1{dot operator} 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 c1 and 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 {curly logical or}V(G'){curly logical or}≤1+c1{dot operator} 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 c1 and 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=38249021538&partnerID=8YFLogxK

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

U2 - 10.1016/0012-365X(89)90083-6

DO - 10.1016/0012-365X(89)90083-6

M3 - Article

AN - SCOPUS:38249021538

SN - 0012-365X

VL - 75

SP - 113

EP - 119

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Graphs with small bandwidth and cutwidth

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this