Accession Number : ADA189648

Title :   The Total Interval of a Graph.

Descriptive Note : Doctoral thesis,

Corporate Author : ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Kratzke, Thomas M

PDF Url : ADA189648

Report Date : Jan 1988

Pagination or Media Count : 124

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.

Descriptors :   *GRAPHS, INTERVALS, THESES, NETWORKS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE