Files in this item



application/pdf9416396.pdf (4MB)Restricted to U of Illinois
(no description provided)PDF


Title:Intersection representations of graphs and digraphs
Author(s):Lin, In-Jen
Doctoral Committee Chair(s):West, Douglas B.
Department / Program:Mathematics
Degree Granting Institution:University of Illinois at Urbana-Champaign
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
Rights Information:Copyright 1994 Lin, In-Jen
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9416396
OCLC Identifier:(UMI)AAI9416396

This item appears in the following Collection(s)

Item Statistics