✦ LIBER ✦

A new characterization of proper interval graphs

✍ Scribed by Zygmunt Jackowski

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 379 KB
Volume: 105
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90135-3

No coin nor oath required. For personal study only.

✦ Synopsis

One of the first characterizations of interval graphs, given by Lekkerkerker and Boland (1962), uses the concept of an asteroidal triple. In this paper we give a similar characterization on the proper interval graphs using the akin concept of an astral triple.

📜 SIMILAR VOLUMES

Metric characterizations of proper inter

Metric characterizations of proper interval graphs and tree-clique graphs

✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

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

The asymptotic probability that a random

The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph

✍ Joel E. Cohen 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 431 KB

Interval digraphs: An analogue of interv

Interval digraphs: An analogue of interval graphs

✍ S. Das; M. Sen; A. B. Roy; D. B. West 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 728 KB

Intersection digraphs analogous to undirected intersection graphs are introduced. Each vertex is assigned an ordered pair of sets, with a directed edge uu in the intersection digraph when the "source set" of u intersects the "terminal set" of u. Every n-vertex digraph is an intersection digraph of o

A new characterization of median graphs

✍ Abdelhafid Berrachedi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 171 KB

A graph is Hilbertian if for any three vertices u, v and w, the interval I(u, u) contains a unique nearest vertex p from w. We show that a graph is median if and only if it is Hilbertian.

A new interval-based method to character

A new interval-based method to characterize estimability

✍ O. Reynet; L. Jaulin 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 1 views

## Abstract Estimability is a property that states the accuracy of the parameter estimation in the case of experimental data. This paper defines a new method based on interval analysis and set inversion to characterize estimability in the case of a bounded additive noise. To illustrate this new met