✦ LIBER ✦

On probe interval graphs

✍ Scribed by F.R. McMorris; Chi Wang; Peisen Zhang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 723 KB
Volume: 88
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(98)00077-8

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Recognizing edge clique graphs among int

Recognizing edge clique graphs among interval graphs and probe interval graphs

✍ Jing Kong; Yaokun Wu 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 250 KB

The edge clique graph of a graph H is the one having the edge set of H as vertex set, two vertices being adjacent if and only if the corresponding edges belong to a common complete subgraph of H . We characterize the graph classes {edge clique graphs} ∩ {interval graphs} as well as {edge clique grap

Tree Spanners for Bipartite Graphs and P

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

✍ Andreas Brandstadt; Feodor F. Dragan; Hoang-Oanh Le; Van Bang Le; Ryuhei Uehara 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 336 KB

Open-interval graphs versus closed-inter

Open-interval graphs versus closed-interval graphs

✍ P. Frankl; H. Maehara 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 218 KB

A graph G = (V, E) is said to be represented by a family F of nonempty sets if there is a bijection f:V--\*F such that uv ~E if and only iff(u)Nf(v)q=~. It is proved that if G is a countable graph then G can be represented by open intervals on the real line if and only if G can be represented by clo

Interval graphs and interval orders

✍ Peter C. Fishburn 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 949 KB

This paper explores the intimate connection between finite interval graphs and interval orders. Special attention is given to the family of interval orders that agree with, or provide representations of, an interval graph. Two characterizations (one by P. Hanlon) of interval graphs with essentially

Random interval graphs

✍ Nicholas Pippenger 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 1 views

We consider models for random interval graphs that are based on stochastic service systems, with vertices corresponding to customers and edges corresponding to pairs of customers that are in the system simultaneously. The number N of vertices in a connected component thus corresponds to the number o

Extremal interval graphs

✍ Jürgen Eckhoff 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB

## Abstract An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for t