Files in this item
Files  Description  Format 

application/pdf 9416396.pdf (4MB)  (no description provided) 
Description
Title:  Intersection representations of graphs and digraphs 
Author(s):  Lin, InJen 
Doctoral Committee Chair(s):  West, Douglas B. 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Mathematics
Operations Research Computer Science 
Abstract:  A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We prove that an interval digraph is a unit interval digraph if and only if its adjacency matrix is free of six forbidden submatrices: three 3 by 4 matrices and their transposes. We consider a hierarchy of four classes of interval digraphs. For each class, we provide a forbidden submatrix characterization for membership in the next class. In particular, we prove that a digraph in the ith class belongs to the next smaller class if and only if its adjacency matrix contains no submatrix in the collection we list. The largest class is that of all interval digraphs; the smallest is the class of unit interval digraphs. As a corollary, we obtain a second proof of the result described in the first paragraph. The leafage of a chordal graph is the minimum number of leaves in a host tree in which the graph has an intersection representation by subtrees. We obtain upper and lower bounds on the leafage in terms of other parameters and compute the leafage on special classes of graphs. We use various new observations about chordal graphs and families of subtrees of a tree. We extend the idea of subtree representations of graphs to digraphs. Unlike undirected graphs, every directed graph does have a subtree representation, hence we can define the leafage of a digraph to be the minimum number of leaves in a host tree T in any subtree representation. A catch representation for a digraph D is a subtree representation in which each sink set $T\sb{v}$ is restricted to be a singleton vertex; the source tree "catches" the singletons assigned to its successors. The catch leafage of a digraph D is the minimum number of leaves in the host tree in any catch representation of D. We study upper and lower bounds for the leafage and catch leafage and show that the bounds are the best possible, but can be arbitrarily weak. 
Issue Date:  1994 
Type:  Text 
Language:  English 
URI:  http://hdl.handle.net/2142/19205 
Rights Information:  Copyright 1994 Lin, InJen 
Date Available in IDEALS:  20110507 
Identifier in Online Catalog:  AAI9416396 
OCLC Identifier:  (UMI)AAI9416396 
This item appears in the following Collection(s)

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois 
Dissertations and Theses  Mathematics