✦ LIBER ✦

Interval graphs and interval orders

✍ Scribed by Peter C. Fishburn

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 949 KB
Volume: 55
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90042-1

No coin nor oath required. For personal study only.

✦ Synopsis

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 unique agreeing interval orders are noted, and relationships between interval graphs and interval orders that concern the number of lengths required for interval representations and bounds on lengths of representing intervals are discussed.

Two invariants of the family of interval orders that agree with an interval graph are established, namely magnitude, which affects end-point placements, and the property of having the lengths of all representing intervals between specified bounds. Extremization problems for interval graphs and interval orders are also considered.

📜 SIMILAR VOLUMES

Comparability graphs with constraint, pa

Comparability graphs with constraint, partial semi-orders and interval orders

✍ Claude Flament 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 580 KB

A symmetric, anfireflexive relation S is a comparability graph ff one can assign a transitive orientation to the edges: we obtain a partial order. We say that S is a comparability graph with constraint C, a subrelation of S, if S has a transitive orientation including C. A characterization is given

Interval representations for interval or

Interval representations for interval orders and semiorders

✍ Peter C. Fishburn 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 835 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 seatching

✍ Lefteris M. Kirousis; Christos H. Papadimitriou 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 247 KB

Interval matroids and graphs

✍ F. Jaeger 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 519 KB

A base of the cycle space of a binary matroid M on E is said to be convex if its elements can be totally ordered in such a way that for every e E E tk set of elements of the base containing e is an interval. \'Ure show that a binary matroid is cographic iff it has a convex base of cycles; equivalent

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