𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Undecidability of the bandwidth problem on linear graph languages

✍ Scribed by Egon Wanke; Manfred Wiegers

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
682 KB
Volume
33
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The bandwidth problem and operations on
The bandwidth problem and operations on graphs
✍ J Chvatalova; J Opatrny πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 479 KB

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 ~'~ ~(~'~)

Some undecidable problems involving the
Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
✍ Stefan A. Burr πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 477 KB

Certain problems involving the coloring the edges or vertices of infinite graphs are shown to be undecidable. In particular, let G and H be finite 3-connected graphs, or triangles. Then a doubly-periodic infinite graph F is constructed such that the following problem is undecidable: For a coloring o

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