✦ LIBER ✦

The total interval number of a graph, I: Fundamental classes

✍ Scribed by Thomas M. Kratzke; Douglas B. West

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 906 KB
Volume: 118
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90057-z

No coin nor oath required. For personal study only.

✦ Synopsis

Kratzke, T.M. and D.B. West, The total interval number of a graph, I: Fundamental classes, Discrete Mathematics 118 (1993) 145-156. A multiple-interval representation of a simple graph G assigns each vertex a union of disjoint real intervals, such that vertices are adjacent if and only if their assigned sets intersect. The total interual number I(G) is the minimum of the total number of intervals used in any such representation of G. We obtain the maximum value of I(G) for n-vertex graphs ([(n' + 1)/41), n-vertex outerplanar graphs ( L3n/2 -I]). and m-edge connected graphs ( L(5m + 2)/4 1).

representation of G. Let #f(v) be the minimum number of intervals whose union is f(u); note that these intervals are disjoint. If #f(o) = k, we say that f(u) consists of k intervals or that u is assigned k intervals.

📜 SIMILAR VOLUMES

The total interval number of a tree and

The total interval number of a tree and the Hamiltonian completion number of its line graph

✍ Arundhati Raychaudhuri 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 672 KB

On the Interval Number of a Triangulated

On the Interval Number of a Triangulated Graph

✍ Thomas Andreae 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 414 KB 👁 2 views

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices u and w of G are adjacent if and only if some interval for u intersect

On the interval number of a chordal grap

On the interval number of a chordal graph

✍ Edward R. Scheinerman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB 👁 2 views

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum

A note on the interval number of a graph

✍ Paul Erdös; Douglas B. West 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 353 KB

Three results on the interval number of a graph on n vertices are presented. (1) The interval number of almost every graph is between n/4 Ig n and n/4 (this also holds for almost every bipartite graph). ( 2) There exist K+\_,, -free bipartite graphs with interval number at least c(m)n 1-2'Cm+1J/lg

Extremal values of the interval number o

Extremal values of the interval number of a graph, II

✍ Jerrold R. Griggs 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 315 KB

I i5 showll that the interval number of a gralh on n vertices is a~ inosl [I;(n ~ Ij], md this bound is best possible. This means that we can represent any l~raph ,,n n verl~cc~ as an intersection graph in which the sets ~ssigued Io the verUccs each ~or, sist of tlxe umorl ~a at m~st [~(n + I)] fini

A sharp edge bound on the interval numbe

A sharp edge bound on the interval number of a graph

✍ Balogh, J�zsef; Pluh�r, Andr�s 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 2 views

The interval number of a graph G, denoted by i(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. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name