The Total Interval of a Graph.
Abstract
An interval representation (or simply representation) R of a graph G is a collection of finite sets(R(v): v Epsilon V(G) of closed bounded intervals so that u is equivalent to v if and only if there exist theta sub u epsilon R(u), theta sub v epsilon R(v) with theta sub u intersects theta sub v not equal to 0. The size of a representation is the number of intervals in the entire collection. The total interval number of G is the size of the smallest representation of G and denoted I(G). This thesis studies I(G) by proving best possible upper bounds for several classes of graphs. For some of the classes, the bounds are in terms of the number of vertices and for some of the classes, the bounds are in terms of the number of edges. The main result is that for planar graphs,I(G) < or = 2n(G) - 3.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1988
- Accession Number
- ADA189648
Entities
People
- Thomas M. Kratzke
Organizations
- University of Illinois Urbana–Champaign