The Total Interval of a Graph.
ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB
Pagination or Media Count:
An interval representation or simply representation R of a graph G is a collection of finite setsRv v Epsilon VG of closed bounded intervals so that u is equivalent to v if and only if there exist theta sub u epsilon Ru, theta sub v epsilon Rv 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 IG. This thesis studies IG 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,IG or 2nG - 3.
- Theoretical Mathematics