𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computing the Bandwidth of Interval Graphs

✍ Scribed by Kleitman, Daniel J.; Vohra, Rakesh V.

Book ID
118198452
Publisher
Society for Industrial and Applied Mathematics
Year
1990
Tongue
English
Weight
414 KB
Volume
3
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Interval degree and bandwidth of a graph
Interval degree and bandwidth of a graph
✍ Fedor V Fomin; Petr A Golovach πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 395 KB

The interval degree id(G) of a graph G is deΓΏned to be the smallest max-degree of any interval supergraphs of G. One of the reasons for our interest in this parameter is that the bandwidth of a graph is always between id(G)=2 and id(G). We prove also that for any graph G the interval degree of G is