✦ LIBER ✦

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

✍ Scribed by Arundhati Raychaudhuri

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 672 KB
Volume: 56
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(95)00163-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The total interval number of a graph, I:

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

✍ Thomas M. Kratzke; Douglas B. West 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 906 KB

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 assi

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

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

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