✦ LIBER ✦

The bandwidth problem and operations on graphs

✍ Scribed by J Chvatalova; J Opatrny

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 479 KB
Volume: 61
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90086-5

No coin nor oath required. For personal study only.

✦ Synopsis

For a given graph G and vertices u, v in G let ,,,~ ~(.,~) G(-,,o) G~, o) denote the graph Gm ~ Va , ~s :, obtained from G by merging vertices u, v, adding edge (u, v), subdividing edge (u, v), contracting edge (u, v) of G, respectively. We give upper and lower bounds for the bandwidth of ~'~ ~(~'~) G~ ''°) in terms of the bandwidth of G. Also given is an upper bound on the Gm , VS ' bandwidth of G~ ~'U) in terms of the bandwidth of G and the distance of u from v in G. It is shown that none of these bounds can be improved.

📜 SIMILAR VOLUMES

Undecidability of the bandwidth problem

Undecidability of the bandwidth problem on linear graph languages

✍ Egon Wanke; Manfred Wiegers 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 682 KB

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

Minimum bandwidth problem for embedding

Minimum bandwidth problem for embedding graphs in cycles

✍ Lin, Yixun 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 2 views

For the bandwidth B(G) and the cyclic bandwidth B c (G) of a graph G, it is known that 1 2 B(G) °Bc (G) °B(G). In this paper, the criterion conditions for two extreme cases B c (G) Å B(G) and B c (G) Å 1 2 B(G) are studied. From this, some exact values of B c (G) for special graphs can be obtained.

A survey of solved problems and applicat

A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs

✍ Lai, Yung-Ling; Williams, Kenneth 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB 👁 1 views

This article provides a survey of results on the exact bandwidth, edgesum, and profile of graphs. A bibliography of work in these areas is provided. The emphasis is on composite graphs. This may be regarded as an update of the original survey of solved bandwidth problems by Chinn, Chvátalová, Dewdne

On bandwidth and edgesum for the composi

On bandwidth and edgesum for the composition of two graphs

✍ Jiuqiang Liu; Kenneth Williams 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 469 KB

The composition of two graphs G and H, written G[H], is the graph with vertex set V(G) x V(H) and with (u,, uI) adjacent to (ul, ul) if either u1 is adjacent to IQ in G or u1 = u2 and ul is adjacent to v2 in H. In this paper, we investigate the bandwidth problem for the composition of two graphs and

On the size of graphs of a given bandwid

On the size of graphs of a given bandwidth

✍ Ronald D. Dutton; Robert C. Brigham 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 489 KB

The relationship between the graphical invariants bandwidth and number of edges is considered. Bounds, some sharp and others improvements of known results, are given for the nznber of edges of graphs having a given bandwidth. An important invariant of undirected graphs having no loops or multiple e