✦ LIBER ✦

Interval degree and bandwidth of a graph

✍ Scribed by Fedor V Fomin; Petr A Golovach

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 395 KB
Volume: 129
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(02)00574-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 at least the pathwidth of G 2 . We show that if G is an AT-free claw-free graph, then the interval degree of G is equal to the clique number of G 2 minus one. Finally, we show that there is a polynomial time algorithm for computing the interval degree of AT-free claw-free graphs.

📜 SIMILAR VOLUMES

On the bandwidth of a Hamming graph

✍ L.H. Harper 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 198 KB

The bandwidth of the Hamming graph (the product, (Kn) d , of complete graphs) has been an open question for many years. Recently Berger-Wolf and Rheingold [1] pointed out that the bandwidth of a numbering of the Hamming graph may be interpreted as a measure of the e ects of noise in the multi-channe

Graph Searching, Elimination Trees, and

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

✍ Fedor V. Fomin; Pinar Heggernes; Jan Arne Telle 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 161 KB

A matrix characterization of interval an

A matrix characterization of interval and proper interval graphs

✍ George B. Mertzios 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 266 KB

In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of this matrix representation every such graph is ass

Ramsey Theory and Bandwidth of Graphs

✍ Zoltán Füredi; Douglas B. West 📂 Article 📅 2001 🏛 Springer Japan 🌐 English ⚖ 114 KB

A relationship between triangulated grap

A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs

✍ Dale J. Skrien 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

## Abstract Given a set __F__ of digraphs, we say a graph __G__ is a __F__‐__graph__ (resp., __F__\*‐__graph__) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in __F__. It is proved that all the classes of graphs mentioned in

Innate degree of freedom of a graph

✍ D. J. Klein; M. Randić 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 433 KB

For a Kekul6 structure we consider the smallest number of placements of double bonds such that the full Kekul6 structure on the given parent graph is fully determined. These numbers for each Kekul6 structure of the parent graph sum to a novel structural invariant F, called the degree of freedom of t