𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Cubicity of Interval Graphs

✍ Scribed by L. Sunil Chandran; Mathew C. Francis; Naveen Sivadasan

Publisher
Springer Japan
Year
2009
Tongue
English
Weight
168 KB
Volume
25
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Cubicity of interval graphs and the claw
Cubicity of interval graphs and the claw number
✍ Abhijin Adiga; L. Sunil Chandran πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 119 KB πŸ‘ 1 views

Let G(V , E) be a simple, undirected graph where V is the set of vertices and E is the set of edges. A b-dimensional cube is a Cartesian product I 1 Γ—I 2 Γ—β€’ β€’ β€’Γ—I b , where each I i is a closed interval of unit length on the real line. The cubicity of G, denoted by cub(G), is the minimum positive in

On probe interval graphs
On probe interval graphs
✍ F.R. McMorris; Chi Wang; Peisen Zhang πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 723 KB

Probe interval graphs have been introduced in the physical mapping and sequencing of DNA as a generalization of interval graphs. We prove that probe interval graphs are weakly triangulated, and hence are perfect, and characterize probe interval graphs by consecutive orders of their intrinsic cliques

On the interval number of special graphs
On the interval number of special graphs
✍ JΓ³zsef Balogh; Pascal Ochem; AndrΓ‘s PluhΓ‘r πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 116 KB πŸ‘ 1 views

## Abstract The interval number of a graph __G__ is the least natural number __t__ such that __G__ is the intersection graph of sets, each of which is the union of at most __t__ intervals, denoted by __i__(__G__). Griggs and West showed that $i(G)\le \lceil {1\over 2} (d+1)\rceil $. We describe the

On the homogeneous representation of int
On the homogeneous representation of interval graphs
✍ Stephan Olariu πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 705 KB

## Abstract An interval graph __G__ is homogeneously representable if for every vertex __v__ of __G__ there exists an interval representation of __G__ with __v__ corresponding to an end interval. We show that the homogeneous representation of interval graphs is rooted in a deeper property of a clas