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