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


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a189648.pdf


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