INTERVAL DIGRAPHS:
A GENERALIZATION OF INTERVAL GRAPHS
by
Roxanne Drachenberg
B.S., B.A., Regis University, Denver, Colorado, 1988
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1994
This thesis for the Master of Science
degree by
Roxanne Drachenberg
has been approved for the
Graduate School
by
/*/*/??
f Date
Drachenberg, Roxanne (M.S., Applied Mathematics)
Interval Digraphs: A Generalization of Interval Graphs
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
Intersection graphs, and in particular, interval graphs have been extensively studied;
however, intersection and interval digraphs have only recently been the subject of
research. This is a survey of those results for intersection and interval digraphs that
are analogous to known characteristics of intersection and interval graphs. For
example, the well known consecutive ones property for interval graphs, when
generalized to interval digraphs, divides into two cases, both of which are proven.
In addition to analogies drawn from interval graphs, other results identifying
interval digraphs are examined. For instance, Ferrers digraphs and Ferrers
dimension are defined and results linking them to interval digraphs are illustrated.
Finally, results regarding other families of sets such as circulararcs are discussed.
This abstract accurately represents the content of the candidate's thesis. I
recommend its publication.
Signed
m
Contents
1 Introduction............................................................... 1
2 Interval Graphs.............................................................3
2.1 History............................................................3
2.2 Characterizations of Interval Graphs . . . ........................4
2.2.1 Maximal Cliques...........................................5
2.2.2 Z4 is Not a Generated Subgraph............................8
2.2.3 Gc is Transitively Orientable............................10
3 Interval Digraphs .....................................................12
3.1 Intersection Digraphs.............................................12
3.1.1 Intersection Number and Biclique Cover Number.........15
3.1.2 Importance of Loops......................................20
3.2 Interval Digraphs............................................... 22
3.2.1 Consecutive Ones Property for IntervalPoint Digraphs
....................................................... 23
3.2.2 Consecutive Ones Property for Interval Digraphs in General
.......................................................28
4 Ferrers Digraphs...........................................................35
4.1 Preliminaries.....................................................35
IV
4.2 Adjacency Matrices and Ferrers Digraphs.........................39
4.3 Adjacency Matrices and Ferrers Dimension........................50
5 Other Characterizations. ................................................58
5.1 Relating Interval Graphs to Interval Digraphs...................58
5.2 CircularArc Digraphs...........................................60
5.3 Other Generalizations...........................................65
6 Conclusion...............................................................67
Bibliography................................................................69
v
1 Introduction
Interval graphs have been extensively studied since their inception in 1959. It has
only been recently, however, that graph theorists developed an interest in interval
digraphs. This paper develops the foundations and presents a survey of the work
completed in the area of interval digraphs.
Since interval digraphs have their roots in interval graphs, this discussion begins
with the latter. Interval graphs are defined and some of their characterizations are
discussed and illustrated in Chapter 2 in order to provide a basis for interval
digraphs. Knowing how interval graphs are characterized motivates interest in
discovering if those same characterizations are true for interval digraphs.
In Chapter 3, analogous results are given for intersection digraphs, including the
intersection number and how this relates to the biclique cover number of a digraph.
As opposed to intersection graphs, loops do occur in intersection digraphs;
therefore, digraphs with loops are investigated. Also in this chapter the consecutive
ones property, a wellknown result for interval graphs, is generalized to interval
digraphs by considering two incidence matrices instead of one, one matrix for the
source intervals and one matrix for the terminal intervals.
Characterizations beyond those known for interval graphs are examined in the
1
remaining chapters. In particular, Ferrers digraphs and Ferrers dimension are
defined in Chapter 4 and necessary and sufficient conditions for a digraph to be
interval are given. One of those results being that a digraph is interval if and only
if it is the intersection of two Ferrers digraphs whose union is complete.
Chapter 5 contains a brief overview of results found in the current literature. We
prove a theorem stating that a graph is interval if and only if its corresponding
symmetric digraph with loops is interval. Circulararc digraphs are studied as the
generalization of circulararc graphs. Much of the work done regarding these
digraphs is analogous to that which is described in Chapter 3 regarding interval
digraphs. A statement which implies that the complement of an interval digraph is
a circulararc digraph is verified. Catch digraphs, containment digraphs and
circulararc containment digraphs are briefly mentioned also.
Finally, open questions regarding other possible generalizations of interval graphs
are posed in Chapter 6.
2
2 Interval Graphs
2.1 History
Since interval digraphs are an outgrowth of interval graphs, we begin with a
discussion of interval graphs, which are a special kind of intersection graph.
Definition: Given a family of sets, each set assigned to a vertex, the intersection
graph of the family of sets has an edge between two distinct vertices
if and only if the corresponding sets intersect.
What kinds of graphs does this describe? From a theorem by Marczewski, 1945
[16] we know all graphs are intersection graphs. So intersection graphs only
become interesting when one looks at different kinds of families of sets. The focus
here is on families of intervals on the real number line.
Definition: A graph G is an interval graph if it is the intersection graph of some
family of intervals on the real number line.
Interest in intersection graphs of families of intervals on the real number line began
with a problem in genetics called Beiizer's problem. (See Roberts [16] for a
description of this problem.) Benzer mapped the substructure of the gene to
3
intervals on the real number line which supported his hypothesis that the structure
of the gene is linear.
Genetics was the beginning, but the applications for interval graphs are limited only
by our imaginations. Interval graphs can be used to model one's indifference
between alternative choices. They have been used to chronologically order artifacts
in archaeology and characteristics in childhood development. Applications also
exist in transportation models of the phasing of traffic lights and in ecology to
model food webs [16].
2.2 Characterizations of Interval Graphs
Interval graphs are relatively easy to identify. The following characterizations
found in Roberts [16] not only tell us some things about what interval graphs look
like, they also give us information about their maximal cliques, their complements
and their vertexclique incidence matrices.
I. [Fulkerson & Gross, 1965] A graph G is an interval graph if and only if
there is a ranking of the maximal cliques of G which is consecutive.
II. A graph G is an interval graph if and only if the columns of its vertexclique
incidence matrix can be permuted so that the ones appearing in any row
appear consecutively. (This is a restatement of I due to Roberts [16].)
4
III. [Gilmore & Hoffman, 1964] A graph G is an interval graph if and only if it
satisfies the following conditions.
a) Z4 is not a generated subgraph of G, and
b) Gc is transitively orientable.
The interest here, is not in the proofs of these theorems, but in understanding how
and why these characterizations interrelate to each other and describe interval
graphs. To this end, in the following subsections examples are used to illustrate
these properties.
Figure 2.1 Graph A
2.2.1 Maximal Cliques
First of all, a clique is a complete subgraph and a maximal clique is a complete
subgraph that is not contained in a larger clique. For graph A above the maximal
cliques are as follows.
5
1 7 8
To consecutively rank the cliques simply means that whenever u is in K{ and K
for i < j, then for i < r < j, u e Kr. So we can easily find a ranking for graph A
to be Ks, K6, Kv Ky Kv Kx It is easy to see how this can be restated in terms of
consecutive ones in the vertexclique incidence matrix of A. Since consecutively
ranking the maximal cliques by definition is to insure that any vertex appearing in
more than one clique will be in consecutive cliques, then the incidence matrix will
have consecutive ones.
The connection between maximal cliques and interval graphs is clear when the
maximal cliques are renumbered in order of their ranking as shown in the incidence
matrix below. Assign each vertex the interval [i,j] where K. is the first clique and
K is the last clique to which that vertex belongs. For example, vertex 1 is
assigned the interval [1,4] and so on. A quick check will confirm that this
assignment works. Since intervals on the real number line must be consecutive,
then consecutive ones means the graph is an interval graph.
6
*2 *3 *4 *5 *
*5 *6 *4 *3 *2 K
1 1 1 1 1 0 0
2 0 1 1 0 0 0
3 1 1 0 0 0 0
4 1 0 0 0 0 0
5 1 0 0 0 0 0
6 0 0 0 1 1 0
7 0 0 1 1 0 0
8 0 0 0 0 1 0
9 0 0 0 0 0 1
10 0 0 0 0 0 1
VertexClique Incidence Matrix
new numbering
Figure 2.3 Interval assignment for
graph A
The following graph is a cycle on 4 vertices where its 4 maximal cliques cannot be
consecutively ranked. Vertices 1,2 and 3 each belong to consecutive cliques;
however, vertex 4 is in Kx and K4 which are clearly not consecutive.
7
2
Renumbering the cliques won't change the fact
that they can't be ranked consecutively. Neither
can the ones be consecutively arranged in each
row of its incidence matrix:
*2 *3 *4
1 1 1 0 0
2 0 1 1 0
3 0 0 1 1
4 1 0 0 1
Figure 2.4 A cycle on 4
vertices
Therefore, this is not an interval graph which leads us to the next property.
2.2.2 Z4 is Not a Generated Subgraph
A generated subgraph of a graph G is a subset of the vertices of G along with all
edges of G connecting those vertices; and, Z4 is a cycle of length 4. Z4 itself is not
an interval graph. This is most easily demonstrated by trying to find an interval
assignment. Assign vertex 1 the interval 1(1), and so on for all of the vertices.
Then 1(2) must intersect with 1(1), 1(3) must intersect with 1(2) but not with 1(1).
1(4) must intersect with 1(3) and not with 1(2). But 1(4) must also intersect with
1(1). Clearly, no matter what vertex you begin with, the result will be the same.
8
EJ
h]
b
Figure 2.5 Attempted interval assignment for 4cycle
Thus an interval assignment cannot be found. So if a graph contains Z4 as a
generated subgraph, it is not an interval graph.
The following example, however, illustrates that this condition is not, by itself,
sufficient in order to have an interval graph.
5 l 4
Figure 2.6 Graph B with its
maximal cliques
Graph B has no Z4, but its maximal cliques cannot be consecutively ranked and it
doesn't have the consecutive ones property. Therefore, it cannot be an interval
graph.
9
2.2.3 Gc is Transitively Orientable
Gc refers to the complement of G. a graph on the same vertex set as G that contains
all the edges not contained in G. A transitive orientation O. of a graph G is an
assignment of direction to the edges of G such that if ab is an edge in O, and be e
E(O), then ac e E{O). Graph B above, in fact, does not have a transitively
orientable complement. It is left to the readers to satisfy themselves that this is the
case.
Figure 2.7 An orientation of the
complement of graph B
Why is the complement of an interval graph transitively orientable? Consider the
complement of an interval graph. Each vertex has an interval assigned to it and an
edge exists if and only if two intervals DO NOT intersect. Then these intervals can
be ordered. For example, the interval assigned to vertex u might be less than the
interval assigned to vertex v. Orient the edges of Gc from u to v whenever
10
I(u) < I(v). If /() < /(v) and I(v) < I(w), then I(ti) < I(w) so the orientation
will be transitive.
To summarize, interval graphs are identifiable by examining their maximal cliques,
their vertexclique incidence matrices, their complements and their generated
subgraphs. Are any of these properties transferable to interval digraphs? Are there
other characterizations of interval digraphs? These are the questions dealt with in
the next chapter. Also, there are intersection graphs of other families of sets that
are of some interest. Although not mentioned with regard to interval graphs at this
point, they will be discussed later.
11
3 Interval Digraphs
3.1 Intersection Digraphs
Interest in interval digraphs began when Sen, Das, Roy and West, in their work
Interval Digraphs: An Analogue of Interval Graphs introduced analogies between
interval graphs and their characterizations and interval digraphs [18]. They
established a basis of definitions and theorems from which others have expanded.
To begin, we saw in Chapter 2 that interval graphs are a special case of intersection
graphs. So before discussing interval digraphs, the first step is to find out if there
is an analogue to intersection graphs for directed graphs. There is. In fact the idea
is easily transferred to digraphs by letting an ordered pair of sets, instead of one set
as with graphs, correspond to each vertex.
Definition: Given a family of ordered pairs of sets consisting of a source set, Sv
(head) and a terminal set Tv (tail), assign each vertex an ordered pair
of sets. The intersection digraph. D(V,E), is the digraph such that
uv is an edge of D if and only if Su fl Tv 0 where loops are
allowed but multiple edges are not.
12
Example 3.1: This example illustrates how each vertex is assigned an ordered pair
of sets, and how this results in an intersection digraph.
Let vertices 1 through 5 have the following set assignment.
vr *1 = {1,2,3,4}, 7, = {2,5,7}
vr (1,3,6}, ^  {1,3,9}
v3: *3 = {7,8,9}, T*  {2}
V4: {3,8,11}, ta = {3,5}
V5: *5 = {1,5}, = {1,2,3}
Sj fl T, 0, therefore edge 1,1 exists (a loop at vertex 1)
Sl fl T3 0, therefore edge 1,3 exists and so on. Thus D is constructed.
Figure 3.1 Notice that loops will
occur, but multiple edges are
disallowed by definition.
As previously mentioned, every graph is an intersection graph; but is the same true
for digraphs? In fact, the answer is yes. Label the edges of a digraph l,2,...,m.
13
Let the source set of each vertex correspond to the set of out edges and the terminal
set equal the set of in edges of that vertex. This results in a collection of sets whose
intersection is the given digraph. Therefore, it is an intersection digraph. More
formally,
Theorem 3.1 Every digraph D=(V,E) is the intersection digraph of some family
of sets.
Proof: Let Sv consist of the edges of D such that vu is an edge of D and Tv consist
of the edges of D such that uvis an edge of D, for all v e V(D). Then
S fl f # 0 if and only if there exists an edge ttv e E(D) implies there will be an
edge in the intersection digraph.
Every digraph is the intersection digraph of some family of sets.
Example 3.2:
Figure 3.2
14
3.1.1 Intersection Number and Biclique Cover Number
Definition: The intersection number of an undirected graph G is the
minimum size of a set U such that G is the intersection graph of
subsets of U.
The following example illustrates this concept.
Example 3.3:
S,;l} S, = {U} Sj {2,4}
Figure 3.3
In graph G above, if = {1}, then SÂ¥ S3 and SA must also contain 1 as
these four vertices are adjacent. Vertices 5 and 6 are not adjacent to 1 and
3; therefore, their assigned sets cannot contain 1. However, 5 is adjacent to
2, so we can add 2 to both sets. Continuing in this manner, we find it takes
four different numbers assigned to the vertices to ensure that all of the edges
of G are accounted for, and there are no additional edges included. Thus
U={1,2,3,4} is minimum and i(G)=4.
15
Erdos, Goodman and Posa, in The Representation of a Graph by Set Intersections,
1966, prove that the intersection number of a graph is equal to the minimum
number of complete subgraphs needed to cover a graph's edges [18]. In the above
example, it will take a minimum of four cliques to cover the edges, which equals
the intersection number of G.
For digraphs, the following definition is virtually the same as for its counterpart;
however, to talk about covering the edges of an intersection digraph, we need an
additional definition.
Definition: The intersection number. i(D). of a digraph is the minimum size of
U such that D is the intersection digraph of ordered pairs of subsets
of U.
Definition: A generalized biclique (abbreviated GB) is a subdigraph generated by
vertex sets X and Y, not necessarily disjoint, whose edges are all xy
such that x e X and ye 7.
Since X and Y may not be disjoint, loops are possible. So "generalized" refers to
the fact that the sets X and Y are not necessarily disjoint.
The analogue to Erdos, Goodman and Posa's result for graphs is below.
Theorem 3.2 [Sen, Das, Roy, West, 1989] The intersection number of a digraph
equals the minimum number of GB's required to cover its edges, and the best
possible upper bound on this is n for nvertex digraphs.
16
Proof: In order to prove this equality, we need to show (1) minimum #(GB) > i(D)
and (2) minimum #(GB) <; i(D). Suppose PvP2,...,Pk is a minimum collection of
GB's whose union is D, where P. = {(Y.,7.)}. Let Sv = {xv e XJ and let
Tv = (;v e 7.}. Thus Su 0 Tv 0 if and only if tcv e E(D). In other words,
the source set for vertex v is the set of all GB's containing v in its X set, and the
terminal set for vertex v is the set of all GB's containing v in its Y set. Since
there are k of these GB's from which to form the ordered pairs, the numbers
are used in their formation. Then since i(D) is the minimum size of U,
i(D) s k
Conversely, if D is the intersection digraph of ordered pairs of subsets of U, then
by definition  U  =i(D). Then for each vertex of D, we have an ordered pair
(,Sv,Tv) whose elements come from the set U = {l,2,...,i(D)}. We can find i(D)
GB's of D as follows. Let u e X. i e Sa and v e Yf => / e Tv. Continue for
all u,v e V(D). Since the elements of the source and terminal sets come from
l,2,...,i(D), then there will be at most i(D) GBs constructed. Also, uv e E(D) if
and only if u e Xt and v e 7. for some i, so the union of the GB's is D.
Therefore, the minimum #(GB)=k <; i(D). Thus, i(D)=kas required.
As for the bound on i(D), note that the set of edges with v as the source vertex is a
generalized biclique. Therefore, n distinct generalized bicliques would cover all the
edges. So if each vertex were a source vertex for only one edge, i.e., a directed
17
cycle of length n, it would take n disjoint GB's to cover D where each GB is
composed of 1 edge only.
Example 3.4: This example illustrates the steps of the proof. Vertices are labeled
v to avoid confusing them with the 7 s.
GBX: II C. 'v' 7i = (vrv5> s = VJ {/v. e X,} r {v, 6 7,.}
GB2: X2 = ?2 = (vs> s = V1 {1,5} r., 0
GB *3 = W* 73 = (VW 5 = v2 {2,6} T = v2 {1}
GB XA = fV4VS> *4 <**> 5 = V3 0 T = v3 {2}
GB5: Xs = (vj, ^5 = W 5 = v4 {1,4} T = V4 {3,5}
GB X6 = ^V2> Y6 = ^V5>
0 ^ {2,4} T = v5 {1,6}
s v6 {3} r = v6 {3,4}
s = v7 0 r = v7 {3}
18
Example 3.5: This proof can be used to find the minimum sized intersection sets if
it is known how many GB's are needed to cover the edges, as this example
shows. Or, if the minimum size of U is known, the proof will construct the
generalized bicliques needed to cover the edges.
Clearly i(D)=2 as it takes 2 GB's to cover the edges.
GBy X, = {1}, = {1,2,3}
GB X. = {4}, 7  {1}
s1 = {1} r, = {1,2}
52 =0 t2 = {1}
53 = 0 r3 = {1}
= {2} T = 0
4
Figure 3.5
19
3.1.2 Importance of Loops
Loops do not occur in intersection graphs, but they can happen with digraphs since
each vertex has a source and a terminal interval which can intersect. Therefore, it
is important to examine how loops affect the intersection number of digraphs.
Definition: Let Dn be the complete digraph of order n with vertices {l,2,...,n}
in which each ordered pair of vertices (ij) i *j, forms an arc of Dn.
Definition: Let D* be the complete digraph of order n in which each ordered
pair of vertices (ij) including i =j, forms an arc of D*. Then
since multiple edges are not allowed, there will be n loops, one loop
per vertex.
The intersection number of D* is 1 as is pictured below.
Example 3.6:
i(Z>4+) = 1 as GB y Xx = (1,2,3,4}, Yx = {1,2,3,4}.
20
When loops are not allowed, the intersection number will be greater than 1 as X.
can no longer equal 7.. Without loops, the digraphs in question are simply Dn.
To cover Dn, generalized bicliques are no longer needed as bicliques will do the
job. De Caen, Gregory and Pullman [4] prove that the biclique cover number of a
f (k\\
complete digraph on n vertices is equal to s(n), where s(n)
nun
Â£
LJ
V 2
however, in [18] the claim is made that i(Z>M) = 2 log 21 F
The following chart compares s(n) to 21og2 as  V  = .
k (k) LJ ^ 2 n s(n) 21og2
2 2 4 4 4
3 3 5 4 4.64
4 6 6 4 5.17
5 10 7 5 5.61
6 20 8 5 6
9 5 6.34
9 126 10 5 6.64
20 184,756 100 9 13.29
100,000 20 33.22
The chart suggests that 2 log 7n is not accurate for > 4; but so far as the above
data goes, it is an upper bound.
21
Example 3.7: Dg can be covered with 5 bicliques as is demonstrated below.
*1 = {2,4,6,8}, = {1,3,5,7}
(1,2,3,4}, Y2 " (5,6,7,8}
(1,5,6,7}, r3  (2,3,4,8}
{3,4,7,8),  (1,2,5,6)
*5 " (2,3,5,8), r5  {1,4,6,7}
1 2 3 4 5 6 7 8
1 0 1 1 I 1 1 1 1
2 1 0 1 1 1 1 1 I
3 I 1 0 I I 1 1 1
4 1 1 1 0 1 1 1 1
5 1 1 1 1 0 1 1 1
6 1 1 1 1 1 0 1 1
7 1 1 1 1 1 1 0 1
8 I I 1 1 1 1 1 0
Therefore, i(Dg) = 5.
3.2 Interval Digraphs
Interval digraphs are a special case of intersection digraphs as was true for interval
and intersection graphs, except now each vertex has two intervals assigned to it.
Definition: An intersection digraph where each source set and terminal set is an
interval is an interval digraph.
22
Example 3.8:
v,: Sl = [1,2] r, = [1,3]
v2: S2 = [1,3] T2 = [2]
v3: S3 = [3,5] T3 = [5]
v4: = [1,0] J4 = [1,2]
0
4
Figure 3.7
As interval digraphs are a subset of intersection digraphs, all that has been stated
thus far holds for interval digraphs; but, what further characterizations analogous to
those for interval graphs can be made about interval digraphs?
As was discovered in Chapter 2, interval graphs are characterized by the fact that
the ones in the rows of their vertexclique incidence matrices can be arranged
consecutively. The analogy for interval digraphs divides into two cases.
3.2.1 Consecutive Ones Property for IntervalPoint Digraphs
Definition: Interval digraphs representable using singleton terminal sets are
intervalpoint digraphs.
In other words, the terminal set is a single point, but the source set may not be.
Theorem 3.3 [18] D is an intervalpoint digraph if and only if its adjacency matrix
has the consecutive ones property for rows.
23
Proof: By definition, D has an intervalpoint representation if and only if there are
source (S(v)) and terminal (T(v)) sets where the terminal sets consist of one point
of a real number line, and tcv e E(D) if and only if S(u) fl T(v) 0. Let
S(v)=[a(v),b(v)] and T(v)=[c(v)]. Then uv e E(D) if and only if c(v) e S(u).
We may assume the c(v)'s are distinct, as if two or more are the same, then there
would be two or more duplicate rows in the adjacency matrix. As multiple edges
are not allowed, the adjacency matrix A(D) will contain zeros and ones only.
Number the vertices in increasing order of c(v). Then c(v) 6 S(u) is true if and
only if the rows of A(D) exhibit the consecutive ones property because of the
following. Assume the consecutive ones property doesn't hold for rows of the
adjacency matrix of D. This implies there exists a vertex v such that if vu. e E(D)
then vu._x $ E(D) and vu.^ <Â£ E(D) and either m._2 or vnj+2 e E(D). But
u^u vu vu^2 are consecutive distinct c(v)'s which implies c(V) e S(v) and
c(u._2) e S(v) but c(Uj_x) S(v), a contradiction as S(v) is an interval on the real
number line.
Furthermore, by permuting the columns of A(D) so that all of the ones are
consecutive, then relabeling the vertices according to this new column order, we
can obtain an intervalpoint representation of D as follows. Take c(vt) = A,
a(vfe) = min {/1vjtvi e Â£(Z>)} and bfvj = max {i\vkv. e E(D)}. (This is the reverse
of that which is found in [18].)
24
Example 3.9: The following exemplifies the steps of the proof.
1 original labeling
1' new labeling
1 2 3 4 5 6
1 0 1 0 0 0 0
2 0 0 1 1 0 0
A(D): 3 1 0 0 0 1 1
4 0 0 0 0 1 0
5 0 1 0 0 0 1
6 0 0 0 0 0 0
1' 2' 3' 4' 5' 6'
1 5  6 2 3 4
lf 1 0 0 0 1 0 0 '
4' 2 0 0 0 0 1 1
A'(D): 1 0 0 0
5/ 3 1 1
6' 4 0 1 0 0 0 0
2' 5 0 0 1 1 0 0
3' 6 . 0 0 0 0 0 0 .
25
Since the consecutive ones property holds, D is an intervalpoint digraph.
Relabel the vertices, and use the theorem:
c(vk)=k, a(vfc) = min {/vfcv. 6 Â£(Z>)} andb(vfc)= max {z'vfcv. e E(D)}.
So the following intervalpoint representation is gained.
*1 = [4] Ti = [1]
s2 = [3,4] t2 = [2]
^3 = 0 T, = [3]
*4 = [5,6] T< = [4]
*5 = [1,3] = [5]
= [2] = [6]
This proof explains why the adjacency matrix of an intervalpoint digraph will
exhibit the consecutive ones property. This, however, wasn't the case for interval
graphs. Nor is it the case for interval digraphs in general.
Note in the following example from [18] that vertices 2,3 & 4 are adjacent to both
1 and themselves. Clearly the adjacency matrix will not exhibit the consecutive
ones property no matter how the columns are permuted.
26
Example 3.10: The smallest interval digraph that is not an intervalpoint digraph is
below.
Not only is it impossible to permute the columns of A(D) to get the ones in
each row consecutive; but, it is also not possible to find an intervalpoint
representation of D as demonstrated. If we proceed as in the proof by first
setting Tj = [r], then finding S(v), a false interval representation occurs (F)
because [1] e S3 and [3] eS3, but if the single point intervals [1] and [3]
are contained in the interval corresponding to vertex 3, so must [2]. But
that would make (3,2) an edge in D, which is not the case. Changing the
order of the Tt' s will not affect the outcome. The correct representation is
shown (T).
Figure 3.9
27
0
S2 = [1,2] T2 = [2]
F:
S, = [1,3] r3 = [3]
S4 = [1,4] T4 = [4]
sl  0 = [1,3]
= [1] t2 = [1]
53 = [2] T,  [2]
*4 = [3] ^4 = [3]
3.2.2 Consecutive Ones Property for Interval Digraphs in General
In general, interval digraphs are characterized by a consecutive ones property for
the rows of two pointset incidence matrices, where one matrix represents the
source sets and the other one represents the terminal sets as defined below. For the
following definitions, let B= {(Zfc,7fc)} be a collection of generalized bicliques
whose union is D.
Definition: The vertexsource incidence matrix for B. denoted V,Xmatrix, is the
incidence matrix between the vertices and the source sets {XÂ£.
Example 3.11: The vertexsource incidence matrix for B= {(Xfc,7fc)} of the GB's
described in Example 3.4 above is as follows.
V,Xmatrix:
*1 *2 *3 *4 *5 *6
vi 1 0 0 0 1 0
V2 0 1 0 0 0 1
V3 0 0 0 0 0 0
V4 1 0 0 1 0 0
V5 0 1 0 1 0 0
V6 0 0 1 0 0 0
V7 0 0 0 0 0 0
28
Definition: Similarly, the vertexterminus incidence matrix for B. denoted V,Y
matrix, is the incidence matrix between the vertices and the terminal
sets {Yk}.
Example 3.12: The vertexterminus incidence matrix for B= {(Xk,Yk)} of the
GBs in Example 3.4 is below.
h *2 V rs rs
V1 0 0 0 0 0 0
V2 1 0 0 0 0 0
v3 0 1 0 0 0 0
V,Ymatrix:
V4 0 0 1 0 1 0
V5 1 0 0 0 0 1
V 0 0 1 1 0 0
O
V7 0 0 1 0 0 0
The following theorem is analogous to the consecutive ones theorem for graphs.
Please note that instead of including all maximal generalized bicliques, only some
subset of them such that D is covered are used.
Theorem 3.4 [18] D is an interval digraph if and only if there is a numbering of
the GB's in some covering B of D such that the ones in rows appear consecutively
for both the V,Xmatrix and V,Ymatrix of D.
Proof: (=): Consider such a B whose union is D, and let (Xk,Yk) be a common
numbering of the columns of the V,X and V,Ymatrices that exhibits the
29
consecutive ones property for both. Let the source and terminal intervals be
sv = 311(1 Tv = [cv=<] where defined by
v e Xk av <. k < bv and v e Yk ~ cv <. k <. dv, i.e., vertex v is in Xk if and
only if k is in the interval assigned to Sv and v is in 7k if and only if k is in the
interval assigned to 7\ Then D is an intersection digraph where the source and
terminal sets are intervals on the real number line; therefore, D is an interval
digraph.
(=>): Assume D is an interval digraph. Consider a representation of D by a family
{(Sv,Tv)} of ordered pairs of intervals. We may assume the intervals are closed
and have integer endpoints. Let Sv = [av,bv] and Tv = [cv,dv] For each integer k
belonging to any of these intervals, define a generalized biclique Bk = (Xk,Yt) as
follows: Let Xk = {vk e SJ and Yk = {v\k e Tv}. In other words, for each
source set, Sv, containing k within its assigned interval, that vertex v is in Xk.
Then these subsets (Xk,Yk), are generalized bicliques of D. As Sa H Tv a if and
only if u e Xk and v g Yk for some k, then the intersection of these interval pairs
is the union of the GB's.
By constructing the GB's and interval subsets as above, vertex v will be in each Xk
{Yk resp.) where k is the interval covered by subset S (T resp.), so it is assured that
the resulting V,X and V,Ymatrices both have the consecutive ones property for
rows.
30
Example 3.13: This example describes the => direction of the proof.
D is an interval digraph with the following interval representation.
S', = [2] ri = [9,10]
= [1] T2 = [2]
S*  E.1] Ts  [1]
*4 = [5,7] ^4 = [1]
Define GBk ={(XkJk)} by:
Xk = {v\k e SJ 7k = {v\k e TJ
= (2,3} = {3,4}
X2 = {1} Y2 = {2}
= 0 Y2 = 0
= 0 ^4 = 0
Therefore, GB,: = {2,3} = {3,4}
GBr *2 = {1} Y2 = {2}
cover the edges of D.
Since each vertex was placed in a source (or terminal) set of Fk where k is
in the interval of the source (or terminal) set corresponding to that vertex,
then the vertexsource (or terminus) incidence matrix will have the
consecutive ones property.
31
*1 *2 Y2
V1 0 1 V1 0 0
V,X: v2 1 0 V,Y: v2 0 1
V3 1 0 V3 1 0
V4 0 0 V4 1 0
Interval graphs exhibit the consecutive ones property for all their maximal cliques.
This property does not hold, however, for interval digraphs as the following
example shows [18].
Example 3.14:
Figure 3.11
G,: *1  {1,2}, r, = {1,4}
GB2: *2 = {1,3}, Y2  {2,4}
GBy *3  {1,4}, ^3 = {3,4}
32
*1 *2 *3 *1 y2 *3
V1 1 1 1 V1 1 0 0
V,X: v2 1 0 0 V,Y: v2 0 1 0
V3 0 1 0 V3 0 0 1
V4 0 0 1 V4 1 1 1
Since the V,X and V,Ymatrices have the consecutive ones property, D is
an interval digraph. Following the theorem, D can be represented by the
ordered pairs of intervals constructed below.
Sv = K,6V] and Tv = [cv,
V e Y~ k e T.
k V
1 6 =* 1,2,3 e S, 1 e 7, 1 e l, = [1,3] Ty = [1]
2 6 F, => 1 6 S2 2 e J2 =>2 e T2 ^2 = [i] II [2]
3 el, = 2 e S3 3 ^3 3 e V ^3 = [2] II [3]
4 e X3 3 e S4 4 6 7,,72,73 1,2,3 e r4 11
33
However, the remaining maximal GB's (which were not needed to cover the
edges of D) cannot be added to the incidence matrices without destroying the
consecutive ones property.
GB *4 = {1}, ^4 = (1,2,3,4}
GBS: *5 = (1,2,3,4}, r5 II
*2 *3 I x
V1 1 1 l  l i
Y,X: V2 1 0 0 1 i
V3 0 1 0 1 0 l
V4 0 0 1 1 0 i
1 r4 r5
V1 1 0 0 1 i 0
V,Y: V2 0 1 0 1 i 0
V3 0 0 1 1 l 0
V4 . 1 1 1 1 i 1
34
4 Ferrers Digraphs
In Chapter 2 we saw that interval graphs have several nice characterizations. In
Chapter 3 we discovered that one of those characterizations has an analogy to
interval digraphs. In this chapter we look at other ways in which interval digraphs
are characterized.
4.1 Preliminaries
Before proceeding with these properties, several definitions and concepts need to be
introduced.
Definition: Ferrers digraphs are digraphs whose successor sets are linearly
ordered by inclusion, where the successor set of v is its set of out
neighbors, i.e., Sv = {u e V\vu 6 E).
Example 4.1:
4 3
Figure 4.1
35
Successor Sets: Sv = {u e V\vu e E}.
^={1}
^={1,2}
53= {1,2}
SA={1,2,3}.
F is a Ferrers Digraph
Is the same true for the predecessor sets?
Predecessor Sets: Pv = {u e V\uv e E)
Px = {1,2,3,4}
P2 = {2,3,4}
P3 = {4}
P* = 
' PAzP3zP2cP 1
Yes, the predecessor sets are also linearly ordered.
The vertices of Ferrers digraphs can then be partitioned according to which
successor and predecessor sets they belong. These partitions are defined as follows.
Definition: Source partition ve^4fcif v belongs to the kA largest nonempty
predecessor set and to no smaller set and A0 contains vertices with
no successors (i.e., vertices that aren't in a predecessor set) if any
exist.
Definition: Terminal partition veDk if v belongs to the kA smallest non
empty successor set and none smaller, with the last set containing the
36
vertices with no predecessors (i.e., the vertices that are in no
successor set) if there are any.
In a larger example, this partitioning becomes apparent.
Example 4.2:
Successor Sets:
*.= {>
S2= (1.2,3)
S3= {1,2,3}
S4= {1,2,3}
S5={1,2,3,4}
S6={1,2,3,4}
S?={1,2,3,4}
Sg={l,2,3,4,5,6,7>
Predecessor Sets:
Px = {2,3,4,5,6,7,8}
P2 = 12,3,4,5,6,7,8}
P3 = {2,3,4,5,6,7,8}
PA = {5,6,7,8}
P5 = {}
P6 = {8}
P7 = {8}
^8 = O
37
Then the partition sets will be as follows.
Source Partition Sets
^0=0)
{2,3,4}
A2={ 5,6,7}
A3={8}
Terminal Partition Sets:
0,2,3}
D2={ 4}
^>3= {5,6,7}
^4={8}
The adjacency matrices of Ferrers digraphs can be permuted so that the l 's appear
in the lower left of the matrix. This makes it easy to partition the vertices as
described above. In the following adjacency matrix, we see that the rows
correspond to the successor sets and the columns correspond to the predecessor sets.
In addition, we see that adjacency in D occurs between source (A.) and terminal
(D ) partitions only when / > j, i.e., uv is an edge if and only if i > j where
u eAt and veDj.
1 2 3 4 5 6 7 8
1 ' 0 0 0 0 0 0 0 0
2 1 1 1 0 0 0 0 0
3 1 1 1 0 0 0 0 0
4 1 1 1 0 0 0 0 0
5 1 1 1 1 0 0 0 0
6 1 1 1 1 0 0 0 0
7 1 1 1 1 0 0 0 0
8 1 1 1 1 1 1 1 0
J>i V D, ^4
38
Definition: The union of 2 digraphs is complete if every ordered pair of vertices
(including u=v) forms an edge in at least one of them, i.e., for all
a,b e V(D), V(F), a,b e E(D) or E(F).
4.2 Adjacency Matrices and Ferrers Digraphs
Theorem 4.1 [18] The following are equivalent:
A) D is an interval digraph
B) The rows and columns of A(D) can be (independently) permuted so that
each 0 can be replaced by one of {R,C} in such a way that every R has only
R's to its right and every C has only Cs below it.
C) D is the intersection of two Ferrers digraphs whose union is complete.
In order to understand what each of these characteristics means and how they
interrelate, the following example from Section 3.2 is used.
v2: S2 = [1,3] T2 = [23
vy S3 = [3,5] r3 = [5]
v4: S4 = [1,0] Ta = [1,2]
v,: S; = [1,2] Tx = [1,3]
Figure 4.3
39
Since D is an interval digraph, its adjacency matrix should exhibit property B
above.
A(D):
1 2 3 4
1 1 1 0 1
2 1 1 0 1
3 1 0 1 0
4 0 0 0 0
Each vertex has a source set [a(v),b(v)] and terminal set [c(v),d(v)]. Define two
vertex numberings as follows.
1) Let the first numbering, uv...,un, be defined by uk = v if a(v) is the fc*
smallest value among the a's where ties are broken arbitrarily. The smallest
value among the a's is 1 so ux = 4. Continuing in this manner, the new
numbering is ux = 4, m2 = 1, 3 = 2, u4 = 3.
2) The second new numbering, wl,...,wn, is obtained by wk= v if c(v) is the
k01 smallest value among the c's with ties broken arbitrarily. Proceeding as
above, the new numbering is Wj = 1, w2 = 4, w3 = 2, w4= 3.
Allow the rows of A(D) to be permuted by the first new numbering and the
columns by the second. Then the vertices labeling the rows of A'(D) are listed in
order of the opening endpoints of their source intervals. And the columns are listed
in order of the opening endpoint of each vertex's terminal interval.
40
W2 W3 "4
1 4 2 3
M1 4 0 0 0 0
U2 1 1 1 1 0
3 2 1 1 1 0
4 3 1 0 0 1
A zero in the adjacency matrix indicates (ut,w ) is not an edge in D which means
SUt fl T 0 or [a(.),*(.)] does not intersect with [c(wy),J(w)]. Clearly, there
are only two ways in which this can occur. Either ciyv^ > b(u.) or a(u.) > .
Then relabel the ijA zero with a C if a(u) > d(w.) and with an R if
c(w.) > b(u).
For example, the position above is zero because S4 fl 7^= 0, i.e.,
[1,0] fl [1,3] = 0. In this case, b < c so this zero becomes an R. Since the
c(w.)'s are getting larger to the right, and in this row, b remains the same, all
remaining entries in this row will be R. Therefore, once an R appears, there will
only be R's to its right.
On the other hand, the u4,w2 position is represented by [3,5] (1 [1,2] = 0 where
a>d so this zero becomes a C. Since d remains the same in this column and the
a(.)'s increase when moving down through the matrix, once there is a C, there
will only be C's below it.
41
A'(D) becomes:
1 4 2 3
4 R R R R
1 1 1 1 R
2 1 1 1 R
3 1 C C 1
But why is this the case? Simply because if a digraph is interval then it has an
interval assignment, which means the intervals can be ordered by their position
along a number line and the replacement of zeros in its adjacency matrix can be
done by R's and C's as stipulated in the theorem.
As for property C, start with the above adjacency matrix with the R's and C's.
Create two new digraphs, Fl and F2 as follows. Let Fx be D plus the edges
labeled R in A'(D) above. Then A(Fl) will have zeros only where the C's are.
Since wherever there is a C there are only C's below it, then the zeros in A(F^) can
be placed in the lower left with a column permutation.
A '(F,)
4 2 1 3
4 1 1 1 1
1 1 1 1 1
2 1 1 1 1
3 0 0 1 1
Then Fl is a Ferrers digraph since its successor sets are ordered by inclusion, i.e.,
*4 = *1 = *2
3
42
Let F2 be D plus the edges corresponding to the Cs. In this case, the only zeros
will be where the R's are, so any zero will have only a zero to its right. Therefore,
by row permutations, the zeros of A(F2) can be placed in the upper right.
A (F2):
1 4 2 3
4 0 0 0 0
1 I I I 0
2 1 1 1 0
3 1 1 1 1
Again, the successor sets are ordered by inclusion so F2 is a Ferrers digraph.
It is Obvious that F, f) F2 = and that Fl U F2 is a complete digraph as there are
no more zeros left. The methods illustrated here are precisely those methods used
to prove A = B =* C. It remains to show that C =* A.
So far the assumption has been that D is an interval digraph, and its interval
assignment was known. But what if property C for example is known. How can
an interval assignment for D be found? This is not so easy. Therefore, an interval
assignment for D above will be found while going through each step of the
following proof to aid in understanding.
Proof: C=* A: Assume Fv F2 are Ferrers digraphs where Fj H F2 = D and
Fj U F2 is complete. Show D is an interval digraph by constructing an intersection
representation of D by ordered pairs of intervals.
43
Let Hx, H2 be the complements of Fv F2 respectively. Then Hx U H2 = D, and
Hx fl H2 = 0. HX,H2 are Ferrers digraphs also as if the 1 s are elements of
inclusive sets then the 0's are elements of inclusive sets.
Let A0,...,Ap_x be the source partition for Hx and let Dv...,Dp be its terminal
partition where A0, Dp may equal the empty set.
Let C0,...,Cq_j be the source partition and Bx,...,Bq be the terminal partition for the
converse of H2, where Bq, Camay equal the empty set. Since the converse of H2
is the transpose of A(H2), clearly H is also a Ferrers digraph. Adjacency for the
two new Ferrers digraphs, Hv H2, is defined as follows.
Hx: ttv1 e Ht . i > /, where u e A. and veDl
H2: mv e H2 j > k, where u e B. and v e Ck
In our example, with Fx and F2 from above, the adjacency matrices for Hx and
H2 are shown below. From the definitions given earlier, the source and terminal
partitions were determined and are also indicated below.
4 2 1 3
4 0 0 0 0 '
Ssets: s3 = <4>2>
1 0 0 0 0 Ao
A(ffj): , 2 0 0 0 0 Psets: PA = {3}
P, = {3}
3 1 1 0 0 Ai 2 1 J
D2
44
Ssets: Si = {4}
4 1 2 3 = {4}
1 1 0 0 0 = {4}
4 1 0 0 0
1 0 0 0 Â£3 = {1,2,4}
2 Psets:
3 1 1 1 0 c P4 = (1,2,3,4}
2
*1 P2 *3 {3}
P2 = {3}
Constructing the interval representation:
1. Assign numbers apbpcpd. to partitions ApB.,CpDi
S = [a(v),6(v)]
2. Assign vertex v the intervals _ where
Tv = [e(v),rf(v)]
(a(v),b(v),c(v),d(v)) = (apbfck,d) if v e A.,BfCk,Dl
Requirements:
1. S and T must be intervals which implies a <. b. and c. <. d. if
v e A. fl B. and v e C. fl D,
2. uv e E <=> a(u) ^ d(v) and b(u) > c(v)
Constructing an interval representation for D:
1. Make the implication digraph M:
i) 4 directed paths: A0,...,Ap< Bp...,Bg; C0,...,Cg^ and Dv...,Dp.
ii) Add edges:
a) AiBj if At (1 B. 0
b) CkDl if Ck (1 Dt 0
45
c) B.C{ for 1 <; J Â£ q1
d) D.Aj for 1 <. i <. p1
Lemma The implication digraph M is acyclic.
Proof: By way of contradiction, assume M has a cycle. Then it must include at
least one vertex in each of the A's, B's, C's and D's. The only edges between the
B's and C's are B.C.. The same is true for the D's and A's. But, because of (a)
and (b) in the construction of M, the edges between the As and B's and between
the C's and D's came from nonempty intersections. So edges ABj and CkDl are
in the cycle implies u e A. fl B. and v e Ckf)Dr Since the indices do not
decrease on any other kind of edge, then in order for B to get to Ck, j <.k and in
order for Dt to get to A., then l <, i. Then there exists a u e B. arid v e Ck with
j <. 1c implies uv e H2 and there exists a u e Ai and v e Dt with l <.i which
implies uv e Hx, a contradiction as H1 fl H2 = 0.
M is acyclic.
In our example, before the implication digraph is constructed, it is useful to
determine the intersections. Therefore, create a chart comparing vertices with the
partition sets that each is in and then list the intersections between A and B and
between C and D only.
46
2 3
4 1,2,4 3
*i 4 1,2
c. I 1,2,4 3
D. t 4,2 1,3
ersections are: A0 n Bv A0C)B:
a1 n b3,
n Dv C^D
C2r\D2
v
Now create the implication digraph M as follows.
The four directed paths are: BvB2,B3; CvC2, DvD2.
Additional edges: A0B^ a,b3
 C^v C^v C2D2
BXCV b2c2

Figure 4.4
47
2. Ordering: since M is acyclic, there exists a topological numbering.
i) Assign the numbers a,b,c,d to the partition sets ApBpCpDi as the
vertices in M.
ii) Then assign each vertex the number t where t is the number of
vertices in the longest path ending at x.
Lemma This topological numbering f V(M) N 9 f(Y)>f(X) when XT e E(M)
puts f(C) = f(B.) + 1 and f(A.) = f(D) + 1.
Proof: By the construction of M, the predecessors of any C., i > 1 are Ci X and
B.. So any path ending at B. can be extended to C. which implies /(C.) > B. + 1.
Now consider a longest path ending at Cr If it begins at C0 then it visits only C's
and has length / + 1, but any path from Bx to B. is shorter by 1. Then the length
of a longest path ending with B. is at least / + 1 I which implies
f{B) > /(C.) 1. Also, if the path crosses from B. to C. for some j < i, then
replacing the vertex sequence CC. with B x,...iBi gives a path shorter by one.
So that the length of any longest path ending with B. is at least one shorter than the
longest path ending with C., i.e., f(B.) > f(c.) 1.
/(C(.) = f(B.) + 1 and by the same argument f(A.) = f(D.) + 1.
Continuing with the example, the following topological ordering is found by
following the instructions in the proof.
48
Topological Ordering:
/' 0 1 2 3
a. I 1 5
6. I 2 3 6
C. I 3 4
1 4 5
Are the conditions satisfied?
1. a. <, b. if A. fl B. 0
1 j . j
2.
3.
^0 n Bi
A0OB2
ax n b%
a0 = 1 si, 2
a0 = 1 A2 = 3
Oj = 5 <. b3 = 6
ct i d, if c, n c,
0
c1 n 2>v
cx n i)2
c2 n d2
Cj = 3 $ = 4
c, = 3 <. d^ = 5
c2 = 4 z d2= 5
All are strictly increasing sequences.
For i 2> 1, a. = d. + 1: = 5 = dx + 1
c. = d. + 1: Cj = 3 = bx + 1
c2 = 4 = i2 + 1
Therefore, this topological ordering satisfies the requirements.
Then the interval representation for D is as follows.
For a(v) = a., b(v) = b., c(v) = ck, d(v) = dt if v e AitBJtCk,Dlt the
intervals are defined by:
Sv = [a(v),b(v)]
Tv = [c(v),d(v)]
Sx = [a(l) = a0 = 1, i(l) = b2 = 3]
52 = [a( 2) = a0 = 1, b( 2) = b2 = 3]
^ = [a( 3) = a, = 5, b( 3) = 63 = 6]
S4 = [a( 4) = a0 = 1, *(4) = 6, = 2]
T, = [c(l) = c, = 3,
T2 = [c(2) = c, = 3,
r3 = [c(3) = c2 = 4,
T4 = [c(4) = c, = 3,
d{ 1) =
fi?(2) = dx = 4]
^(3) = d2 = 5]
49
And the intervals are:
7 1 2 3 4
s. I [1,3] [1,3] [5,6] [1,2]
Tt [3,5] [3,4] [4,5] [3,4]
This assignment yields the original D. It isn't the same assignment we started with,
nor is this the most efficient one, but it is an assignment that works.
4.3 Adjacency Matrices and Ferrers Dimension
Adjacency matrices of interval digraphs can be characterized further with regard to
Ferrers digraphs. Again, some ideas need to be generated before the theorem is
presented.
Definition:, Ferrers dimension of a digraph D is the minimum number of Ferrers
digraphs whose intersection is D.
Ferrers digraphs were defined in the previous section as having successor sets that
are linearly ordered by inclusion. The following is another way of looking at them.
Definition: A digraph D is a Ferrers digraph if and only if A(D) does not contain
an obstruction, where an obstruction is a 2x2 matrix that is a
permutation matrix; and a couple refers to the pair of zeros in the
obstruction.
50
Looking at the adjacency matrix in Example 4.1, it is clear that an obstruction does
not exist. In fact, since the successor sets are linearly ordered, one can see that an
obstruction can never occur in Ferrers digraphs.
Definition: A graph H(D) is a graph whose vertices correspond to the zeros of
A(D), with 2 vertices joined by an edge if the corresponding zeros
belong to an obstruction.
Example 4.3: 1 2
D: y
3
Figure 4.5
A(D):
Label the zeros as vertices:
1. 2 3
1 0 1 0
2 1 0 1
3 0 1 0
1 2 3
1 a 1 b
2 1 c i
3 d 1 e
obstruction
These vertex pairs making edges in H(D) are called couples.
51
Then identify each obstruction and place an edge between the 2 vertices in
that obstruction.
Hence H(D):
a
b \ \
d' / /
e
Figure 4.6
In theorem 4.3 below, the proof of C= A is due to the following theorem by Cogis
[2].
Theorem 4.2 A digraph D has Ferrers dimension less than or equal to 2 if and
only if H(D) is bipartite.
Example 4.4: Since Example 3.8 from the preceding proof is an interval digraph,
then it has Ferrers dimension < 2. According to the above theorem, H(D) is
bipartite.
Take the adjacency matrix of D:
1 2 3 4
i ' 1 1 0 1 '
2 1 1 0 1
3 1 0 1 0
4 0 0 0 0
52
And label the zeros to be the vertices of H(D):
1 2 3 4
1 1 1 a 1
2 1 1 i 1
3 1 c l d}
4 e / 8 h
obstruction
Then H(D) is bipartite.
Figure 4.7
Recall from theorem 4.1 that all interval digraphs are the intersection of two Ferrers
digraphs. So the minimum number of Ferrers digraphs whose intersection is D is at
most 2, i.e., all interval digraphs have Ferrers dimension at most 2.
Theorem 4.3 [18] The following conditions are equivalent.
A) D has Ferrers dim <,2.
B) The rows and columns of A(D) can be permuted so that no 0 has a 1 both
below it and to its right.
C) The graph H(D) of couples in D is bipartite.
Looking at the example used above, D is an interval digraph, therefore D has
Ferrers dim at most 2. From the previous proof, Fv F2 are Ferrers digraphs whose
53
intersection is D and Av A2 are their adjacency matrices, each permuted so that the
O's are in the lower left and upper right respectively. Renumber the rows of
permuted Ax and the columns of permuted A2.
4 2 1 3
l = 4 1 1 1 1
A'(Fj) : u2 = 1 1 1 1 1 A(F2): 4
3 = 2 1 1 1 1 1
2
M4 = 3 0 0 1 1 3
W2 "3 W4
1 4 2 3
0 0 0 0
1 1 1 0
1 1 1 0
1 1 1 1
Now put the rows of A(D) in the order 4 and the columns in the order
wv...,w4.
1 2 4 3
1 1 1 1 0
: 2 1 1 1 0
4 0 0 0 0
3 1 0 0 1
Since fl F2 = D, then where A(D)(m.w.)=0 so must either A^tiw^ = 0 or
A2(ufw) = 0. If Ax(tiw}) = 0 then Ax(u\Vj) = 0 for all r > i as the zeros of Ax
are in the lower left. Then A(D)(rivj)=0 for all r > i. Hence, if A(D)(tt.vr)=0
then there will be only zeros below it.
Similarly, if A2(uw.) = 0 then A2(uwr) = 0 for all r > j and A(D)(.M'r)=0
r > j. So if A(D)(.w/)=0 then there will be only zeros to its right.
54
Therefore, the rows and columns of A(D) can be permuted so that no 0 has a 1 both
below it and to its right.
Now, beginning with permuted A(D) (as above) such that no 0 has a 1 both below
0 1
it and to its right, then 2x2 permutation matrices of the form
1 0
leaving only
0 1
1 0
cannot exist,
as possible obstructions. Label the zeros of A(D) as vertices
of H(D) and place an edge between 2 vertices only if their corresponding O's are in
an obstruction. Then label the O' s of A(D) with a 1 below them as R and the zeros
with a 1 to their right as C. Clearly, each obstruction will have an R and a C.
Hence, the only edges of H(D) will be between a vertex corresponding to an R and
a vertex corresponding to a C. Therefore, H(D) is bipartite with possible isolated
vertices. This much is left to the reader to verily.
1 2 4 3 1 2 4 3
1 1 1 1 a i 1 1 1 R '
A'(D): 2 1 1 ~'b. A'(D): 2 1 1 1 R
4 c d e> [f  obstruction 4 R 0 0 R
3 1 g ,h i: 3 1 C c 1
In the above example, the two zeros not labeled could be R's or C's, but since they
are not part of any obstruction, they do not affect H(D).
This exemplifies precisely those methods used to prove A = B = C. For C = A,
please see [2].
All interval digraphs have Ferrers dim < 2, but it remains to ask if all digraphs with
Ferrers dim ^ 2 are interval. The answer is no as the following theorem states.
55
Theorem 4.4 [18] The interval digraphs are properly contained in the set of
digraphs with Ferrers dimension at most 2.
In the following adjacency matrix of a digraph D, no 0 has a 1 both below it and to
its right. So D has Ferrers dimension at most 2.
vl. V2 V3 V4 V5 v V7
VJ ' 1 1 1 0 0 0 0
V2 1 1 1 1 1 0 0
V3 1 1 1 1 1 1 0
V4 0 1 1 1 1 1 1
V5 0 1 1 1 1 0 1
V6 0 0 1 1 0 0 0
V 0 0 0 1 1 0 1
However, it is not possible to label the zeros with R's and C's as stipulated in
Theorem 4.1 above.
A(D):
V1 v2 V3 V4 V5 V6 V7
V! 1 1 1 R R R R
V2 1 1 1 1 1 R R
V3 1 1 1 1 1 1 R
V4 c 1 1 1 1 1 1
V5 c 1 1 1 1 C 1
V6 c c 1 1 R 0 R
V7 c c c 1 1 c 1
56
It can be shown that the zero in the v6v6 position must be both a C and an R.
Therefore, although D has Ferrers dimension at most 2, D is not an interval
digraph. For a proof of this, please see [18].
57
5 Other Characterizations
Families of sets other than intervals on the real number line, have interested graph
theorists. Consider, for example, an intersection graph where the sets are arcs on a
circle. These are called circulararc graphs. Is there a generalization to digraphs;
and if so, what is known about them? Asteroidal triples, the absence of which
plays a part in identifying interval graphs, have a counterpart for directed graphs.
The following is a brief overview of these topics and others taken from recent
literature having to do with interval digraphs.
5.1 Relating Interval Graphs to Interval Digraphs
If it is known that a graph G is an interval graph, what is known about its
corresponding digraph? When that digraph is obtained by adding l's to the
diagonal of A(G), then D is called a symmetric digraph with loops and something
very specific is known about it.
Theorem 5.1 [19] A graph G is an interval graph if and only if the corresponding
symmetric digraph with loops is an interval digraph.
Proof: Necessity Assume G is an interval graph with each vertex v assigned
interval 7v. Let Sv = Tv = Iv thereby giving an interval representation of D(G).
58
Sufficiency Assume D(G), a symmetric digraph with loops, is an interval digraph
with interval representation: {(Sy,Ty)\ v e V(G)} where Sv = [av,6v] and
Tv = [cy,dv]. If m <> v in D(G) then both Sv fl Tu and Su fl Ty will not be empty,
a <. d coid. c <, b a,+c<,d+b
leading to the following inequalities: v u ,v =* v
s dvand cv bu au + cu z dv + bv
For G, the underlying undirected graph without loops, let 7v = [ay + cv, by + dy].
Then the above implies 7v H 7u is not empty so that vu is an edge of G as needed.
a > d
If u*f>v in D(G) then both Sy fl Tu and Sa fl Ty are empty, implying v > or
c > b
" , Together these lead to the following inequalities:
c > b
V u
(1) Either a > d and a > d or c > b and c > b
v/ v ti u v a v v u
(2) Either a > d and c > b or a > d and c > 6
V/ V U V U U V tt V
But u and v both have loops which means that Sy fl Ty and Sa fl Tu are not empty,
thus implying v
au
<. d and c
V V
< d and c
~ ** u ^ U
< b
V
^ b
u
When this is coupled with (1) above contradictions are the result:
< a
V
< C
u
<. d < a
V U
< b < c
* du
* K
So (2) implies ay + cy > da + bu and au + c> dy + by which means Iy fl Iu is
empty so mv,vu $ E(G).
Therefore, G is an interval graph.
59
5.2 CircularArc Digraphs
An intersection graph where the families of sets are arcs on a circle are called
circulararc graphs and are used to model traffic flow through intersections. If the
families of sets are ordered pairs of arcs on a circle, then the intersection graph is a
circulararc digraph.
In Chapter 2, we saw that Z4, a circuit on 4 vertices, wasn't an interval graph.
However, Z4 can easily be represented as a circulararc graph.
The same argument that was used to show Z4 had no interval assignment shows that
D below doesn't have one either, and therefore is not an interval digraph.
ICO
Figure 5.1
Figure 5.2
60
However, D can be represented by ordered pairs of arcs on a circle. Therefore, D
is a circulararc digraph.
Figure 5.3
Sen, Das and West, in their paper CircularArc Digraphs: A Characterization, give
characterizations for circulararc digraphs corresponding to those in [18] for
interval digraphs. For example, in Section 3.2 an analogy of the consecutive ones
property for interval graphs was made to interval digraphs in two parts:
consecutive ones property for intervalpoint digraphs and a general consecutive ones
property. These authors give similar statements for circulararc digraphs in the
following theorems.
Definition: A 0,1matrix has the circular ones property for rows if its columns
can be permuted so that the ones in each row are consecutive when
we view the positions as a cycle, with the first column following the
last.
61
Theorem 5.2 A digraph D has an intersection representation by circular arcs in
which all terminal arcs are single points if and only if its adjacency matrix has the
circular ones property for rows.
Theorem 5.3 D is a circulararc digraph if and only if there is a numbering of the
GBs in some covering B of D that exhibits the circular ones property for rows for
both the V,Xmatrix and V, Ymatrix of B.
In fact, except for the word interval being replaced with circulararc, these
theorems are exactly the same as their counterparts for interval digraphs. The
reader is referred to [19] for the proofs and further discussion. The following
theorem is included for completeness as it is used to prove theorem 5.5 below.
Theorem 5.4 A digraph D is a circulararc digraph if and only if the rows and
columns of its adjacency matrix can be permuted independently so that the resulting
matrix has the generalized circular ones property.
The authors define a stair partition of a 0,1matrix to be some partition of its
elements into two sets (L,U) such that U corresponds to the nonzero positions in
some upper triangular matrix and L to the nonzero positions in some lower
triangular matrix. Then a graph has the generalized circular ones property if it has
a stair partition (L,U) such that all of its ones are covered by V. and IF., where V.
consists of the ones in row i that begin at the stair and continue rightward until the
first 0 is reached and W consists of the ones in column j that begin at the stair and
62
continue downward until the first 0 is reached.
The theorem that I found most interesting in this paper was the following which
states that the compliment of any interval digraph is a circulararc digraph.
Theorem 5.5 The complement of any digraph with Ferrers dimension at most 2 is
a circulararc digraph.
Proof: Let D be a digraph with Ferrers dimension at most 2. Then by theorem 4.3
we know the rows and columns of A(D) can be permuted so that no 0 has a 1 both
below and to its right. Take the complement and reverse the order of the rows and
the order of the columns. Then in the resulting adjacency matrix of the compliment
of D, no 1 has a zero both above it and to its left. Let the matrix have stair
partition (L,U) where the entire matrix is U. Then the ones in A'(D) can be
covered as follows. A 1 in the i,j position with no 0 to its left belongs to V.. A 1
in i,j position with no 0 above it belongs to W Then all the ones will be covered
by the V/s and W.'s.
Therefore, A\D) has the generalized circular ones property, so by theorem 5.4, D
is a circulararc digraph.
Example 5.1: Since we know D from Example 3.8 is an interval digraph, we will
see if D is a circulararc digraph. Start with A'.(D) above where the rows
and columns have already been permuted so that no zero has a 1 both below
it and to its right, and take its complement.
63
1 2 4 3 1 2 4 3
1 1 1 1 0 1 0 0 0 1
A'(D): 2 1 1 1 0 A(D): 2 0 0 0 1
4 0 0 0 0 4 1 1 1 1
3 1 0 0 1 3 . 0 1 1 0
Then reverse the order of the rows and the columns.
3
A'(D): 4
2
1
3 4 2
0 1 1
1 1 1
1 0 0
1 0 0
1
0
1
0
0
The ones in row 4 will be covered by V4, those in column 3 will be covered by
W3, and the last two ones in row 3 can be covered by V3. Then there exists some
circulararc assignment for D pictured below.
1 2
A possible circulararc representation is below.
Figure 5.5
64
5.3 Other Generalizations
Although the idea of interval digraphs is a recent one, there have been several
papers written which draw further analogies to interval graphs. A brief summary of
those investigations follow.
A triple of vertices u, v, w of a graph is called asteroidal if there are chains C,
between u and v, C2 between u and w and C3 between v and w so that there is no
edge from uto C3, from v to C2 or from w to Cx. Erich Prisner, in his work, A
Characterization of Interval Catch Digraphs [13], defines a diasteroidal triple in
much the same way except that in each of the three x,ychains, there is no vertex
that is an initial endpoint of an arc preceding vertex z. He points out that a digraph
has a diasteroidal triple if and only if its underlying undirected graph contains an
asteroidal triple.
Lekkerkerker and Boland, 1962 (please see Roberts [16]) extend the Z4 property for
interval graphs by including asteroidal triples. They prove that a graph is an
interval graph if and only if it does not have any Zn, n^ 4 as a generated subgraph
and it has no asteroidal triples. Prisner gives an analogous characterization for
interval digraphs when he proves that a digraph is an interval catch digraph if and
only if it has no diasteroidal triple.
Among the relationships between intervals on the real number line, that of
containment has been investigated with regard to interval digraphs. In [21] an
65
interval containment digraph is an interval digraph where the terminal sets are
properly contained in the source sets whenever Su and Tv intersect. They prove
that a digraph is an interval containment digraph if and only if it has Ferrers
dimension at most 2.
They also extend this concept to circulararcs by defining a circulararc containment
digraph to be a digraph where the ordered pairs (Su,Tv) are arcs on a circle and
there is an edge from u to v if and only if Su properly contains Tv. They show
that a digraph is a circulararc containment digraph if and only if its complement is
a circulararc digraph.
Finally, the last in this summary is a paper by Harary, Kabell and McMorris [8]
investigating acyclic interval digraphs. They show that a labeling of the vertices
v...,v of D such that whenever v.v. is an edge, then i< j, and for all k with
i < k < j, vvk is also an edge is both necessary and sufficient to being an interval
acyclic digraph. They extend this property to include interval digraphs where all
the intervals are of unit length. And they describe three forbidden induced
subdigraphs for interval acyclic digraphs and two forbidden induced subdigraphs for
unitinterval acyclic digraphs.
66
6 Conclusion
This survey is by no means exhaustive. Other work has been or is being done with
interval digraphs, and there are many areas that are still open for new research.
Certainly there are more categories of interval and intersection graphs to which
analogies could be drawn for digraphs. Areas for future investigation could include
the following topics.
Tolerance graphs are interval graphs where xy is an edge in G only when the
intervals corresponding to x and y overlap by some specified positive value. This
way, two intervals can overlap at under the tolerance amount and this will not result
in an edge. Are there any interesting generalizations to be made by considering
pairs of intervals for each vertex where xy is an edge in D if and only if the source
interval for x and the terminal interval for y overlap at least the tolerance amount?
What kinds of applications could this have?
Some work has been done linking competition graphs to interval graphs, but there
is more to be learned in this area. For example, what can be said about the
competition graphs of interval digraphs in general? The digraph that was used to
illustrate several of the concepts presented in this paper is an interval digraph
(Fig.4.3). What does its competition graph look like? By definition, the
67
competition graph of D has the same vertex set as D and xy is an edge if and only
if xc and yc are both edges in D. Hence, C(D) would have edges (1,2), (2,3) and
(3,1) and vertex 4 would be isolated. In this case, the competition graph of D is an
interval graph, but is this always the case? What do competition graphs of interval
digraphs look like in general? And is an interval graph the competition graph of
some interval digraph?
Lastly, what might be said about the applications of interval digraphs? Are there
any; and if so, do they differ from the applications for interval and intersection
graphs?
68
BIBLIOGRAPHY
[1] Biro, M., Hujter, M., Tuza, Zs., Precoloring extension. I. Interval graphs,
Discrete Math., Vol. 100, 267279, 1992.
[2] Cogis, O., A characterization of digraphs with Ferrers dimension 2, Rap.
Rech. 19, G.R. CNRS, 22, Paris, 1979.
[3] Cogis, O., Ferrers Digraphs and Threshold Graphs, Discrete
Mathematics, Vol. 38, 3346, 1982.
[4] De Caen, D., Gregory, D.A., Pullman, N.J., The Boolean Rank of Zero
One Matrices, Proc. 3rd Car. Conf. Comb, and Comp., 169173.
[5] Eckhoff, J., Extremal Interval Graphs, Journal of Graph Theory, Vol. 17,
No. 1, 117127, 1993.
[6] Gimbel, J., End Vertices in Interval Graphs, Elsevier Science Publishers,
1988.
69
[7] Golumbic, M.C., Monma, C.L., Trotter, Jr., W.T., Tolerance Graphs,
Discrete Applied Math., Vol. 9, 157170, 1984.
[8] Harary, F., Kabell, J.A., McMorris, F.R., Interval Acyclic Digraphs, to
appear.
[9] Jachowski, Z., A new characterization of proper interval graphs, Discrete
Math,, Vol. 105, 103109, 1992.
[10] Jacobson, M.S., McMorris, F.R., Scheinerman, E.R., General results on
tolerance intersection graphs, Submitted to Journal of Graph Theory.
[11] Lundgren, J.R., Rasmussen, C.W., Maybee, J.S., Interval competition
graphs of symmetric digraphs, Discrete Mathematics, Vol. 119, 113122,
1993.
[12] Marathe, M.V., Ravi, R., Rangan, C.P., Generalized vertex covering in
interval graphs, Discrete Applied Math., Vol. 39, 8793, 1992.
[13] Prisner, E., A Characterization of Interval Catch Digraphs, Discrete
70
Mathematics, Vol. 73, 285289, 1989.
[14] Raychaudhuri, A., Optimal multiple interval assignments in Irequency
assignment and traffic phasing, Discrete Applied Math., Vol. 40, 319
332, 1992.
[15] Raychaudhuri, A., Roberts, F.S., Generalized Competition Graphs and
Their Applications, Methods of Operations Research, Vol. 49, 295311,
1985.
[16] Roberts, F.S., Discrete Mathematical Models, PrenticeHall, Inc., 1976.
[17] Scheinerman, E.R., An Evolution of Interval Graphs, Discrete Math.,
Vol. 82, 287302, 1990.
[18] Sen, M., Das, S., Roy, A.B., West, D.B., Interval Digraphs: An
Analogue of Interval Graphs, Journal of Graph Theory, Vol. 13, No. 2,
189202, 1989.
71
[19] Sen, M., Das, S., West, D.B., CircularArc Digraphs: A
Characterization, Journal of Graph Theory, Vol. 13, No. 4, 581592,
1989.
[20] Sen, M., Sanyal, B.K., Indifference Digraphs: A Generalization of
Indifference Graphs and Semiorders, SIAM Journal of Discrete Math.,
Vol. 7, No. 2, 157165, 1994.
[21] Sen, M.K., Sanyal, B.K., West, D.B., Representations of Digraphs Using
Intervals and Circular Arcs, Submitted to Discrete Math.
\
[22] Trotter, Jr., W.T., Harary, F., On Double and Multiple Interval Graphs,
Journal of Graph Theory, Vol. 3, 205211, 1979.
72

PAGE 1
INTERVAL DIGRAPHS: A GENERALIZATION OF INTERVAL GRAPHS by Roxanne Drachenberg B.S., B.A., Regis University, Denver, Colorado, 1988 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1994
PAGE 2
This thesis for the Master of Science degree by Roxanne Drachenberg has been approved for the Graduate School by I :_/z Uy 1 I Date
PAGE 3
Drachenberg, Roxanne (M.S., Applied Mathematics) Interval Digraphs: A Generalization of Interval Graphs Thesis directed by Professor J. Richard Lundgren ABSTRACT Intersection graphs, and in particular, interval graphs have been extensively studied; however, intersection and interval digraphs have only recently been the subject of research. This is a survey of those results for intersection and interval digraphs that are analogous to known characteristics of intersection and interval graphs. For example, the well known consecutive ones property for interval graphs, when generalized to interval digraphs, divides into two cases, both of which are proven. In addition to analogies drawn from interval graphs, other results identifying interval digraphs are examined. For instance, Ferrers digraphs and Ferrers dimension are defined and results linking them to interval digraphs are illustrated. Finally, results regarding other families of sets such as circulararcs are discussed. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed J. Richard Ill
PAGE 4
Contents 1 Introduction ....................................... 1 2 Interval Graphs ..................................... 3 2.1 History ..................................... 3 2. 2 Characterizations of Interval Graphs . . . . . . . . .. 4 2. 2.1 Maximal Cliques .................... 2.2.2 Z4 is Not a Generated Subgraph ... 5 8 2.2.3 G' is Transitively Orientable. . . . .......... 10 3 Interval Digraphs .................................. 12 3.1 Intersection Digraphs. . . . . . . . . . . . 12 3.1. I Intersection Number and Biclique Cover Number. 15 3.1.2 Importance of Loops. . . . . . . . . . . 20 3. 2 Interval Digraphs. . . . . . . . . . . . . . . 22 3.2.1 Consecutive Ones Property for IntervalPoint Digraphs 23 3.2.2 Consecutive Ones Property for Interval Digraphs in General ................................... 28 4 Ferrers Digraphs ..................................... 35 4.1 Preliminaries ....... . ...................... 35 IV
PAGE 5
4. 2 Adjacency Matrices and Ferrers Digraphs .................. 39 4. 3 Adjacency Matrices and Ferrers Dimension ................ 50 5 Other Characterizations .................................. 58 5.1 Relating Interval Graphs to Interval Digraphs ............... 58 5.2 CircularArc Digraphs ............................. 60 5.3 Other Generalizations .............................. 65 6 Conclusion ........................................... 67 Bibliography ........................................... 69 v
PAGE 6
1 Introduction Interval graphs have been extensively studied since their inception in 1959. It has only been recently, however, that graph theorists developed an interest in interval digraphs. This paper develops the foundations and presents a survey of the work completed in the area of interval digraphs. Since interval digraphs have their roots in interval graphs, this discussion begins with the latter. Interval graphs are defined and some of their characterizations are discussed and illustrated in Chapter 2 in order to provide a basis for interval digraphs. Knowing how interval graphs are characterized motivates interest in discovering if those same characterizations are true for interval digraphs. In Chapter 3, analogous results are given for intersection digraphs, including the intersection number and how this relates to the biclique cover number of a digraph. As opposed to intersection graphs, loops do occur in intersection digraphs: therefore, digraphs with loops are investigated. Also in this chapter the consecutive ones property, a wellknown result for interval graphs, is generalized to interval digraphs by considering two incidence matrices instead of one, one matrix for the source intervals and one matrix for the terminal intervals. Characterizations beyond those known for interval graphs are examined' in the
PAGE 7
remaining chapters. In particular, Ferrers digraphs and Ferrers dimension are defined in Chapter 4 and necessary and sufficient conditions for a digraph to be interval are given. One of those results being that a digraph is interval if and only if it is the intersection of two Ferrers digraphs whose union is complete. Chapter 5 contains a brief overview of results found in the current literature. We prove a theorem stating that a graph is interval if and only if its corresponding symmetric digraph with loops is interval. Circulararc digraphs are studied as the generalization of circulararc graphs. Much of the work done regarding these digraphs is analogous to that which is described in Chapter 3 regarding interval digraphs. A statement which implies that the complement of an interval digraph is a circulararc digraph is verified. Catch digraphs, containment digraphs and circulararc containment digraphs are briefly mentioned also. Finally, open questions regarding other possible generalizations of interval graphs are posed in Chapter 6. 2
PAGE 8
2 Interval Graphs 2.1 History Since interval digraphs are an outgrowth of interval graphs, we begin with a discussion of interval graphs, which are a special kind of intersection graph. Definition: Given a family of sets, each set assigned to a vertex, the intersection Jm!l2h of the family of sets has an edge between two distinct vertices if and only if the corresponding sets intersect. What kinds of graphs does this describe? From a theorem by Marczewski, 1945 [ 16] we know all graphs are intersection graphs. So intersection graphs only become interesting when one looks at different kinds of families of sets. The focus here is on families of intervals on the real number line. Definition: A graph G is an interval graph if it is the intersection graph of some family of intervals on the real number line. Interest in intersection graphs of families of intervals on the real number line began with a problem in genetics called Benzer' s problem. (See Roberts [ 16] for a description of this problem.) Benzer mapped the substructure of the gene to 3
PAGE 9
intervals on the real number line which supported his hypothesis that the structure of the gene is linear. Genetics was the beginning, but the applications for interval graphs are limited only by our imaginations. Interval graphs can be used to model one's indifference between alternative choices. They have been used to chronologically order artifacts in archaeology and characteristics in childhood development. Applications also exist in transportation models of the phasing of traffic lights and in ecology to model food webs [16[. 2.2 Characterizations of Interval Graphs Interval graphs are relatively easy to identify. The following characterizations found in Roberts [ 161 not only tell us some things about what interval graphs look like, they also give us information about their maximal cliques, their complements and their vertexclique incidence matrices. I. [Fulkerson & Gross, 1965] A graph G is an interval graph if and only if there is a ranking of the maximal cliques of G which is consecutive. II. A graph G is an interval graph if and only if the columns of its vertexclique incidence matrix can be permuted so that the ones appearing in any row appear consecutively. (This is a restatement of I due to Roberts [16].) 4
PAGE 10
III. [Gilmore & Hoffman, 1964] A graph G is an interval graph if and only if it satisfies the following conditions. a) Z4 is not a generated subgraph of G, and b) G' is transitively orientable. The interest here is not in the proofs of these theorems, but in understanding how and why these characterizations interrelate to each other and describe interval graphs. To this end, in the following subsections examples are used to illustrate these properties. 2 'i '. I '"' . i '/I ::::1 9 4 s 6 8 Figure 2.1 Graph A 2.2.1 Maximal Cliques First of all, a clique is a complete sub graph and a maximal clique is a complete subgraph that is not contained in a larger clique. For graph A above the maximal cliques are as follows. 5
PAGE 11
1 7 8 1 K 3 7 K. 1 K, K2 Figure 2.2 Maximal cliques of A 9 10 To consecutively rank the cliques simply means that whenever u is in K, and Ki fori < J, then for i < r < j, u E K,. So we can easily find a ranking for graph A to be K5 K6 K4 K3 K2 K1 It is easy to see how this can be restated in terms of consecutive ones in the vertexclique incidence matrix of A. Since consecutively ranking the maximal cliques by definition is to insure that any vertex appearing in more than one clique will be in consecutive cliques, then the incidence matrix will have consecutive ones. The connection between maximal cliques and interval graphs is clear when the maximal cliques are renumbered in order of their ranking as shown in the incidence matrix below. Assign each vertex the interval [i.j] where K, is the first clique and K. is the last clique to which that vertex belongs. For example, vertex 1 is J assigned the interval[! ,4] and so on. A quick check will confirm that this assignment works. Since intervals on the real number line must be consecutive, then consecutive ones means the graph is an interval graph. 6
PAGE 12
Kt K2 K, K, K, K, K, K, 1 1 1 1 1 2 0 1 1 0 3 1 1 0 0 4 1 0 0 0 5 1 0 0 0 6 0 0 0 1 7 0 0 1 1 8 0 0 0 0 9 0 0 0 0 10 0 0 0 0 VertexClique Incidence Matrix [2.3] [6] 2 1 [3.4] 7 9 [6] [1] 4 5 [1] Figure 2.3 Interval assignment for graph A K, K6 new numberlng K, Kt 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 The following graph is a cycle on 4 vertices where its 4 maximal cliques cannot be consecutively ranked. Vertices 1,2 and 3 each belong to consecutive diques; however, vertex 4 is in K 1 and K 4 which are clearly not consecutive. 7
PAGE 13
Renumbering the cliques won't change the fact that they can't be ranked consecutively. Neither can the ones be consecutively arranged in each row of its incidence matrix: 1 1 1 0 0 2 0 1 1 0 3 0 0 1 1 4 1 0 0 1 _______ .. 2 K, K, Figure 2.4 A cycle on 4 vertices Therefore, this is not an interval graph which leads us to the next property. 2.2.2 Z4 is Not a Generated Subgraph A generated subgraph of a graph G is a subset of the vertices of G along with all edges of G connecting those vertices; and, Z4 is a cycle of length 4. Z4 itself is not an interval graph. This is most easily demonstrated by trying to find an interval assignment. Assign vertex 1 the interval 1(1), and so on for all of the vertices. Then 1(2) must intersect with 1(1), 1(3) must intersect with 1(2) but not with 1(1). 1(4) must intersect with 1(3) and not with 1(2). But 1(4) must also intersect with 1(1). Clearly, no matter what vertex you begin with, the result will be the same. 8
PAGE 14
E 1 E ] [ 3 ] [ 4 ] [ 4 ] Figure 2.5 Attempted interval assignment for 4cycle Thus an interval assignment cannot be found. So if a graph contains Z4 as a generated subgraph, it is not an interval graph. The following example. however, illustrates that this condition is not, by itself, sufficient in order to have an interval graph. 5 7 Figure 2.6 Graph B with its maximal cliques 4 2 Graph B has no Z4 but its maximal cliques cannot be consecutively ranked and it doesn't have the consecutive ones property. Therefore, it cannot be an interval graph. 9
PAGE 15
2.2.3 G' is Transitively Orientable G' refers to the complement of G, a graph on the same vertex set as G that contains all the edges not contained in G. A transitive orientation Q, of a graph G is an assignment of direction to the edges of G such that if ah is an edge in 0, and be E E( Q), then ac E E( Q). Graph B above, in fact, does not have a transitively orientable complement It is left to the readers to satisfy themselves that this is the case. 2 Figure 2. 7 An orientation of the complement of graph B Why is the complement of an interval graph transitively orientable? Consider the complement of an interval graph. Each vertex has an interval assigned to it and an edge exists if and only if two intervals DO NOT intersect Then these intervals can be ordered. For example, the interval assigned to vertex u might be less than the interval assigned to vertex v. Orient the edges of G' from u to v whenever 10
PAGE 16
I(u) < I(v). If I(u) < l(v) and l(v) < l(w), then l(u) < /(w) so the orientation will be transitive. To summarize, interval graphs are identifiable by examining their maximal cliques, their vertexclique incidence matrices, their complements and their generated subgraphs. Are any of these properties transferable to interval digraphs? Are there other characterizations of interval digraphs? These are the questions dealt with in the next chapter. Also, there are intersection graphs of other families of sets that are of some interest. Although not mentioned with regard to interval graphs at this point, they will be discussed later. I l
PAGE 17
3 Interval Digraphs 3.1 Intersection Digraphs Interest in interval digraphs began when Sen, Das, Roy and West, in their work Interval Digraphs: An Analogue of Interval Graphs introduced analogies between interval graphs and their characterizations and interval digraphs [ 18]. They established a basis of definitions and theorems from which others have expanded. To begin, we saw in Chapter 2 that interval graphs are a special case of intersection graphs. So before discussing interval digraphs, the first step is to find out if there is an analogue to intersection graphs for directed graphs. There is. In fact the idea is easily transferred to digraphs by letting an ordered pair of sets, instead of one set as with graphs. correspond to each vertex. Definition: Given a family of ordered pairs of sets consisting of a source set, s. (head) and a terminal set T (tail), assign each vertex an ordered pair of sets. The intersection digraph, D(V, E), is the digraph such that uv is an edge of D if and only if s. n r. 0 where loops are allowed but multiple edges are not. 12
PAGE 18
Example 3.1: This example illustrates how each vertex is assigned an ordered pair of sets, and how this results in an intersection digraph. Let vertices 1 through 5 have the following set assignment. vl: sl = { 1,2,3 ,4}, Tt {2,5,7} vz: s, = {1,3,6}, r, { 1,3,9} v3: s, = {7 ,8,9}, r, {2} v4: s, {3,8,11 }, T, = {3,5} vs: s, { 1,5}, T, = { 1,2 ,3} S 1 n T1 0, therefore edge 1, 1 exists (a loop at vertex 1) S1 n T, 0, therefore edge l ,3 exists and so on. Thus Dis constructed. D: 4 3 Figure 3.1 Notice that loops will occur, but multiple edges are disallowed by definition. As previously mentioned, every graph is an intersection graph; but is the same true for digraphs? In fact, the answer is yes. Label the edges of a digraph 1,2, ... ,m. 13
PAGE 19
Let the source set of each vertex correspond to the set of out edges and the terminal set equal the set of in edges of that vertex. This results in a collection of sets whose intersection is the given digraph. Therefore, it is an intersection digraph. More formally, Theorem 3.1 Every digraph D=(V,E) is the intersection digraph of some family of sets. Proof: Let S. consist of the edges of D such that vu is an edge of D and T. consist of the edges of D such that uv is an edge of D, for all v E V(D). Then s. n T. e if and only if there exists an edge ttv E E(D) implies there will be an edge in the intersection digraph. :. Every digraph is the intersection digraph of some family of sets. Example 3.2: S,=(l} T,=(} S, {3} T,= (2} V< "' 2 s, = {2} 3 v 5 T, = {1,5} 4 S,={4,5}T,={} S,={}T,={3,4} Figure 3.2 14
PAGE 20
3.1.1 Intersection Number and Biclique Cover Number Definition: The intersection number iiGl of an undirected graph G is the minimum size of a set U such that G is the intersection graph of subsets of U. The following example illustrates this concept. Example 3.3: s.PI s,"" {1,2} s, {2,4} G: I I 4 6 s,"' {l} ={1.3} s, = {3,4} Figure 3.3 In graph G above, if S1 = {I}, then s,. s, and S4 must also contain 1 as these four vertices are adjacent. Vertices 5 and 6 are not adjacent to 1 and 3; therefore, their assigned sets cannot contain l. However, 5 is adjacent to 2, so we can add 2 to both sets. Continuing in this manner, we find it takes four different numbers assigned to the vertices to ensure that all of the edges of G are accounted for, and there are no additional edges included. Thus U={l,2,3.4} is minimum and i(G)=4. 15
PAGE 21
Erdos, Goodman and Posa, in The Representation of a Graph by Set Intersections, !966, prove that the intersection number of a graph is equal to the minimum number of complete subgraphs needed to cover a graph's edges [ 18]. In the above example, it will take a minimum of four cliques to cover the edges, which equals the intersection number of G, for digraphs, the following definition is virtually the same as for its counterpart; however, to talk about covering the edges of an intersection digraph, we need an additional definition. Definition: The intersection number. i(Dl, of a digraph is the minimum size of U such that D is the intersection digraph of ordered pairs of subsets of U. Definition: A generalized biclique (abbreviated GBl is a subdigraph generated by vertex sets X and Y. not necessarily disjoint, whose edges are all xy such that x E X and y E Y. Since X and Y may not be disjoint, loops are possible. So "generalized" refers to the fact that the sets X and Y are not necessarily disjoint. The analogue to Erdos, Goodman and Posa' s result for graphs is below. Theorem 3.2 [Sen, Das, Roy, West, 1989] The intersection number of a digraph equals the minimum number of GB' s required to cover its edges, and the best possible upper bound on this is n for nvertex digraphs. 16
PAGE 22
Proof: In order to prove this equality, we need to show (l) minimum #(GB) 2 i(D) and (2) minimum #(GB) s: i(D). Suppose P"P,, ... ,P, is a minimum collection of GB's whose union is D. where P, = {(X,Y,)}. LetS,= {ijv EX,} and let T = {i'1v E Y }. Thus S n T 0 if and only if uv E E(D). In other words, V I U V the source set for vertex v is the set of all GB' s containing v in its X set, and the terminal set for vertex v is the set of all GB' s containing v in its Y set. Since there are k of these GB' s from which to form the ordered pairs, the numbers l ,2, ... ,k are used in their formation. Then since i(D) is the minimum size of U, i(D) s: k. Conversely, if Dis the intersection digraph of ordered pairs of subsets of U, then by definition 1 U I =i(D). Then for each vertex of D, we have an ordered pair (S,,T,) whose elements come from the set U = {l,2, ... ,i(D)}. We can t'ind i(D) GB's of D as follows. Let u E X = i E S and v E Y = i E T. Continue for 1 u 1 v all u,v E V(D). Since the elements of the source and terminal sets come from l,2 .... ,i(D), then there will be at most i(D) GB's constructed. Also. uv F. E(D) if and only if u EX and v E Y for some i, so the union of the GB's is D. ' Therefore, the minimum #(GB) = k ,; i(D). Thus. i(D) = k as required. As for the bound on i(D), note that the set of edges with v as the source vertex is a generalized biclique. Therefore, n distinct generalized bicliques would cover all the edges. So if each vertex were a source vertex for only one edge, i.e., a directed 17
PAGE 23
cycle of length n, it would taken disjoint GB's to cover D where each GB is composed of I edge only. Example 3.4: This example illustrates the steps of the proof. Vertices are labeled v1 to avoid confusing them with the is. I I I / '/ />)1 Figure 3.4 GB1 1 x, {v1,v4}, Y, {v2,v5 } s {i lv1 E X,} T {i I v1 E Y} vi vi GB,, x, = { v 2' v ,} Y, {v,} s { 1,5} T 0 vi v, GB3! x, {v ,}, Y, {v4,v6,v7 } s {2,6} T {I } v, v, GB4 1 x, { v 4' v ,} Y, = { v,} s T = 0 = {2} v, v, GB5! x, = {v,}, Y, { v,} s = { 1,4} T {3 ,5} v, v, GB6 : x, = { v ,} Y, {v,} s = {2,4} T { 1,6} v, v, s {3} T {3 ,4} v, v, s v, = 0 T v, {3} 18
PAGE 24
Example 3.5: This proof can be used to find the minimum sized intersection sets if it is known how many GB' s are needed to cover the edges, as this example shows. Or, if the minimum size of U is known, the proof will construct the generalized bicliques needed to cover the edges. Clearly i(D) =2 as it takes 2 GB' s to cover the edges. GBI: XI {1}, yl = {1,2,3} GB,: X, = {4}, Y2 {I} s = "1 s] = s, s, s, = {ilv EX.} 1 {I} Tt 2! r, 2! r, {2} r, G T = {i jv1 "1 = = {I ,2} {I} { I } 2! 2 I .. "'" 4 3 Figure 3.5 E Y,} 19
PAGE 25
3.1.2 Importance of Loops Loops do not occur in intersection graphs, but they can happen with digraphs since each vertex has a source and a terminal interval which can intersect. Therefore, it is important to examine how loops affect the intersection number of digraphs. Definition: Let D, be the complete digraph of order n with vertices {l,2, ... ,n} in which each ordered pair of vertices (i,j) i j, forms an arc of D . Definition: Let D; be the complete digraph of order n in which each ordered pair of vertices (i,J) including i = J, forms an arc of D;. Then since multiple edges are not allowed, there will be n loops, one loop per vertex. The intersection number of D; is l as is pictured below. Example 3.6: Figure 3.6 {1,2,3,4}, r, {1,2,3,4}. 20
PAGE 26
When loops are not allowed, the intersection number will be greater than I as X can no longer equal Y,. Without loops, the digraphs in question are simply D . To cover D., generalized bicliques are no longer needed as bicliques will do the job. De Caen, Gregory and Pullman [41 prove that the biclique cover number of a complete digraph on n vertices is equal to s(n), where s(n) = min {k : n ,; ( however, in [18] the claim is made that i(D.) = 21og2 j V j. The following chart compares s(n) to 21og ,n as IV 1 = n. k ( n s(n) 21og 2n 2 2 4 4 4 3 3 5 4 4.64 4 6 6 4 5.17 5 10 7 5 5.61 6 20 8 5 6 9 5 6.34 9 126 10 5 6.64 20 184 .756 100 9 13.29 100 .000 20 33.22 The chart suggests that 21og 2n is not accurate for n > 4 ; but so far as the above data goes, it is an upper bound. 21
PAGE 27
Example 3. 7: D, can be covered with 5 bicliques as is demonstrated below. XI = {2,4,6,8}, yl {1,3,5,7} x, = {1,2,3,4}, Y, = {5,6,7,8} x, = {1,5,6,7}, Y, = {2,3,4,8} x. {3,4,7,8}, r. (1,2,5,6} xs {2,3,5,8}, ys {1,4,6,7} 1 2 3 4 5 6 7 8 1 0 1 1 1 1 1 1 2 1 0 1 1 1 1 1 1 3 1 1 0 1 1 1 1 1 4 1 1 1 0 1 1 1 1 5 1 1 1 1 0 1 1 1 6 1 1 1 1 0 1 1 7 1 1 1 1 1 0 1 8 1 1 1 1 1 1 0 Therefore, i(D,) = 5. 3.2 Interval Digraphs Interval digraphs are a special case of intersection digraphs as was true for interval and intersection graphs, except now each vertex has two intervals assigned to it. Definition: An intersection digraph where each source set and terminal set is an interval is an interval digr;wh. 22
PAGE 28
Example 3.8: vi: sl [1 ,2] TI = [1 ,3] v s, = [1 ,3] T, [2] ,. v3: s, = [3 ,5] T, [5] 4 v4: s. [ 1,0 l r. = [1 ,2] Figure 3.7 As interval digraphs are a subset of intersection digraphs, all that has been stated thus far holds for interval digraphs; but, what further characterizations analogous to those for interval graphs can be made about interval digraphs? As was discovered in Chapter 2, interval graphs are characterized by the fact that the ones in the rows of their vertexclique incidence matrices can be arranged consecutively. The analogy for interval digraphs divides into two cases. 3.2.1 Consecutive Ones Property for IntervalPoint Digraphs Definition: Interval digraphs representable using singleton terminal sets are intervalpoint digr;whs. In other words, the terminal set is a single point, but the source set may not be. Theorem 3.3 [ 18] Dis an intervalpoint digraph if and only if its adjacency matrix has the consecutive ones property for rows. 23
PAGE 29
Proof: By definition, D has an intervalpoint representation if and only if there are source (S( v)) and terminal (T( v)) sets where the terminal sets consist of one point of a real number line, and ttv E E(D) if and only if S( u) n T( v) e Let S(v)=[a(v),b(v)] and T(v)=[c(v)]. Then uv E E(D) if and only if c(v) e S(u). We may assume the c( v)' s are distinct, as if two or more are the same, then there would be two or more duplicate rows in the adjacency matrix. As multiple edges are not allowed, the adjacency matrix A(D) will contain zeros and ones only. Number the vertices in increasing order of c( v). Then c( v) E S( u) is true if and only if the rows of A(D) exhibit the consecutive ones property because of the following. Assume the consecutive ones property doesn't hold for rows of the adjacency matrix of D. This implies there exists a vertex v such that if vu e E(D) 1 then vu1 1 $ E(D) and vur1 $ E(D) and either vu1 2 or vr11 2 E E(D). But u1 2 u1_1' u1.1' u1 1 are consecutive distinct c( v )' s which implies c( u) e S( v) and c( ur2 ) E S( v) but c( u1 _1 ) $ S( v ), a contradiction asS( v) is an interval on the real number line. Furthermore, by permuting the columns of A(D) so that all of the ones are consecutive, then relabeling the vertices according to this new column order, we can obtain an intervalpoint representation ofD as follows. Take c(v,)=k; a(v,)= min {ilv,v1 e E(D)} and b(v,) =max {ilv,v, E E(D)}. (This is the reverse of that which is found in [18!.) 24
PAGE 30
Example 3.9: The following exemplifies the steps of the proof. I original labeling 1' new labeling Figure 3.8 l 2 3 4 5 6 I 0 I 0 0 0 0 2 0 0 I I 0 0 A( D): 3 I 0 0 0 I .t 0 0 0 0 I 0 5 0 l 0 0 0 I 6 0 0 0 0 0 0 I' 2' 3' 4' 5' 6' l 5 6 2 3 4 I' I 0 0 0 I 0 0 4' 2 0 0 0 0 I I A'(D): 5' 3 I I I 0 0 0 6' 4 0 l 0 0 0 0 2' 5 0 0 I 0 0 3' 6 0 0 0 0 0 0 25
PAGE 31
Since the consecutive ones property holds, D is an intervalpoint digraph. Relabel the vertices, and use the theorem: So the following intervalpoint representation is gained. s = [4] T, = [ 1] 1 s, = [3 ,4] T, = [2] s, = 0 T, = [3] s, [5,6] T, = [4] s, = [1,3] T, [5] S. [2] T. [6] 0 0 This proof explains why the adjacency matrix of an intervalpoint digraph will exhibit the consecutive ones property. This. however, wasn't the case for interval graphs. Nor is it the case for interval digraphs in generaL Note in the following example from [18] that vertices 2,3 & 4 are adjacent to both 1 and themselves. Clearly the adjacency matrix will not exhibit the consecutive ones property no matter how the columns are permuted. 26
PAGE 32
Example 3.10: The smallest interval digraph that is not an intervalpoint digraph is below. I I ! Q Figure 3.9 2 3 Not only is it impossible to permute the columns of A(D) to get the ones in each row consecutive; but, it is also not possible to find an intervalpoint representation of D as demonstrated. If we proceed as in the proof by first setting T, = [i], then finding S( v ), a false interval representation occurs (F) because [I] 0 s, and [3] E s,. but if the single point intervals [II and [3] are contained in the interval corresponding to vertex 3, so must [2]. But that would make (3.2) an edge in D. which is not the case. Changing the order of the T 's will not affect the outcome. The correct representation is shown (T). 27
PAGE 33
s, = 0 T, = [I] s, 0 T, [1,3] s, = [1,2] T, = [2] s, = [!] T, = [ 1] F: T: s, [1 ,3] T, = [3] s, = [2] T, [2] s, [1,4] T, [4 J s, [3] T, = [3] 3.2.2 Consecutive Ones Property for Interval Digraphs in General In general, interval digraphs are characterized by a consecutive ones property for the rows of two pointset incidence matrices, where one matrix represents the source sets and the other one represents the terminal sets as defined below. For the following definitions, let B= {(X,,Y.)} be a collection of generalized bicliques whose union is D. Definition: The vertexsource incidence matrix forB, denoted V,Xmatrix, is the incidence matrix between the vertices and the source sets {X }. Example 3.11: The vertexsource incidence matrix forB= {(X,,Y,)} of the GB's described in Example 3.4 above is as follows. x, x, v, 1 0 v, 0 1 v, 0 0 V,Xmatrix: v, 1 0 v, 0 1 v6 0 0 v, 0 0 x, 0 0 0 0 0 I 0 28 x, 0 0 0 1 0 0 x, 1 0 0 0 0 0 0 0 0 0
PAGE 34
Definition: Similarly, the vertexterminus incidence matrix forB, denoted V, Ymatrix, is the incidence matrix between the vertices and the terminal sets {Y,}. Example 3.12: The vertexterminus incidence matrix forB= {(X,,Y,)} of the GB's in Example 3.4 is below. Y, Y, Y, Y, Y, y6 v, 0 0 0 0 0 0 v, 1 0 0 0 0 0 v, 0 1 0 0 0 0 V,Ymatrix: v, 0 0 1 0 1 0 vs 1 0 0 0 0 1 v. 0 0 1 1 0 0 0 v, 0 0 1 0 0 0 The following theorem is analogous to the consecutive ones theorem for graphs. Please note that instead of including all maximal generalized bicliques, only some subset of them such that D is covered are used. Theorem 3.4 [ 18] D is an interval digraph if and only if there is a numbering of the GB' sin some covering B of D such that the ones in rows appear consecutively for both the V,Xmatrix and V, Ymatrix of D. Proof: (): Consider such a B whose union is D, and let (X,,Y,) be a common numbering of the columns of the V,Xand V,Ymatrices that exhibits the 29
PAGE 35
consecutive ones property for both. Let the source and terminal intervals be S = [a ,b 1 and T = [c ,d 1 where a ,b ,c ,d are defined by v vv v ,, vvvv v E X, = a k <; b and v E Y, = c k d i.e., vertex v is in X, if and v v v v only if k is in the interval assigned to S, and v is in Y, if and only if k is in the interval assigned to T,. Then D is an intersection digraph where the source and terminal sets are intervals on the real number line; therefore, D is an interval digraph. (): Assume D is an interval digraph. Consider a representation of D by a family {(S,,T,)} of ordered pairs of intervals. We may assume the intervals are closed and have integer endpoints. LetS, = [a,,b,] and T, = [c,,d,J. For each integer k belonging to any of these intervals, define a generalized biclique B, = (X,,Y ,) as follows: Let X,= {vik S) and r, = (v!k E T). In other words, for each source set, S,, containing k within its assigned interval, that vertex v is in X,. Then these subsets (X,,Y ,), are generalized bicliques of D. As S u n T, 0 if and only if u c. x, and v s Y, for some k, then the intersection of these interval pairs is the union of the GB's. By constructing the GB's and interval subsets as above, vertex v will be in each X, (Y, resp.) where k is the interval covered by subsetS (T resp.), so it is assured that the resulting V, Xand V, Y matrices both have the consecutive ones property for rows. 30
PAGE 36
.I Example 3.13: This example describes the direction of the proof. D is an interval digraph with the following interval representation. s, [2] s, [l] s; [ 1] s4 [5 ,7] T, T, T; T4 [9' 10 l [2] [ 1] [1] 4 Define GB = {(X Y .l} by: Figure 3.10 Xk = {vik <= S) Yk = {vik <= T) x, {2.3} r, {3,4} x, { 1} r, = {2} X. 0 Y, 0 x, 0 f4 0 GB1 : x, {2,3} Y, {3,4} Therefore, cover the edges of D. GB1 : x, { l} Y, = {2} Since each vertex was placed in a source (or terminal) set of F. where k is in the interval of the source (or terminal) set corresponding to that vertex, then the vertex source (or terminus) incidence matrix will have the consecutive ones property. 31
PAGE 37
x, x, Y, Y, v, 0 1 v, 0 0 V,X: v, 1 0 V,Y: v, 0 1 v, 1 0 v, 1 0 v, 0 0 v, 1 0 Interval graphs exhibit the consecutive ones property for all their maximal cliques. This property does not hold, however, for interval digraphs as the following example shows [18]. Example 3.14: D: Figure 3.11 GB1 : x, = { 1.2 }. Y, {I ,4} GB2 : x, { 1,3}. Y, = {2,4} GB3 : x, { 1,4 }, Y, = {3,4} I I I I : 32
PAGE 38
XI x, x, yl Y, r, VI I I I VI I 0 0 V,X: v, I 0 0 V,Y: v, 0 I 0 v, 0 I 0 v, 0 0 I v, 0 0 I v, I 1 I Since the V,Xand V, Ymatrices have the consecutive ones property, Dis an interval digraph. Following the theorem, D can be represented by the ordered pairs of intervals constructed below, S, = [a,,b,] and T, = [c,,d,] where v E X,k E S and v v E r, k s r,. 1 E X1.X2.X3 1.2.3 sl s, [1 ,3] T, = [1] 1 E yl 1 E T, 2 "X 1 "' s, I s, [1] T, [2] 2 c y 2 Tz 2 3 r:::: x2 2 s SJ s, [2] T, [3] 3 E y 3 E T, 3 4 c X 3 E S4 3 s, = [3] T, = [1 ,3] 4 E YI.Y,.Y, 1,2,3 E T, 33
PAGE 39
However, the remaining maximal GB' s (which were not needed to cover the edges of D) cannot be added to the incidence matrices without destroying the consecutive ones property. v, V,X: v, v, v, v, V,Y: v, v, v 4 { 1}, {1,2,3,4}, x, x, 1 1 1 0 0 1 0 0 Y, Y, 1 0 0 1 0 0 1 1 Y4 {1,2,3,4} Y5 = {4} x, x, x, 1 1 1 0 0 1 0 0 1 1 0 1 Y, Y, Y, 0 1 0 0 1 0 1 1 0 1 1 1 34
PAGE 40
4 Ferrers Digraphs In Chapter 2 we saw that interval graphs have several nice characterizations. In Chapter 3 we discovered that one of those characterizations has an analogy to interval digraphs. In this chapter we look at other ways in which interval digraphs are characterized. 4.1 Preliminaries Before proceeding with these properties, several definitions and concepts need to be introduced. Definition: Ferrers digraphs are digraphs whose successor sets are linearly ordered by inclusion, where the successor set of v is its set of outneighbors, i.e., Sv = {u Vjvu E }. Example 4.1: 4 3 Figure 4.1 35
PAGE 41
Successor Sets: s. = {u E Vlvu E E}. S1 = { 1} s,={l,2} s,={U} S4={1,2,3} ... S1 c;;S2c;;S3c;;S4 .. F is a Ferrers Digraph Is the same true for the predecessor sets? Predecessor Sets: P. = {u E Vluv E E} p1 = {1,2,3,4} P2 = {2,3,4} P, = {4} P4 = 0 ... P4c;;P3c;;P2c;;P1 Yes, the predecessor sets are also linearly ordered. The vertices of Ferrers digraphs can then be partitioned according to which successor and predecessor sets they belong. These partitions are defined as follows. Definition: Source partitionvEAkif v belongs to the kli> largest nonempty predecessor set and to no smaller set and A0 contains vertices with no successors (i.e., vertices that aren't in a predecessor set) if any exist. Definition: Terminal partition v ED k if v belongs to the k"' smallest nonempty successor set and none smaller, with the last set containing the 36
PAGE 42
I vertices with no predecessors (i.e., the vertices that are in no successor set) if there are any. In a larger example, this partitioning becomes apparent. Example 4.2: Successor Sets : St= {} S2={1,2,3} s,= {1,2,3} S4={1,2,3} s,={1,2,3,4} s.= {1,2,3,4} s,={1,2,3,4} Figure 4.2 S8= {1,2,3,4,5,6,7} Predecessor Sets : PI = {2,3,4,5,6,7,8} p2 = {2,3,4,5,6,7,8} P3 = {2,3,4,5,6,7,8} P4 = {5,6,7,8} P5 = {8} P6 = {8} P1 = {8} p8 = {} 37
PAGE 43
Then the partition sets will be as follows. Source Partition Sets : A0 = { 1} A1={2,3,4} A2= {5,6,7} A3={8} Terminal Partition Sets : D1={1,2,3} D2={4} D3= {5,6,7} D4={8} The adjacency matrices of Ferrers digraphs can be permuted so that the l' s appear in the lower left of the matrix. This makes it easy to partition the vertices as described above. In the following adjacency matrix, we see that the rows correspond to the successor sets and the columns correspond to the predecessor sets. In addition, we see that adjacency in D occurs between source (A,) and terminal (D ) partitions only when i J 1, i.e., uv is an edge if and only if i J where u cA1 and 1 2 3 4 5 6 7 8 1 0 0 0 0 0 0 0 0 Ao 2 1 1 1 0 0 0 0 0 3 1 1 1 0 0 0 0 0 A, 4 1 1 1 0 0 0 0 0 5 1 1 1 1 0 0 0 0 6 1 1 1 1 0 0 0 0 A, 7 1 1 1 1 0 0 0 0 8 1 1 1 1 1 1 1 0 A, D, Dz D, D, 38
PAGE 44
Definition: The union of 2 digraphs is complete if every ordered pair of vertices (including u=v) forms an edge in at least one of them, i.e., for all a,b E V(D), V(F), a,b E E(D) or E(F). 4.2 Adjacency Matrices and Ferrers Digraphs Theorem 4.1 [ 18] The following are equivalent: A) D is an interval digraph B) The rows and columns of A(D) can be (independently) permuted so that each 0 can be replaced by one of {R,C} in such a way that every R has only R' s to its right and every C has only C' s below it. C) D is the intersection of two Ferrers digraphs whose union is complete. In order to understand what each of these characteristics means and how they interrelate, the following example from Section 3.2 is used. vt: s [ 1 ,2] r, [1.3) 'f,. < ! l s, [ 1 ,3) T, [2] D: I v2: I vJ: s, [3,5] T, [5] .. 4 v4: s4 [1.0) T, = [1 ,2] Figure 4.3 39
PAGE 45
Since D is an interval digraph, its adjacency matrix should exhibit property B above. A(D): 1 2 3 4 1 1 1 1 0 2 1 1 0 0 3 0 0 1 0 4 1 1 0 0 Each vertex has a source set [a(v),b(v)] and terminal set [c(v),d(v)]. Define two vertex numberings as follows. l) Let the first numbering, u 1 ,u., be defined by u = v if a( v) is the k'" smallest value among the a's where ties are broken arbitrarily. The smallest value among the a's is 1 so u1 = 4. Continuing in this manner, the new numbering is u1 = 4, u, = 1, u, = 2, u, = 3. 2) The second new numbering, w p w., is obtained by w = v if c( v) is the k'" smallest value among the c's with ties broken arbitrarily. Proceeding as above, the new numbering is w1 = 1, w2 = 4, w3 = 2, w,= 3. Allow the rows of A(D) to be permuted by the first new numbering and the columns by the second. Then the vertices labeling the rows of A' (D) are listed in order of the opening endpoints of their source intervals. And the columns are listed in order of the opening endpoint of each vertex's terminal interval. 40
PAGE 46
w, w, w, w, I 4 2 3 u, 4 0 0 0 0 A'(D): I I I I 0 u, u, 2 I I I 0 u, 3 I 0 0 I A zero in the adjacency matrix indicates (u,. w) is not an edge in D which means S n T = 0 or [a(u),b(u)] does not intersect with [c(w),d(w )]. Clearly, there u1 w1 1 1 ) 1 are only two ways in which this can occur. Either c(w) > b(u,) or a(u,) > d(w). Then relabel the iJ"' zero with a C if a(u) > d(w) and with an R if J For example, the ul'w1 position above is zero because S, n T,= 0, i.e., [1,0) n [1,3] = e. In this case, b d so this zero becomes a C. Since d remains the same in this column and the a( u ,)' s increase when moving down through the matrix, once there is a C, there will only be C' s below it. 41
PAGE 47
A'(D) becomes: 4 1 2 3 1 R 1 1 4 R 1 1 c 2 R 1 1 c 3 R R R 1 But why is this the case? Simply because if a digraph is interval then it has an interval assignment, which means the intervals can be ordered by their position along a number line and the replacement of zeros in its adjacency matrix can be done by R' sand C' s as stipulated in the theorem, As for property C, start with the above adjacency matrix with the R' sand C' s. Create two new digraphs, F1 and F, as follows. Let F1 be D plus the edges labeled R in A' (D) above. Then A(F1 ) will have zeros only where the C' s are. Since wherever there is a C there are only C's below it, then the zeros in A(F1 ) can be placed in the lower left with a column permutation. 4 1 2 3 4 1 0 2 1 1 1 0 1 1 1 1 1 3 1 1 1 Then F1 is a Ferrers digraph since its successor sets are ordered by inclusion, i.e., S4 S1 s, s,. 42
PAGE 48
Let F, be D plus the edges corresponding to the C' s. In this case. the only zeros will be where the R' s are, so any zero will have only a zero to its right. Therefore, by row permutations, the zeros of A(F,) can be placed in the upper right. A(F2 ) : 4 1 2 3 1 0 1 1 1 4 0 1 1 1 2 0 1 1 1 3 0 0 0 1 Again, the successor sets are ordered by inclusion so F, is a Ferrers digraph. It is obvious that F1 n F, = D and that F1 U F, is a complete digraph as there are no more zeros left. The methods illustrated here are precisely those methods used to prove ABC. It remains to show that CA. So far the assumption has been that D is an interval digraph, and its interval assignment was known. But what if property C for example is known. How can an interval assignment for D be found? This is not so easy. Therefore, an interval assignment for D above will be found while going through each step of the following proof to aid in understanding. Proof: CA: Assume Fl' F, are Ferrers digraphs where F1 n F, = D and F1 U F2 is complete. Show D is an interval digraph by constructing an intersection representation of D by ordered pairs of intervals. 43
PAGE 49
Let H1 H2 be the complements ofF" F2 respectively. Then H, U H, = D, and H1 n H, = 0. H1 H, are Ferrers digraphs also as if the I 's are elements of inclusive sets then the 0' s are elements of inclusive sets. Let A0 ... ,Ar, be the source partition for H1 and let D" ... ,D P be its terminal partition where A 0 D P may equal the empty set. Let C0 ... ,c._, be the source partition and B" ... ,B. be the terminal partition for the converse of H 2 where B q' C 0 may equal the empty set. Since the converse of H 2 is the transpose of A(H2), clearly H2 is also a Ferrers digraph. Adjacency for the two new Ferrers digraphs, H 1 H, is defined as follows. H1 : uv EH1 i >I, whereu EA,andv ED1 H 2 : uv E H 2 j > k, where u E B1 and v E C < In our example, with F1 and F, from above, the adjacency matrices for H1 and H,' are shown below. From the definitions given earlier, the source and terminal partitions were determined and are also indicated below. 4 2 1 3 4 0 0 0 0 Ssets: s, { 4,2} 1 0 0 0 0 Ao A(H1 ): Psets: P, {3} 2 0 0 0 0 P, = {3} 3 1 1 0 0 A, D, D, 44
PAGE 50
Ssets: s, { 4} 4 1 2 3 s, {4} 1 1 0 0 0 s2 { 4} 4 1 0 0 0 c, A(H2'): s, = {1,2,4} 2 0 0 0 Psets: P, = {1,2,3,4} 3 1 1 0 c, P, = {3} B, B, B, pl = {3} Constructing the interval representation: L Assign numbers a,,b,,c,,d, to partitions A,,B,,C,,D, 2. . S, = [a(v),b(v)] Asstgn vertex v the mtervals T, = [c(v),d(v)] where (a(v),b(v),c(v),d(v)) = (a,.bpc<,d1 ) if v E A,,BFC,,D, Requirements: L S, and T, must be intervals which implies a, s b1 and c, s d1 if 2. uv E E a(u) s d(v) and b(u) ::: c(v) Constructing an interval representation for D: 1. Make the implication digraph M: ii) Add edges: a) A B if A n B 0 j I j 45
PAGE 51
c)BC for 1,; i,; q1 I d) D.A. for 1 c i,; p1 ' Lemma The implication digraph M is acyclic. Proof: By way of contradiction, assume M has a cycle. Then it must include at least one vertex in each of the A's, B's, C's and D's. The only edges between the B's and C's are B,C,. The same is true for the D's and A's. But, because of (a) and (b) in the construction of M, the edges between the A's and B' s and between the C's and D's came from nonempty intersections. So edges A,B1 and C,D1 are in the cycle implies u c. A, (1 B1 and v E C, (1 D1 Since the indices do not decrease on any other kind of edge, then in order for B1 to get to C ,, J ,; k and in order for D1 to get to A,, then l,; i. Then there exists au E B1 and v E c, with J,; k implies tiV E H, and there exists au E A, and v E D1 with lsi which implies uv E H 1 a contradiction as H 1 II H, = 0. :. M is acyclic. In our example, before the implication digraph is constructed, it is useful to determine the intersections. Therefore, create a chart comparing vertices with the partition sets that each is in and then list the intersections between A and B and between C and D only. 46
PAGE 52
0 A. 1,2,4 B. c D. Then the intersections are: 1 2 3 3 4 1,2 3 1,2,4 3 4,2 1,3 A0 n B" A0 n B,, A1 n B,, C1 n Dp C1 n D,, c, n D, Now create the implication digraph M as follows. i) The four directed paths are: A0,A1 ; BI'B1,B3 ; C1,C2 ; D1,D1 i i) Additional edges: AOBI; AOB,; A1B3 C1D1 ; C1D2 ; c,D, B1C1 ; B,c, D1A1 Figure 4.4 47
PAGE 53
2. Ordering: since M is acyclic, there exists a topological numbering. i) Assign the numbers a,b,c,d to the partition sets A1,B1,C1,D1 as the vertices in M. ii) Then assign each vertex the number t where t is the number of vertices in the longest path ending at x. Lemma This topological numbering f V(M)N /(Y) > f(X) when XY E E (M) Proof: By the construction of M, the predecessors of any C 1 i 1 are C 1 1 and B So any path ending at B can be extended to C which implies/( C) B. + 1. l t I I I Now consider a longest path ending at C1 If it begins at C0 then it visits only C's and has length i + 1 but any path from B 1 to B 1 is shorter by 1. Then the length of a longest path ending with B 1 is at least i + 1 1 which implies f(B) :: f(C) 1. Also, if the path crosses from B1 to C1 for some J i, then replacing the vertex sequence C1 ... ,C1 with Bfr" ... ,B1 gives a path shorter by one. So that the length of any longest path ending with B 1 is at least one shorter than the longest path ending with C1 i.e., f(B) z f(c1 ) 1. :. f( C) = f(B) + 1 and by the same argument f(A,) = f(D) + 1. Continuing with the example, the following topological ordering is found by following the instructions in the proof. 48
PAGE 54
Topological Ordering: 0 I 2 3 a. I 5 b 2 3 6 c 3 4 d. 4 5 Are the conditions satisfied? I. A0 n B1 = a0 = I s A0 n B2 = a0 = I AnB=a=5 1 3 1 s b = 3 2 ::: b, = 6 c, n D, c, = 3 ::: d, = 4 c, n D, c, = 3 ::: d, = 5 c, n D, c, = 4 d, = 5 2. All are strictly increasing sequences. 3. Fori 2 I, a,= d, + 1: a1 = 5 = d1 + I c 1 = d1 + 1: c 1 = 3 = b 1 + I c =4=b +1 2 2 Therefore, this topological ordering satisfies the requirements. Then the interval representation for D is as follows. For a(v) =a,, b(v) = b1 c(v) = c,, d(v) = d1 if v E A,,B1,C,,D,, the intervals are defined by: S = [a(v),b(v)J sl = [a (I) = ao = 1, S = [a(2) = a = I 2 0 ) S3 = [a(3) = a1 = 5, S4 = [a(4) = a0 = I, b(l)=b,=3] b(2)=b,=3] b(3) = b 3 = 6] b(4) = b1 = 2] 49 T = [c(vJ,d(v)J rl = [c(l) = cl = 3, r, = [c(2) = cl = 3, r, = [c(3) = c, = 4, r, = [c(4) = cl = 3, d(l)=d,=5] d(2) = d, = 4] d(3)=d,=5] d(4) = d1 = 4]
PAGE 55
And the intervals are: s, T, 1 [UJ [3,5] 2 [1 ,3] [3 ,4] 3 [5,6] [4,5] 4 [1 ,2] [3,4] This assignment yields the original D. It isn't the same assignment we started with, nor is this the most efficient one. but it is an assignment that works. 4.3 Adjacency Matrices and Ferrers Dimension Adjacency matrices of interval digraphs can be characterized further with regard to Ferrers digraphs. Again, some ideas need to be generated before the theorem is presented. Definition: Ferrers dimension of a digraph D is the minimum number of Ferrers digraphs whose intersection is D. Ferrers digraphs were defined in the previous section as having successor sets that are linearly ordered by inclusion. The following is another way of looking at them. Definition: A digraph D is a Ferrers digraph if and only if A(D) does not contain an obstruction, where an obstruction is a 2x2 matrix that is a permutation matrix; and a couple refers to the pair of zeros in the obstruction. 50
PAGE 56
Looking at the adjacency matrix in Example 4.1, it is clear that an obstruction does not exist. In fact, since the successor sets are linearly ordered, one can see that an obstruction can never occur in Ferrers digraphs. Definition: A H(D) is a graph whose vertices correspond to the zeros of A(D), with 2 vertices joined by an edge if the corresponding zeros belong to an obstruction. Example 4.3: D: 3 Figure 4.5 2 3 1 [ : 1 0 1 A(D): 2 0 1 3 1 0 Label the zeros as vertices: 1 2 3 a 1 r,.,. 2 1 c 3 d 1 These vertex pairs making edges in H(D) are called couples. 51
PAGE 57
Then identify each obstruction and place an edge between the 2 vertices in that obstruction. Hence H(D): b d a e Figure 4.6 In theorem 4. 3 below, the proof of CA is due to the following theorem by Cogis [2]. Theorem 4.2 A digraph D has Ferrers dimension less than or equal to 2 if and only if H(D) is bipartite. Example 4.4: Since Example 3. 8 from the preceding proof is an interval digraph, then it has Ferrers dimension < 2. According to the above theorem, H(D) is bipartite. Take the adjacency matrix of D: l 2 3 4 l 1 1 1 0 2 1 1 0 0 52 3 0 0 1 0 4 1 1 0 0
PAGE 58
' '' And label the zeros to be the vertices of H(D): I 2 3 4 I I I a 1 2 I I ,' b 1 obstruction 3 I c ) d_ 4 e f g h Then H(D) is bipartite. Figure 4.7 Recall from theorem 4. I that all interval digraphs are the intersection of two Ferrers digraphs. So the minimum number of Ferrers digraphs whose intersection is D is at most 2, i.e., all interval digraphs have Ferrers dimension at most 2. Theorem 4.3 [ 18[ The following conditions are equivalent. A) D has Ferrers dim ,; 2. B) The rows and columns of A(D) can be permuted so that no 0 has a I both below it and to its right. C) The graph H(D) of couples in D is bipartite. Looking at the example used above, D is an interval digraph, therefore' D has Ferrers dim at most 2. From the previous proof, Fl' F2 are Ferrers digraphs whose 53
PAGE 59
intersection is D and AI' A2 are their adjacency matrices, each permuted so that the O's are in the lower left and upper right respectively. Renumber the rows of permuted A1 and the columns of permuted A2 4 2 1 3 w, w, w, w, u, = 4 l 1 1 1 1 4 2 3 A'(F1): u, = 1 1 1 1 1 4 0 0 0 0 A(F2): 1 1 1 1 0 u, = 2 1 1 1 1 2 1 1 1 0 u, 3 0 0 1 1 3 1 1 1 l Now put the rows of A(D) in the order u l' ... ,u 4 and the columns in the order wP ... ,w4 1 2 4 3 1 1 1 1 0 A'(D): 2 1 1 1 0 4 0 0 0 0 3 1 0 0 1 Since F1 n F, = D, then where A(D)( u w ) =0 so must either A 1(u w ) = 0 or .,. I } I } A,(u,w) = 0. If A1(u,w1 ) = 0 then AJu,w) = 0 for all r > i as the zeros of A1 are in the lower left. Then A(D)(u,w)=O for all r > i. Hence, if A(D)(u,w)=O then there will be only zeros below it. Similarly, if A,(u,w) = 0 then A2(u1w,) = 0 for all r > 1 and A(D)(u,w,)=O r > 1. So if A(D)( u w ) =0 then there will be only zeros to its right. 1 54
PAGE 60
Therefore, the rows and columns of A(D) can be permuted so that no 0 has a I both below it and to its right. Now, beginning with permuted A(D) (as above) such that no 0 has a I both below it and to its right, then 2x2 permutation matrices of the form [ ] cannot exist, leaving only [ ] as possible obstructions. Label the zeros of A(D) as vertices of H(D) and place an edge between 2 vertices only if their corresponding 0' s are in an obstruction. Then label the 0' s of A(D) with a I below them as R and the zeros with a 1 to their right as C. Clearly, each obstruction will have an R and a C. Hence, the only edges of H(D) will be between a vertex corresponding to an R and a vertex corresponding to a C. Therefore, H(D) is bipartite with possible isolated vertices. This much is left to the reader to verify. 1 2 4 3 1 2 4 3 1 1 1 1 a 1 1 1 1 R A'(D): 2 1 1 .1 b A'(D): 2 1 1 1 R 4 c d e_,' f obstruction 4 R 0 0 R 3 1 g h r 3 1 c c 1 In the above example, the two zeros not labeled could be R' s or C' s, but since they are not part of any obstruction, they do not affect H(D). This exemplifies precisely those methods used to prove ABC. For CA, please see [2]. All interval digraphs have Ferrers dim< 2, but it remains to ask if all digraphs with Ferrers dim 2 are interval. The answer is no as the following theorem states. 55
PAGE 61
Theorem 4.4 [18] The interval digraphs are properly contained in the set of digraphs with Ferrers dimension at most 2. In the following adjacency matrix of a digraph D, no 0 has a 1 both below it and to its right. So D has Ferrers dimension at most 2. VI v, v, v. v, v6 v, vt 1 1 1 0 0 0 0 v, I 1 1 1 1 0 0 v, 1 1 1 1 1 1 0 A(D): v. 0 1 1 1 1 1 1 v, 0 1 1 1 1 0 1 v, 0 0 1 0 0 0 v, 0 0 0 1 0 1 However, it is not possible to label the zeros with R' sand C' s as stipulated in Theorem 4.1 above. vi v 2 v, v. v, v6 v, vi 1 1 1 R R R R v, 1 1 1 1 1 R R v, 1 1 1 1 1 1 R A(D): c 1 1 1 1 v. 1 1 v, I c 1 1 1 1 c 1 v, l c c 1 1 R 0 R v, c c c 1 1 c 1 56
PAGE 62
It can be shown that the zero in the v6v6 position must be both a C and an R. Therefore, although D has Ferrers dimension at most 2, D is not an interval digraph. For a proof of this, please see [18]. 57
PAGE 63
5 Other Characterizations Families of sets other than intervals on the real number line have interested graph theorists. Consider, for example, an intersection graph where the sets are arcs on a circle. These are called circulararc graphs. Is there a generalization to digraphs; and if so, what is known about them? Asteroidal triples, the absence of which plays a part in identifying interval graphs, have a counterpart for directed graphs. The following is a brief overview of these topics and others taken from recent literature having to do with interval digraphs. 5.1 Relating Interval Graphs to Interval Digraphs If it is known that a graph G is an interval graph, what is known about its corresponding digraph? When that digraph is obtained by adding 1 's to the diagonal of A(G), then Dis called a symmetric digraph with loops and something very specific is known about it. Theorem 5.1 [ 19[ A graph G is an interval graph if and only if the corresponding symmetric digraph with loops is an interval digraph. Proof: Necessity Assume G is an interval graph with each vertex v assigned interval I Let S = T = I thereby giving an interval representation of D(G). v v v v 58
PAGE 64
Sufficiency Assume D(G), a symmetric digraph with loops, is an interval digraph with interval representation: {(S,,T.)I v E V(G)} where S, = [a,,b,] and T = [c ,d ]. If u +> v in D(G) then both S n T and S n T will not be empty, v vv v u u v a ,; d and cu b a + c ,; d + b leading to the following inequalities: du d b' a' + c' d" + b". au ;;; v an cv c:;: u u u. v v For G, the underlying undirected graph without loops, let I, = [a, + c,, b, + d,]. Then the above implies I, n I, is not empty so that YU is an edge of Gas needed. a > du If u u v c > b c" > b'. Together these lead to the following inequalities: v u (1) Either a,> du and au> d, or cu > b, and c, > bu (2) Either a > d and c > b or a > d and cu > b .. v u v u u v But u and v both have loops which means that S, n T, and S" n T" are not empty, a d and thus implying a' d' and u u When this is coupled with (1) above contradictions are the result: d d + b and a + c > d + b which means I n I JS v 'II u u u uv v v u empty so uv, vu $ E(G). Therefore, G is an interval graph. 59
PAGE 65
5.2 CircularArc Digraphs An intersection graph where the families of sets are arcs on a circle are called circulararc Jiraphs and are used to model traffic flow through intersections. If the families of sets are ordered pairs of arcs on a circle, then the intersection graph is a circulararc diiiraph. In Chapter 2, we saw that Z,, a circuit on 4 vertices, wasn't an interval graph. However, z, can easily be represented as a circulararc graph. Figure 5.1 The same argument that was used to show Z 4 had no interval assignment shows that D below doesn't have one either, and therefore is not an interval digraph. ,,..... .{II "'"2) ,Figure 5.2 60
PAGE 66
However, D can be represented by ordered pairs of arcs on a circle. Therefore, D is a circulararc digraph. Figure 5.3 Sen, Das and West, in their paper CircularArc Digraphs: A Characten"zation, give characterizations for circulararc digraphs corresponding to those in [18] for interval digraphs. For example, in Section 3.2 an analogy of the consecutive ones property for interval graphs was made to interval digraphs in two parts: consecutive ones property for intervalpoint digraphs and a general consecutive ones property. These authors give similar statements for circulararc digraphs in the following theorems. Definition: A 0, !matrix has the circular ones property for rows if its columns can be permuted so that the ones in each row are consecutive when we view the positions as a cycle, with the first column following the last. 61
PAGE 67
Theorem 5.2 A digraph D has an intersection representation by circular arcs in which all terminal arcs are single points if and only if its adjacency matrix has the circular ones property for rows. Theorem 5.3 D is a circulararc digraph if and only if there is a numbering of the GB' s in some covering B of D that exhibits the circular ones property for rows for both the V,Xmatrix and V, Ymatrix of B. In fact, except for the word interval being replaced with circulararc, these theorems are exactly the same as their counterparts for interval digraphs. The reader is referred to [ 191 for the proofs and further discussion. The following theorem is included for completeness as it is used to prove theorem 5.5 below. Theorem 5.4 A digraph D is a circulararc digraph if and only if the rows and columns of its adjacency matrix can be permuted independently so that the resulting matrix has the generalized circular ones property. The authors define a stair partition of a 0, !matrix to be some partition of its elements into two sets (L, U) such that U corresponds to the nonzero positions in some upper triangular matrix and L to the nonzero positions in some lower triangular matrix. Then a graph has the generalized circular ones property if it has a stair partition (L, U) such that all of its ones are covered by v, and W1 where v, consists of the ones in row i that begin at the stair and continue rightward until the first 0 is reached and W consists of the ones in column j that begin at the stair and 1 62
PAGE 68
continue downward until the first 0 is reached. The theorem that I found most interesting in this paper was the following which states that the compliment of any interval digraph is a circulararc digraph. Theorem 5.5 The complement of any digraph with Ferrers dimension at most 2 is a circulararc digraph. Proof: Let D be a digraph with Ferrers dimension at most 2. Then by theorem 4. 3 we know the rows and columns of A(D) can be permuted so that no 0 has a I both below and to its right. Take the complement and reverse the order of the rows and the order of the columns. Then in the resulting adjacency matrix of the compliment of D, no I has a zero both above it and to its left. Let the matrix have stair partition (L,U) where the entire matrix is U. Then the ones in A'(D) can be covered as follows. A I in the i,j position with no 0 to its left belongs to v,. A I in i,j position with no 0 above it belongs to W1 Then all the ones will be covered by the V, 'sand W/s. Therefore. A'(D) has the generalized circular ones property, so by theorem 5.4, D is a circulararc digraph. Example 5.1: Since we know D from Example 3.8 is an interval digraph, we will see if D is a circulararc digraph. Start with A' (D) above where the rows and columns have already been permuted so that no zero has a I both below it and to its right, and take its complement. 63
PAGE 69
1 2 4 3 1 1 l l 0 A'(D): 2 l l l 0 A(D ): 4 0 0 0 0 3 1 0 0 1 Then reverse the order of the rows and the columns. 3 A'(D ): 4 2 1 3 0 1 1 1 4 l l 0 0 2 1 1 0 0 1 0 l 0 0 l 2 4 3 1 0 0 0 1 2 0 0 0 1 4 l 1 l l 3 0 1 1 0 The ones in row 4 will be covered by V4 those in column 3 will be covered by W,, and the last two ones in row 3 can be covered by v,. Then there exists some circulararc assignment for D pictured below. 1 2 Figure 5.4 A possible circulararc representation is below. 64 Figure 5.5
PAGE 70
5.3 Other Generalizations Although the idea of interval digraphs is a recent one, there have been several papers written which draw further analogies to interval graphs. A brief summary of those investigations follow. A triple of vertices u, v. w of a graph is called asteroidal if there are chains C 1 between u and v, C 2 between u and w and C 3 between v and w so that there is no edge from u to C,, from v to C2 or from w to C1 Erich Prisner, in his work, A Characterization of Interval Catch Digraphs [131, defines a diasteroidal triple in much the same way except that in each of the three x,ychains, there is no vertex that is an initial endpoint of an arc preceding vertex z. He points out that a digraph has a diasteroidal triple if and only if its underlying undirected graph contains an asteroidal triple. Lekkerkerker and Boland, 1962 (please see Roberts [ 16]) extend the Z4 property for interval graphs by including asteroidal triples. They prove that a graph is an interval graph if and only if it does not have any Z", n c: 4 as a generated subgraph and it has no asteroidal triples. Prisner gives an analogous characterization for interval digraphs when he proves that a digraph is an interval catch digraph if and only if it has no diasteroidal triple. Among the relationships between intervals on the real number line, that of containment has been investigated with regard to interval digraphs. In [21] an 65
PAGE 71
interval containment digraph is an interval digraph where the terminal sets are properly contained in the source sets whenever S" and T. intersect. They prove that a digraph is an interval containment digraph if and only if it has Ferrers dimension at most 2. They also extend this concept to circulararcs by defining a circulararc containment digraph to be a digraph where the ordered pairs ( S", T) are arcs on a circle and there is an edge from u to v if and only if S" properly contains T.. They show that a digraph is a circulararc containment digraph if and only if its complement is a circulararc digraph. Finally, the last in this summary is a paper by Harary, Kabell and McMorris [8] investigating acyclic interval digraphs. They show that a labeling of the vertices v1 .... ,v of D such that whenever v v. is an ed2e, then i
PAGE 72
6 Conclusion This survey is by no means exhaustive. Other work has been or is being done with interval digraphs, and there are many areas that are still open for new research. Certainly there are more categories of interval and intersection graphs to which analogies could be drawn for digraphs. Areas for future investigation could include the following topics. Tolerance graphs are interval graphs where xy is an edge in G only when the intervals corresponding to x and y overlap by some specified positive value. This way, two intervals can overlap at under the tolerance amount and this will not result in an edge. Are there any interesting generalizations to be made by considering pairs of intervals for each vertex where xy is an edge in D if and only if the source interval for x and the terminal interval for y overlap at least the tolerance amount? What kinds of applications could this have? Some work has been done linking competition graphs to interval graphs, but there is more to be learned in this area. For example, what can be said about the competition graphs of interval digraphs in general? The digraph that was used to illustrate several of the concepts presented in this paper is an interval digraph (Fig.4.3). What does its competition graph look like? By definition, the 67
PAGE 73
competition graph of D has the same vertex set as D and xy is an edge if and only if xc and yc are both edges in D. Hence, C(D) would have edges (I ,2), (2,3) and (3, I) and vertex 4 would be isolated. In this case, the competition graph of Dis an interval graph, but is this always the case? What do competition graphs of interval digraphs look like in general? And is an interval graph the competition graph of some interval digraph? Lastly, what might be said about the applications of interval digraphs? Are there any; and if so, do they differ from the applications for interval and intersection graphs? 68.
PAGE 74
BIBLIOGRAPHY [1 1 Biro, M., Hujter, M., Tuza, Zs., ?recoloring extension. I. Interval graphs, Discrete Math., Vol. 100, 267279, 1992. [2 1 Cogis, 0., A characterization of digraphs with Ferrers dimension 2, Rap. Rech. 19, G.R. CNRS, 22, Paris, 1979. [31 Cogis, 0 .. Ferrers Digraphs and Threshold Graphs, Discrete Mathematics. Vol. 38, 3346, 1982. [4] De Caen, D., Gregory, D.A., Pullman, N.J .. The Boolean Rank of Zero One Matrices. Proc. 3rd Car. Conf. Comb. and Comp., 169173. [5] Eckhoff, J., Extremal Interval Graphs, Journal of Graph Theory, Vol. 17, No. I, 117127, 1993. [6] Gimbel, J., End Vertices in Interval Graphs, Elsevier Science Publishers, 1988. 69
PAGE 75
[7] Golumbic, M.C., Monma, C.L., Trotter, Jr., W.T., Tolerance Graphs, Discrete Applied Math., Vol. 9, 157170, 1984. [8] Harary, F., Kabel!, J.A., McMorris, F.R., Interval Acyclic Digraphs, to appear. [9] Jachowski, Z., A new characterization of proper interval graphs, Discrete Math., Vol. 105, 103109, 1992. [10] Jacobson, M.S., McMorris, F.R., Scheinerman, E.R., General results on tolerance intersection graphs, Submitted to Journal of Graph Theory. [ 11] Lundgren, J.R., Rasmussen, C. W., Maybee, J.S., Interval competition graphs of symmetric digraphs, Discrete Mathematics, Vol. 119, 113122, 1993. [12] Marathe, M.V., Ravi, R., Rangan, C.P., Generalizedvertexcoveringin interval graphs, Discrete Applied Math., Vol. 39, 8793, 1992. [131 Prisner, E., A Characterization oflnterval Catch Digraphs, Discrete 70
PAGE 76
Mathematics, Vol. 73, 285289, 1989. [ 14] Raychaudhuri, A., Optimal multiple interval assignments in frequency assignment and traffic phasing, Discrete Applied Math., Vol. 40, 319332, 1992. [15] Raychaudhuri, A .. Roberts, F.S., Generalized Competition Graphs and Their Applications. Methods of Operations Research, Vol. 49, 295311, 1985. [ 16] Roberts, F.S.. Discrete Mathematical Models, PrenticeHall, Inc., 1976. [17] Scheinerman. E.R., An Evolution of Interval Graphs, Discrete Math., Vol. 82, 287302, 1990. [18] Sen, M .. Das. S .. Roy, A.B .. West. D.B .. Interval Digraphs: An Analogue of!nterval Graphs, Journal of Graph Theory, Vol. 13, No. 2, 189202, 1989. 71
PAGE 77
[19] Sen, M., Das, S., West, D. B., CircularArc Digraphs: A Characterization, Journal of Graph Theory, Vol. 13, No. 4, 581592, 1989. [20] Sen, M., Sanyal, B. K., Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders, SIAM Journal of Discrete Math., Vol. 7, No. 2, 157165, 1994. [21] Sen, M.K., Sanyal, B.K., West, D.B., Representations of Digraphs Using Intervals and Circular Arcs, Submitted to Discrete Math. [22] Trotter, Jr., W.T., Harary, F .. On Double and Multiple Interval Graphs, Journal of Graph Theory, Vol. 3, 205211, 1979. 72
