Intersection representations of graphs and digraphs

Lin, In-Jen

Permalink

https://hdl.handle.net/2142/19205 Copy

Description

Title

Intersection representations of graphs and digraphs

Author(s)

Lin, In-Jen

Issue Date

1994

Doctoral Committee Chair(s)

West, Douglas B.

Department of Study

Mathematics

Discipline

Mathematics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Mathematics
• Operations Research
• Computer Science

Language

eng

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."

Type of Resource

text

Permalink

http://hdl.handle.net/2142/19205

Copyright and License Information

Copyright 1994 Lin, In-Jen

Owning Collections