Citation
Interval competition graphs of symmetric digraphs and two-step graphs of trees

Material Information

Title:
Interval competition graphs of symmetric digraphs and two-step graphs of trees
Creator:
Rasmussen, Craig Wood
Publication Date:
Language:
English
Physical Description:
x, 119 leaves : illustrations ; 28 cm

Subjects

Subjects / Keywords:
Trees (Graph theory) ( lcsh )
Symmetric functions ( lcsh )
Symmetric functions ( fast )
Trees (Graph theory) ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 113-119).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Department of Mathematical and Statistical Sciences.
Statement of Responsibility:
by Craig Wood Rasmussen.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
23041647 ( OCLC )
ocm23041647
Classification:
LD1190.L62 1990d .R37 ( lcc )

Full Text
INTERVAL COMPETITION GRAPHS
OF SYMMETRIC DIGRAPHS
AND
TWO-STEP GRAPHS OF TREES
by
Craig Wood Rasmussen
B.A., University of Colorado at Denver, 1986
M.S., University of Colorado at Denver, 1988
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Department of Mathematics


This thesis for the Doctor of Philosophy
degree by
Craig Wood Rasmussen
has been approved for the
Department of
Mathematics
by


Rasmussen, Craig Wood (Ph.D., Applied Mathematics)
Interval Competition Graphs of Symmetric Digraphs and Competition Graphs
of Trees
Thesis directed by Professor J. Richard Lundgren
The competition graph C(D) of a digraph D = (V, A) is the graph with
V(C) = V and an edge [u,u] if and only if there exists z £ V such that
(u,z),(v,z) £ A. If the digraph D is symmetric, then it is convenient to view it
as an undirected graph G (V, £). In this case the competition graph G(G) is
similarly defined but with edges [u, z], [u, z] replacing arcs (u, z), (v, z). We show
that the competition graph of an arbitrary loopless graph G is the two-step graph
52(G). The boxicity of a graph G is the smallest k such that G is the intersec-
tion graph of generalized rectangles in Euclidean /s-space. An interval graph is
a graph of boxicity one. These graphs frequently arise in applications and have
good coloring properties.
We answer the following questions: What graphs are the competition graphs
of loopless interval graphs? When are these competition graphs interval? It is
shown that P4-free interval graphs, bridgeless interval graphs, and interval trees
all have interval competition graphs. In each case, a competition cover is used to
prove the result. A competition cover is then developed that can be derived from
an arbitrary interval graph. Using this cover, necessary and sufficient conditions


are developed for the competition graph of an arbitrary interval graph to be
interval. Interval graphs with interval competition graphs are then characterized
in terms of subgraphs, contributing some insight of a more intuitive nature to
the previous result.
In an effort to obtain more general results than those restricted to graphs of
boxicity one, results are obtained for trees. Competition graphs of trees are char-
acterized, and necessary and sufficient conditions are given for the competition
graph of a tree to be an interval graph.
An algorithm is presented that, given a connected, chordal, diamond-free
graph H, produces a tree T such that H is a component of C(T). The class of
even trees is defined, and the algorithm is used to obtain results that show that
these trees have invertible two-step graphs. Open questions are discussed.
The form and content of this abstract are approved. I recommend its publication.
Signed
J. Richard Lundgren
IV


To my parents


CONTENTS
List of Figures.................................................. viii
Acknowledgements..................................................... x
1 INTRODUCTION 1
Definitions.......................................................... 1
Graphs and Matrices.................................................. 9
Intersection Graphs.................................................. 9
Interval Graphs................................................ 11
Definition and Characterizations............................... 12
Unit Interval Graphs........................................... 14
Higher Dimensional Analogues................................... 14
Applications of Interval Graphs............................... 16
Tolerance Graphs............................................... 17
Derived Graphs...................................................... 18
Step Graphs and Powers of Graphs............................... 18
Competition Graphs ............................................ 21
Generalized Competition Graphs ................................ 23
Related Graphs................................................. 24
Applications of Competition Graphs ................................. 25
The Channel Assignment Problem............................... 27
Description of the Thesis........................................... 29
2 CLASSES OF INTERVAL GRAPHS WITH INTERVAL COM-
PETITION GRAPHS 31
Interval Graphs with Interval Squares............................... 31
Interval Graphs with Interval Two-Step Graphs....................... 33
Competition Covers............................................. 37
Competition Covers and Interval Two-Step Graphs................ 37
Certain Classes of Interval Graphs with Interval Two-Step Graphs ... 40
P4-Free Graphs................................................. 40
Bridgeless Interval Graphs..................................... 43
Caterpillars................................................... 45
Two-Step Graphs of Cycles .......................................... 47
3 CHARACTERIZATIONS OF INTERVAL GRAPHS WITH IN-
TERVAL TWO-STEP GRAPHS 50
Construction of a Special Competition Cover......................... 50
A Classification of the Nonsimplicial Vertices of a Graph...... 50


Nonsimplicial Competition Covers.......................... 52
Characterization Using Nonsimplicial Competition Cover....... 60
Extension to Unit Interval Graphs......................... 60
Some Remarks on Computational Complexity.................. 64
Characterization in Terms of Subgraphs ........................ 65
Limitations on Number and Location of Type III Vertices. 66
Restrictions on Bridge-Induced Subgraphs.................. 73
4 TWO-STEP GRAPHS OF TREES 82
Trees with Interval Two-Step Graphs............................ 82
Forbidden Subgraph Characterization............................ 85
The Reconstruction Problem..................................... 88
Algorithm 4.1 for Partial Reconstruction of a Tree........ 95
Proof of Correctness of the Algorithm..................... 97
Uniquely Reconstructive Trees ............................102
5 CONCLUSIONS AND OPEN QUESTIONS 106
Synopsis of the Thesis.........................................106
Open Questions.................................................108
LIST OF NOTATION ..............................................110
BIBLIOGRAPHY..................................................113
Vll


LIST OF FIGURES
1.1 A graph G and a digraph D........................................... 2
1.2 A graph G, with subgraph G' induced by {iq, v2, U3}, and edge-
induced subgraph G" induced by {[!, u2]> [*>3) ^4]}............. 3
1.3 A tree T and a caterpillar C........................................ 6
1.4 A complete bipartite graph.......................................... 6
1.5 A comparability graph G with a transitive orientation; graph K is
not a comparability graph........................................ 7
1.6 Graph G and complement Gc........................................... 8
1.7 Digraph D with adjacency matrix A(D), graph G with adjacency
matrix A(G), incidence matrix M(G), and clique matrix C(G). . 10
1.8 Intersection graph for a family of sets............................ 11
1.9 A family I of real intervals, and corresponding interval graph G. . 12
1.10 Examples of asteroidal triples..................................... 12
1.11 Illustration of theorem of Fulkerson and Gross..................... 14
1.12 with box representation...................................... 15
1.13 Graph G and clique graph K(G)...................................... 18
1.14 Graph G with three derived graphs.................................. 19
1.15 Acyclic digraph D with competition graph C(D)...................... 22
2.1 An Interval Graph H with Noninterval Competition Graph. ... 36
2.2 Illustration for proof of Theorem 2.5.............................. 39
2.3 Forced P4 of Lemma 2.1............................................. 40
2.4 A P4-free interval graph, with dominating vertex c................. 42
2.5 A bridgeless interval graph H and 82(H)............................ 44
2.6 A Caterpillar T with its competition graph S2(T)\JS2"(T). ... 46
2.7 Graphs with induced fc-cycles, k > 3, and two-step graphs.......... 48
3.1 Classes of nonsimplicial vertices.................................. 51
3.2 Illustration for proof of Lemma 3.3................................ 54
3.3 Graphs for Case l.ii, Lemma 3.4.................................... 55
3.4 Subgraphs for Case l.iii, Lemma 3.4................................ 57
3.5 Subgraphs for Theorem 3.2.......................................... 61
3.6 Graphs for proof of Theorem 3.2.................................... 62
3.7 Graph G, with edge-induced G and G*................................ 66
3.8 Induced subgraphs resulting from disconnected H.................... 67
3.9 Effect on S of disconnected H...................................... 67
3.10 H* isomorphic to P5, and S2(H)................................... 68
3.11 Cliques containing three (G) and two (H) Type III vertices. ... 69


3.12 Graphs for Lemma 3.7........................................ 69
3.13 Illustration for proof of Lemma 3.8......................... 71
3.14 Graphs and covers for proof of Theorem 3.5.................... 74
3.15 Diamond-free graphs for proof of Theorem 3.7, part 1.......... 77
3.16 Diamond-free graphs for proof of Theorem 3.7, part 2.......... 78
3.17 Diamond-free graphs for proof of Theorem 3.7, part 3.......... 80
4.1 Noninterval tree T with interval S2{T)........................ 82
4.2 H C S2(T), and acylic preimage................................ 84
4.3 Forbidden subgraph for tree with interval two-step graph...... 86
4.4 Forbidden subgraphs for interval graphs....................... 87
4.5 Graphs for proof of Theorem 4.1............................... 87
4.6 Nonisomorphic trees with same competition graph......... 88
4.7 Klfi and S2(iQ,6)............................................. 88
4.8 Subgraph and clique configuration for proof of Lemma 4.7...... 92
4.9 Components Gj, G2, G3 with (J (Gh, G2, G3).................... 94
4.10 Construction of T using algorithm 4.1. ....................... 96
4.11 Subtree and clique configuration for proof of Lemma 4.8....... 98
IX


ACKNOWLEDGEMENTS
I would like to take this opportunity to thank my advisor, Rich Lundgren,
for the guidance and encouragement that he provided during all phases of the
preparation of this dissertation. It has been a privilege to work with him, and I
hope that I have acquired some of his insight in the process. Thanks go to the
other four members of my committee; they are Bill Cherowitzo, Kathy Jones,
Jenny Ryan, and Bill Wolfe. Each, in his or her own way, has introduced me to
mathematics of great beauty that will keep me happily occupied for the rest of
my life. In addition, Bill Cherowitzo, Kathy Jones, and Jenny Ryan served as
proofreaders; without their critical reading this document would be less than it
now is, both in content and in style.
I would also like to thank my family and my friends for their unflagging
support. There have been many dark times during the past four years when their
confidence in me exceeded my own. Their encouragement kept me going, and
I am in their debt. It is impossible to list them all, but a few deserve special
mention; they are Debbie Beltz, Van and Teri Henson, and Steve Lang. I know
that others should be on this list, and I apologize for any omission.
Thanks go to the Office of Naval Research, for partial support of this work
under Research Contract N00014-88-K-0087.


CHAPTER 1
INTRODUCTION
Graph models of conflict or competition have grown in number and impor-
tance in the last two decades. The roots of this thesis lie in the pioneering work
of Cohen [16] on competition in ecosystems. Before describing the early work in
this area, it is necessary to provide necessary definitions. Further definitions will
be introduced as they become needed. Treatment of certain topics not directly
related to the research described here will be somewhat terse; for a detailed treat-
ment, see any of the general texts on graph theory, such as Harary [46] or Bondy
and Murty [11]. The reader who is familiar with the vocabulary and concepts of
graph theory might wish to skip over this section. The appendix contains a list
of notation used.
Definitions
A graph G = (V,E) is a nonempty collection V of vertices together with a
set E C V x V of unordered pairs called edges. If e = [x,y] 6 22(G) then x and
y are said to be adjacent and e is incident to both x and y. The vertices x and
y are the end-vertices of e. If |V| is finite, then G is said to be finite. All graphs
in this thesis will be assumed to be finite. A loop in a graph is an edge of the


Figure 1.1: A graph G and a digraph D.
form [cc, x]. Unless otherwise specified, all graphs will be assumed to be loopless.
A path in a graph G is a sequence u2,..., u*. of vertices in which the existence
of e, = is implicit for every i, i 1,..., k 1. If the Vi are all distinct,
then the path is said to be simple. If vj. = v1 then the path is called a cycle.
Like a path, a cycle is simple if all of its vertices, with the exception v/c, are
distinct.
A directed graph, or digraph D = (V, A) is similarly defined, but edges are
oriented, that is, elements of A C V X V are ordered pairs, called arcs. If (x,y) £
A, it is conventionally understood that x is the origin and y the terminus of (x, y)\
the arc is from x to y. A digraph D is symmetric if (x,y) £ A implies (y,x) £ A.
It is convenient to view a symmetric digraph as a graph, by considering each pair
(m, y), (y,x) of arcs as the edge [x,y]. Paths and cycles in digraphs are defined as
in the undirected case above, but with arcs replacing edges.
Both graphs and digraphs allow a convenient pictorial representation, as
shown in Figure 1.1. A subgraph G' of a graph G is a subset V' C V together with
a subset E' C E, where E' is restricted to V1 x V'. If G' ^ G then G' is a proper
subgraph of G. If E' = Ef](V' x V') then G is an induced subgraph of G. One
2


Figure 1.2: A graph G, with subgraph G' induced by {'Ui, v2, u3}, and
edge-induced subgraph G" induced by {[uj,u2], [u3,u4]}.
also speaks of an edge-induced subgraph of a graph G. This is a subset E' C E,
together with the associated end-vertices. An induced subgraph will typically be
specified by describing its vertex set. If S C V(G), then the subgraph induced
by S is denoted by < S >. It is sometimes convenient to refer to the subgraph
induced by the complement of a subset S C V(G)\ in keeping with the notation
of sets (see, for example, Halmos [45]), such a subgraph will be denoted by G\S
or, if H =< S >, G\H. Similar definitions hold in the case of digraphs. See
Figure 1.2 for an illustration of a graph G together with an induced subgraph
and an edge-induced subgraph.
A graph G is said to be connected if, for all i,j, there exists a path connecting
Vi and Vj. A graph that is not connected is said to be disconnected. A bridge in
a connected graph G is an edge e with the property that G\e is disconnected.
Connectivity in a digraph D is a bit more complicated. If a directed path exists
from u to v in a digraph D, then u reaches v. The length of a path P is the
number of edges in P; P*. denotes a path on k vertices; this is a path of length
A: 1. The length of a cycle Z is identically defined; Z*. is a cycle on k vertices;
3


note that has length k. Z3 is aptly called a triangle. Note that Zk has k edges
as well as k vertices. A graph is said to be chordal, or triangulated, if it contains
no induced cycles Z^ for k > 4. A graph G is triangle-free if every cycle in G has
length at least four.
The distance d(x,y) between two vertices in a graph G is the length of the
shortest path from x to y. The same terms may be applied to a directed path
in a digraph, with the obvious meaning. When there is danger of confusion, the
distance from x to y in a specific graph G will be denoted by dc(x,y).
The order of a graph or digraph will be assumed to mean |V|, while the size
of a graph will refer to \E\. The notation |G| will be understood to mean the
order of G, and we define Qn to mean the set of all graphs of order n.
A coloring of a graph G is a function / : V{G) Z+ such that [x,y] 6
E(G) implies /(x) ^ f(y)', this can be conveniently thought of as an assignment
of colors to the vertices of G in such a way that no two adjacent vertices are
assigned the same color. This is commonly referred to in the literature as a
proper coloring. A k-coloring of G is a coloring using at most k colors; G is said
to be k-colorable if such a coloring is possible. The chromaticmumber X(G) is
defined by X(G) = min {k \ G is k-colorable}.
Three special cases of graphs are a complete graph Kn, in which all possible
edges are present in a set of n vertices, an empty graph, in which no edges are
present, and the trivial graph consisting of a single vertex. The graph consisting
of k isolated vertices is denoted /*.. None of these is particularly interesting in
4


its own right, although a special case of a complete graph has considerable value.
A clique in a graph G is a complete subgraph of G. A maximal clique has the
property that it is not a subgraph of a larger clique. The clique number cv(G)
of a graph G is the size of the largest clique in G. A consecutive ordering of the
maximal cliques C\,..., Cm of a graph G has the property that, for any x £ V(G),
if x £ C{ and x £ Ck, where i < k, then x £ Cj for all i < j < k. The clique
structure of a graph G provides a valuable tool in the present work.
The degree d(v) of a vertex v £ V(G) is defined by d(v) |{x £ V(G)\[x,v] £
£'(G)}|. We refer to any x satisfying [x,u] £ E(G) as a neighbor of v, the set
{x £ V(G)|[x,u] £ E(G)} will be called the neighborhood of v, denoted N(v). It
is occasionally useful to consider the closed neighborhood jV[u] = A"(u)U{u}. A
vertex v satisfying |iV(u)| = 0 is said to be isolated. A vertex v with the property
that N(v) is a clique is said to be simplicial; otherwise v is nonsimplicial. If
there is danger of confusion, the notation Ng{v) will denote the neighborhood of
v in the graph G.
A class of graphs that will play an important role in this work is that of trees.
A tree is a connected acyclic graph, i.e., the path connecting any two vertices
is unique. It is a well-known result in graph theory that a tree has at least two
pendant vertices, i.e., vertices of degree one. We will refer to a vertex in a tree
that is not pendant as an interior vertex. If a tree T has the property that
removal of all pendant vertices leaves a path, then T is called a caterpillar, for
reasons that are intuitively, if not entomologically, obvious. See Figure 1.3.
5


Figure 1.3: A tree T and a caterpillar C.
2/i 2/2 2/3
Figure 1.4: A complete bipartite graph.
A tree is an example of a bipartite graph. A bipartite graph G = (V, E)
permits a partition V X, Y of the vertices such that every edge e £ E is of
the form [xi,yj] where x,- £ X, yj £ Y. Every bipartite graph G is two-colorable,
i.e., if G is bipartite then X(G) = 2. A complete bipartite graph has the property
that [x,y] £ E(G) for all x £ X, y £ F. Such a graph is denoted Kmn, where
m = \X\ and n =. |y|. See Figure 1.4.
A vertex cover of a graph G is a subset C C V(G) with the property that
every edge e £ E(G) is incident to at least one vertex in C. An edge cover of
G is similarly defined to be a subset T C E(G) with the property that every
vertex is incident to at least one edge in T. Two related objects are a clique
cover, a collection of cliques of a graph G that contains every vertex of G, and
an edge clique cover, which is a collection of cliques of G that contains every edge
of G. Edge clique covers and their applications in graph theory have been widely
6


Figure 1.5: A comparability graph G with a transitive orientation;
graph K is not a comparability graph.
studied. See, for example, Roberts [83], Roberts and Steif [85], or Brigham and
Dutton [13].
An orientation of a graph G is an orientation of its edges, i.e., the edge [x,y]
is replaced by one of the arcs (x,y) or (y,x). So an oriented graph is a digraph.
A digraph D is transitive if the relation defining its arcs is transitive: for any
x,y,z £ V(D), if (x,y),(y,z) £ A(D) then (x,z) £ A(D). A graph that permits
a transitive orientation of its edges is called a comparability graph. See Figure 1.5
for an illustration of a comparability graph G and a transitive orientation of
its edges. The graph K in Figure 1.5 is not a comparability graph, since every
possible orientation contains at least one triple x,y,z such that (x,y) and (y,z)
are arcs but no edge exists connecting x to z. In the uncompleted orientation of
K in Figure 1.5, no transitive orientation of the final edge is possible.
Given an arbitrary graph G, its complement Gc is defined by V(GC) = V(G)
and E(GC) = (V x V) E(G). A graph and its complement are shown in
Figure 1.6.
7


A graph G is said to be perfect if X(G') = oj{G') for every induced subgraph
G' C G. Perfect graphs have been the object of intensive study since they were
first described in the literature by Berge [2] in 1961. One of the preeminent open
problems in graph theory today is to either prove or provide a counterexample
to the strong perfect graph conjecture, first stated by Berge [3]. The conjecture
has several equivalent forms, perhaps the simplest of which is this: A graph is
perfect if and only if it contains no induced subgraph isomorphic to either an odd
cycle of length greater than three or its complement. While the conjecture has
been shown to be correct for several classes of graphs, it has not been proven
for undirected graphs in general. Golumbic [30] has assembled a comprehensive
body of material on perfect graphs. See also Berge [4, 6], Fulkerson [26, 27], and
Lovasz [59, 58]. Many classes of perfect graphs have remarkable effectiveness in
applications, and the graphs comprising the central topic of this thesis fall into
such a class. Before these graphs are introduced, though, a brief discussion of
the connection between graphs and matrices is in order.
8


Graphs and Matrices
There are several natural ways to associate a graph or digraph with a (0,1)-
matrix. If D = (V, A) is a digraph, the adjacency matrix A(D) is the |V| x |Vj
matrix whose i, gentry is one if (i,j) £ A and zero otherwise. The adjacency
matrix of a graph G is analogously defined and is of course symmetric. The
incidence matrix of D is the |Vj x |A| matrix whose (i,j)-entry is one, if vertex i
is incident to arc j, and zero otherwise. A third matrix that can be derived from
a graph is the clique matrix, more properly called the vertex-maximal clique
incidence matrix, denoted C(G). See Figure 1.7 for examples of the adjacency
matrix of a digraph D and the adjacency, incidence, and clique matrices of a
graph G. For a thorough discussion of graphs and matrices, see Roberts [80] or
Harary, Norman, and Cartwright [47].
A matrix property that will be useful in characterizing an important class
of graphs is the consecutive ones property. A (0,l)-matrix is said to have the
consecutive ones property for rows (respectively, columns) if it can be permuted
in such a way that all of the ones in any row (respectively, column) occur in
consecutive columns (respectively, rows).
Intersection Graphs
Before introducing the graphs that are central to this thesis, we must define
the class that contains them. This is the class of intersection graphs. Let T be a
9


va v2 v3 v4
D:
v4
e7
^3
el e2 e3 64 e5 66 e7
M(G)
Vl
V2
V3
Va
VS
V&
Vl 0 0 1 0
v2 1 0 1 0
A (D)-. v3 0 0 0 0
Va 1 0 1 0
Vl v2 v3 va Vs ve
Vl 0 1 0 1 0 0
V2 1 0 1 1 1 1
V3 0 1 0 0 0 1
A(G): v va 1 1 0 0 0 0
v5 0 1 0 0 0 0
v6 0 1 1 0 0 0
e7 Cl c2 c3
1 1 0 0 0 0 0
0 111110
0 0 0 0 0 1 1
1 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
C(G)
Vi
v2
v3
va
v5
ve
1
1
0
1
0
0
0
1
0
0
1
0
0
1
1
0
0
1
Figure 1.7: Digraph D with adjacency matrix A{D), graph G with adjacency
matrix A(G), incidence matrix M(G), and clique matrix G(G).
10


{6,c,/} {a,d,f}
G:
{a,b,c} {d,e} {e,^}
Figure 1.8: Intersection graph for a family of sets.
family of sets. The intersection graph G of T has V(G) = F, and if F{, Fj E F
with i / j then [Fi,Fj] E E(G) if and only if Fif]Fj ^ 0. For example, see the
graph G of Figure 1.8. Here F = {Fi, F2, F3, F4}, where Fi = {a, b, c}, F2 =
{a, d,/}, F3 = {b,c,f}, and F4 = {d, e}. The structure of intersection graphs
was studied by Kabell [53]. Marczewski [68] showed that every graph is the
intersection graph of some family of sets, so the property of being an intersection
graph is not particularly interesting. Certain subclasses are of interest, however,
and we are especially concerned with the class described in the next subsection.
Interval Graphs
Among the most useful classes of graphs in the context of applications is the
class of interval graphs. These graphs have been intensively studied by a large
number of researchers. Interval graphs were independently discovered by Hajos
[42] and Benzer [1], the former working in graph theory, the latter in molecular
biology. Early work that remains useful today was done by Lekkerkerker and
Boland [56], Gilmore and Hoffman [29], and Fulkerson and Gross [28]. Perhaps
the most comprehensive study is the treatise by Fishburn [25] in which interval
11


7:
a
d
G:
e
Figure 1.9: A family I of real intervals, and corresponding interval graph G.
Figure 1.10: Examples of asteroidal triples.
graphs are viewed in the context of interval orders. Interval graphs are perfect,
which gives them a chapter in Golumbic [30]. Interval graphs have a broad variety
of applications, but discussion of this is deferred to a later section.
Definition and Characterizations
An interval graph is typically defined as the intersection graph of intervals
on the real line. For an example, see Figure 1.9. Two characterizations are
standard in the literature. These will be stated without proof. The first is due to
Lekkerkerker and Boland [56] and describes interval graphs as being those graphs
not possessing any representative of a certain family of forbidden subgraphs. An
asteroidal triple is a triple {s, y, z} of vertices in a connected graph with the
property that, for any two of x,y, and z, there exists a path connecting them
12


that avoids the neighborhood of the third. See Figures 1.10 and 4.4 for several
examples.
Theorem 1.1 (Lekkerkerker & Boland) A graph G is interval if and only if it
is chordal and contains no asteroidal triple.
The minimal chordal graphs containing asteroidal triples are illustrated in Fig-
ure 4.4. The second characterization that will prove useful here is due to Gilmore
and Hoffman [29].
Theorem 1.2 (Gilmore & Hoffman) Let G be a connected graph. The following
are equivalent:
(i) G is an interval graph.
(ii) G is chordal, and Gc is a comparability graph.
(Hi) The maximal cliques of G can be consecutively ordered.
Also useful is the characterization due to Fulkerson and Gross [28], which
describes interval graphs in terms of their vertex-clique incidence matrices; this
is also stated without proof.
Theorem 1.3 (Fulkerson & Gross) An undirected graph G is an interval graph
if and only if the clique matrix M(G) has the consecutive ones property for rows.
Figure 1.11 shows a copy G of Z4 with its clique matrix M(G) and illustrates
the effect on the clique matrix of the addition of a single edge, creating the interval
graph H.
13


cx c2 c3 c4
J ^3
a ( i < >c a 10 0 1
G: M(G): b 110 0
c4 C2 c 0 110
Ci , d 0 0 11
a
d. 1 H a 1 1
M(H): (, 1 0
c 1 1
s' C2
* d 0 1
a
Figure 1.11: Illustration of theorem of Fulkerson and Gross.
Unit Interval Graphs
If G is the intersection graph of a family of intervals of unit length, then G is
said to be a unit interval graph. A proper interval graph is the intersection graph
of a family of intervals, none of which is properly contained in another. Roberts
[77] showed that these two classes of graphs are the same.
Higher Dimensional Analogues
A natural extension of the class of interval graphs is obtained by consider-
ing the intersection graphs of generalized spheres or rectangles in two or more
dimensions. Roberts [78] showed that every graph is the intersection graph of
boxes in Euclidean k-space for some k, where a box is a generalized rectangle
with sides parallel to the coordinate axes. He defined the boxicity, Box(G), to
14


Z4:

d
a c
b

Figure 1.12: Z4 with box representation.
be the smallest such k. In a similar vein, Maehara [67] showed that every graph
is the intersection of unit spheres in Euclidean A;-space for some value of k. The
smallest such k is called the sphericity Df a graph G. Figure 1.12 shows a copy of
Z\ together with its representation as the intersection of boxes in 9£2; it follows
that the boxicity of Z is two. It is not difficult to construct a similar analog
to Z using unit disks instead of boxes, showing that Z4 has sphericity two as
well. A complete graph Kn is said to have boxicity zero, since it may be viewed
as the intersection graph of n points superimposed. Boxicity and sphericity have
been studied extensively by Roberts [78, 82], Cozzens [20], and by Cozzens and
Roberts[22]. Cozzens [20] showed that computing the boxicity of an arbitrary
graph is ./VP-complete. In fact, graphs of boxicity two have not been character-
ized.
It is not hard to see that an interval graph necessarily has boxicity at most
one and that a unit interval graph has sphericity one. It is interesting to note that
the sphericity of an interval graph can be arbitrarily high. For example, consider
the interval graph K1>n. Roberts [77] has shown that ifli3 is not unit interval,
15


and it is simple to show that this graph has sphericity two, although it clearly
has boxicity one. K\$ still has sphericity two, although it is an easy exercise
in geometry to show that Kli6 cannot be the intersection graph of unit spheres
in 2-space; this graph has sphericity three. By choosing arbitrarily high n, it is
possible to construct a graph, namely K\>n, with boxicity one and arbitrarily high
sphericity.
Applications of Interval Graphs
Interval graphs have two properties that make them attractive in terms of
applications. First, they are easily recognized. Booth and Lueker [12] showed
that an interval graph can be recognized in time proportional to the sum of its
order and its size, i.e., 0(|V| + |I2|). Second, they are easily colored. Interval and
unit interval graphs can be colored in 0(|V|2) time. A generalized coloring, called
a T-coloring, can also be applied in 0(|V|2) time. See, for example, Cozzens and
Roberts [21], Raychaudhuri [75], Roberts [84], or Tesman [94].
Interval graphs provide a suitable model whenever a problem is time-dependent
or has an inherent physical restriction that allows a one-dimensional characteri-
zation. Roberts [82] describes the application of interval graphs to the problem of
assigning radio frequencies to mobile transmitters, to the measurement of prefer-
ence or indifference in sociology, and to seriation in archeology. The algorithmic
aspects of interval graphs are surveyed by Trotter [95]. Benzers [1] motivation
when he first became concerned with what are now known as interval graphs
16


was a problem in the structure of the gene. Golumbic [30] describes applications
of interval graphs in chemistry and in computer data storage and retrieval. Be-
cause of its coloring properties, an interval graph is desirable when translating a
real-world problem into a graph coloring problem.
Tolerance Graphs
A generalization of the class of interval graphs is the class of tolerance graphs.
G = (V,E) is a tolerance graph if there exists a collection X = {Ix|x £ V} of
intervals on an ordered set and a set T = {tx\x £ V} of positive real numbers
satisfying [x,y] £ E if and only if |7xf|^vl min{tx,ty}. The pair X,T is
a tolerance representation for G. If the tolerances satisfy tx c for all x £ V,
where c is constant, then we have the class of interval graphs. A bounded tolerance
graph is one whose tolerance representation satisfies tx < IX^ for all x £ V. These
graphs were introduced by Golumbic and Monma [31], and have been investigated
by Golumbic, Monma, and Trotter [32], Jacobson, McMorris, and Scheinerman
[51], and Jacobson, McMorris, and Mulder [50], as well as by other researchers.
Tolerance graphs share some, but of course not all, of the characteristics of interval
graphs. For example, every tolerance graph is the complement of a comparability
graph. Tolerance graphs are not necessarily chordal, since otherwise they would
be a subset of the interval graphs, but they have no cycles of length greater than
four. Like interval graphs, tolerance graphs are perfect.
17


G:
Figure 1.13: Graph G and clique graph K{G).
Derived Graphs
Given an arbitrary graph G, there are a number of graphs that may be derived
from G. If G is a graph with maximal cliques Ci,..., Ck, a useful graph K(G)
can be derived from G by letting V(K(G)) = {C|C is a maximal clique in G}
and E(K(G)) = {[C;, Cj]\Ci f|Cj 0}. This is called the clique graph of G. The
clique graph will prove to be a convenience in Chapter 4, and will play a role in
some interesting results regarding trees. See Figure 1.13.
Step Graphs and Powers of Graphs
The notion of a step graph was initially explored by Exoo and Harary [24].
The k-step graph Sk(G) of a graph G is the graph defined by V(Sk(G)) = V(G)
and E(Sk(G)) = {[i, j/]| there exists an (x,y)-path of length k in G}. Of particular
interest is the two-step graph ^(G). The two-step graph has also been called
the neighborhood graph in the literature. These graphs have been investigated by
Greenberg, Lundgren, and Maybee [40], by Exoo and Harary [24], by Brigham
and Dutton [14], and by Boland, Brigham and Dutton [9, 10], among others.
18


Two families of graphs are related to step graphs in a natural way. The kth
power Gk of a graph G is the graph defined by V(Gk) = V(G) and E(Gk) =
{[ai,y]| there exists a (u,v)-path of length j < k in G}. Thus G2 = G\J 82(G).
Raychaudhuri [75] has investigated powers of interval graphs. A graph H is said
to have a square root if it is the square G2 of some graph G. Graphs with square
roots have been characterized by Mukhopadhyay [70]. Finally we define a family
of graphs denoted Gk, where V(Gk) = V(G') and E(Gk) = {[z,y]|d(a:,2/) = A:}.
So [x,y] £ E(G2) if and only if d(x,y) = 2. These graphs have been studied
by McKay and Laskar [69]. It is easy to verify that, for any graph G, G2 Q
82(G) C G2. These graphs are illustrated in Figure 1.14. Note the missing edges
[c, d], [c, e] and [d, e] in G2. While paths of length two exist connecting each of
these pairs of vertices, since dc(c,d) = do(c, e) = dc(d,e) = 1, these edges are
19


omitted in construction of G2. In 52(G), note the missing edges [a, e] and [fc, c].
While these edges are present in G, no paths of length two exist from a to e or
from b to c, so these edges are omitted in construction of S2(G). In G2, all edges
are present since every pair of vertices of G is connected either by an edge or by
a path of length two. Under certain conditions, it can occur that G2 = S2(G) or
that 52(G) = G2. We describe these conditions in the following two theorems.
Theorem 1.4 Let G be a graph. Then 52(G) = G2 if and only if G is triangle-
free.
Proof: Suppose that 52(G) = G2, and let be a triangle in G. Then
[it,u], [V)W] and [u,iu] are edges in 52(G) but none is an edge in E(G2), a contra-
diction.
Conversely, suppose that G is triangle-free. Let [it, i>] £ E(S2(G)). Then
there exists z £ V(G) such that [it, z],[i>,z] £ E(G). Since G is triangle-free,
[u, u] 0 E(G), so [u, v] £ E(G2). If [utv] £ E(G2) then [u,u] £ E(S2(G)) since
G2 C 52(G). 1
Theorem 1.5 Let G be a graph. Then G2 = 52(G) if and only if every edge is
contained in a triangle.
Proof: First suppose that G2 = 52(G). Let [it, t?] £ E(G). If [it, u] is not
contained in a triangle, then [a,v\ £ E(S2(G), but G C G2, so [u,u] £ E(G2), a
contradiction.
20


Conversely, suppose that every edge [u,v] £ E(G) is contained in a triangle.
If [u,u] £ E(G2), then [u,u] £ E(S2(G)) since [u,u] is contained in a triangle. If
[w,u] £ E(S2(G)), then [u,u] £ E(G2) since ^(G) C G2. |
These derived graphs have natural interpretations in terms of matrices. If M
is an integer matrix, let B(M) be the corresponding Boolean matrix obtained by
= 1 if and only if Mitj / 0. Then if A(G) is the adjacency matrix
of a graph G we have A(S2{G)) = A2(G), A(G2) = B(A(G) + A2(G)), and
A(G2) = B(A2(G)) A(G).
It will be convenient to regard a derived graph as the functional image of a
graph. For example, we might regard the two-step graph 82(G) of a graph G as
the image of G under the function 52 : Qn Qn It then is reasonable to consider
whether a given graph H might have a preimage under 52, i.e., whether H =
52(G) for some graph G. This is the inversion problem studied by Greenberg,
Lundgren, and Maybee [40] and by Lundgren, Maybee, and McMorris [64].
Competition Graphs
The competition graph C(D) of an acyclic digraph D (V,A) is a graph
with V(C(D)) = V(D) and [x,y\ £ E(C(D)) if and only if 3 z £ V(D) such that
(x,z),(y,z) £ A(D). Figure 1.15 shows an acyclic digraph D and its competition
graph C(D). It was in studying ecosystems that Cohen [16] first developed the
idea of a competition graph. The graph-theoretic development of this idea was
continued by Roberts [81]. The assumption that the digraph D in question is
21


Figure 1.15: Acyclic digraph D with competition graph C(D).
acyclic is a reasonable one when D is being used to model the relationships
between predators and prey. This has an interesting effect on the competition
graph, which is of graph-theoretic interest in its own right. Since D is acyclic,
it has at least one vertex with no outgoing arcs. Such a vertex then becomes an
isolated vertex in the competition graph. Thus every competition graph has at
least one isolated vertex. Roberts [81] defined the competition number k(G) of
a graph G to be the least number k such that G U Ik is the competition graph
of an acyclic digraph. If G is a connected graph with size e, then it is easy to
construct an acyclic digraph D such that G\JIe is the competition graph of D.
The construction is as follows. Let D initially have the same vertex set as G,
with no arcs. For each edge [x,y\ E E(G), add a vertex vxy and arcs (x,vxy) and
(y,vxy) to D. Then G = C(D). Thus k(G) is well-defined. In general, computing
the competition number of a graph is a difficult problem; indeed, Opsut [71]
showed that this is NP-complete. Graphs with given competition number were
studied by Lundgren and Maybee [62].
When a digraph arises in some context other than that of an ecological model,
it is quite likely to have cycles, perhaps even loops. Competition graphs arising
22


in this way were characterized by Dutton and Brigham [13], in the case where
loops are allowed, and by Roberts and Steif [85] in the case where loops are not
allowed.
There is a natural way to define the competition graph C{G) of an undirected
graph G. Let V(C(G)) = V(G) and include [x,y] £ E(C(G)) if and only if there
exists z £ V(G) such that [x, z\, [y, z] £ E(G). While this does not guarantee
that C(G) is connected, even if G is, it does eliminate the phenomenon observed
in the case of competition graphs of acyclic digraphs, namely that every such
competition graph has at least one isolated vertex. This is because a graph G
can be viewed as a digraph D in which every arc (x,y) has mirror image (y,x),
implying a potentially large number of cycles.
Generalized Competition Graphs
The competition graph described above is a special case of a graph called a
generalized competition graph. If D is a digraph and V(D) = B\JC, then the
generalized competition graph is defined to be the graph GC(D), with vertex
set B and and edge [x, y] £ E if and only if there exists z £ C such that
(x,z),(y,z) £ A(D). If D is acyclic and if B C then we have the competition
graph C(D). Generalized competition graphs have been studied by Lundgren,
Maybee, and Rasmussen [66], by Raychaudhuri and Roberts [76], and by Roberts
[83].
The competition graph is also the special case p 1 of the p competition
23


graph studied by Kim, McKee, McMorris, and Roberts [55]. In the p-competition
graph of a digraph D, two vertices x,y are considered to compete if and only
if there are vertices a1}...,ap such that (as, and (y,a;) are arcs for every
1 = 1,... ,p. The case p 2 has been studied by Isaak, Kim, McKee, McMorris,
and Roberts [49].
Related Graphs
One obvious relative of the competition graph is obtained by considering
two vertices related if and only if they have not a common prey but a common
predator. The result is called the common enemy graph. The niche graph of
a digraph is the union of its competition graph and its common enemy graph.
Niche graphs are studied by Cable, Jones, Lundgren, and Seager [15], and by
Sakai [87]. The niche number n(G) of a graph G is the least k such that G U 7* is
the niche graph of some acyclic digraph. The competition-common enemy graph
of D is the intersection of its competition graph and its common enemy graph.
These graphs were introduced by Scott [89], who defines the double competition
number, dk(G), of a graph G to be the least integer k such that G\JIk is the
competition-common enemy graph of an acyclic digraph. The double competition
number dk(G) is shown to be well-defined in a manner analogous to that used for
k(G). Bounds on dk(G) for arbitrary G were obtained by Scott [89]. The double
competition number of the complete 3-partite graph K(n n n) was investigated by
Jones, Lundgren, Roberts, and Seager [52].
24


An (i, j)-competition graph is defined as follows in the work of Hefner, Jones,
Kim, Lundgren, and Roberts [48]. An acyclic digraph D is said to be an (i,j)-
digraph if, for every vertex x, id(x) < i and od(x) < j, where id{x), the indegree
of x, is the number of arcs of the form (?j, as) and od(x), the outdegree of x, is
the number of arcs of the form (x,v). If every x satisfies id(x) = 0 or i then i
is replaced by 1 in the notation; j is replaced by j if every x satisfies od(x) = 0
or j. Thus we obtain (z,j), and (z, j)-digraphs. A graph G is a (u,v)-
competition graph, where u £ {z,z} and v £ {j, j}, if G is the competition graph
of a (u, ^-digraph.
Bergstrand and Jones [7, 8], and Lundgren, Maybee, and McMorris [64] have
investigated the following question. Given a pair of graphs G and H, under
what conditions does there exist a digraph D with the property that G is the
competition graph of D and H is the common-enemy graph of D? Current results
concern digraphs D that are either acyclic or digraphs of partial orders.
Applications of Competition Graphs
It has been mentioned that the origins of the idea of a competition graph
lie in the application of graph theory to a problem in ecology. Specifically, the
competition graph is derived from a food web, which is a digraph D with vertices
corresponding to species in an ecosystem. An arc (x, y) represents the fact that
species x preys on species y. Starting with the introduction of this model by
Cohen [16], food webs have been the object of continued study by Cohen [17, 18,
25


19] as well as by Brigham and Dutton [13], Lundgren and Maybee [62, 63], Opsut
[71], Roberts [81], Steif [91], Sugihara [92, 93], and Roberts and Steif [85].
Generalized competition graphs have been applied to other problems, as well.
Raychaudhuri and Roberts [76] surveyed several applications of generalized com-
petition graphs, including several that lie outside of the study of ecology.
Consider the problem of communicating over a noisy channel. If we have a
transmission alphabet B and a receiving alphabet C, we construct a digraph D
with V(D) = B\JC and an arc (b,c) £ A(D) if and only if b £ B could be
received as c £ C. The generalized competition graph G(D,B,C) is called the
confusion graph corresponding to the channel. First studied by Shannon [90],
additional work has been done by Berge [5], Roberts [82], Haemers [41], Hales
[44], Li and Li [57], Lovasz [60], Rosenfeld [86], and Schrijver [88].
It is quite common, in the context of computer modeling of systems, to be
confronted with a large matrix M = (m^j). This can occur when solving systems
of differential equations by numerical techniques, when solving a linear program-
ming formulation, or when analyzing networks. If we define a digraph D by
letting B be the rows of M, C the columns, V(D) = B\JC, and (6, c) £ A(D),
where b £ B and c £ C, if and only if TOfe|C ^ 0, then the competition graph
G(D, B, C) joins two rows of M with an edge if and only if each has a nonzero
entry in the same column. This is the row graph of M, studied by Greenberg,
Lundgren, and Maybee [34, 35, 36, 37, 38, 39, 40], by Greenberg [33], Provan [73],
and Provan and Kydes [74]. The column graph CG(M) of M is similarly defined.
26


Note that, if M is the adjacency matrix of a digraph D, RG(M) = C(D), the
competition graph of D.
Lundgren [61] has published a survey of recent results on competition graphs
and their related graphs. Another comprehensive survey of the growing body of
work in this area can be found in Kim [54].
The Channel Assignment Problem
Consider the problem of allocating radio frequencies in a congested area. Let
the range of a transmitter T be the area in which a receiver is capable of intercept-
ing a signal from T. If two transmitters whose ranges.intersect are assigned the
same frequency, then a receiver placed in the intersection of their ranges is faced
with a potentially chaotic situation in which two signals are received simultane-
ously. Thus it is necessary that transmitters whose ranges intersect be assigned
distinct frequencies. On the other hand, given a fixed bandwidth there are lim-
itations on the total number of available frequencies. Assignment of frequencies
in such a way that the number of available frequencies is not exceeded and no
transmitters are in conflict is a difficult problem. A number of researchers have
investigated the application of graph theoretic and other models to this problem,
including Hale [43], Cozzens and Roberts [21], Cozzens and Wang [23], Proulx and
Rabinowitz [72], Lundgren, May bee, and Rasmussen [65, 66], and Raychaudhuri
and Roberts [76].
27


Generalized competition graphs can arise in the context of the channel assign-
ment problem. Raychaudhuri and Roberts [76] describe this in the following way.
Given are a set of points in the plane or, more generally, in where each point
is the location of a transmitter, a receiver, or a combined installation. A signal
originating at transmitter x can be received at receiver y if and only if d(x, y) < 8
for some fixed 8, where the distance is Euclidean. The situation can be modeled
by a digraph with vertices B\JC, where B is the set of transmitters and C the
set of receivers. If x £ B and y E C, the arc (x,y) is present if and only if
2/) < 8. The generalized competition graph G(D,B,C) then represents the
conflict among transmitters. If we assume that B = C, implying a combined
transmitter-receiver installation at each point, then D is symmetric and can be
represented by an undirected graph G. Assignment of frequencies can then be
modeled by a coloring of the competition graph C(G). Since coloring graphs is,
in general, a hard problem, it is desirable that the competition graph be interval,
or at least chordal. Good algorithms exist for coloring these classes of graphs.
The graph G constructed above is the intersection graph of closed spheres of
radius 8 in Euclidean A)-space, so it is a graph of sphericity at most k. The funda-
mental graph-theoretic questions raised are these: How does one characterize the
competition graphs of graphs with sphericity at most k? Under what conditions
can these competition graphs be interval? In the context of the problem, we are
concerned with transmitters and receivers placed on land, on ships at sea and
in aircraft. Although the likelihood of airborne transmitters seems to imply a
28


three-dimensional problem, the thinness of the atmosphere relative to the range
of a transmitter allows us to be concerned only with k = 2.
Raychaudhuri and Roberts [76], reasoning that d(x,x) < S, placed a loop at
each vertex of the graph G and solved the problem for k = 1.
Description of the Thesis
The primary goal of the research presented here is to deepen the results ob-
tained by Raychaudhuri and Roberts [76] in their study of generalized competi-
tion graphs as related to the channel assignment problem. The main questions
concern conditions under which the competition graph of a loopless symmetric
digraph is an interval graph.
This thesis falls neatly into three main divisions. In Chapter 2, the aforemen-
tioned work of Raychaudhuri and Roberts is sketched. Their work is described
there because of the profound influence that it exerted on the remainder of the
work presented in the second chapter. The difference between their fundamental
assumptions regarding the digraphs of interest and those of the author result in a
different characterization of the competition graph, and results parallel to theirs
are obtained, up to a point. Competition covers are then introduced, and the
relationship between competition covers and interval competition graphs is ex-
plained. These covers are then applied to the problem of establishing conditions
under which the competition graph of a loopless symmetric digraph D is interval,
given that the undirected graph underlying D is interval. The chapter includes
29


a catalogue of special cases of interval graphs with interval two-step graphs, but
does not address the general problem. Chapter 2 concludes with an enumeration
of those cycles with interval competition graphs.
Chapter 3 is concerned with the possibility of completely characterizing inter-
val graphs that have interval two-step graphs. Such a characterization is shown
to be possible, using a carefully constructed competition cover. In an effort to
extract from this result something with intuitive value, a partial characteriza-
tion is produced in terms of forbidden and necessary subgraphs, but this work is
incomplete at the present time.
In Chapter 4 we abandon the assumption that the symmetric digraph in
question has an interval underlying graph, producing a characterization of non-
interval trees with interval competition graphs. The techniques of Chapter 4 are
distinct from those of Chapters 2 and 3; inversion of two-step graphs, rather than
construction of competition covers, is the primary tool. Following the character-
ization of trees with interval competition graphs, we investigate the existence of
trees whose competition graphs are invertible. The two-step graphs of trees are
characterized, and an algorithm is presented that, given an appropriate graph
H, produces a tree T such that H is a component of ^(T). A class of trees is
identified with the property that, for any tree T in the class, T is the unique
acyclic preimage of its two-step graph.
Chapter 5 is a brief summary of the thesis. Directions for further research are
identified, and open problems are discussed.
30


CHAPTER 2
CLASSES OF INTERVAL GRAPHS WITH INTERVAL
COMPETITION GRAPHS
In this section we discuss several classes of interval graphs whose competition
graphs are also interval. Competition graphs of two types are discussed. The
model being used depends upon whether the symmetric digraph with which the
problem originates is assumed to have loops or not. The chapter closes with a
brief, but complete, characterization of those cycles with interval competition
graphs.
Interval Graphs with Interval Squares
In the search for a graph-theoretic solution to the channel assignment problem
discussed in the introduction, Raychaudhuri and Roberts [76] assumed naturally
that the digraph in question had a loop at each vertex. They obtained the
following results.
Proposition 2.1 Suppose that D is a symmetric digraph with a loop at each
vertex, H is its underlying graph, and H' is H with the loops removed. Then the
competition graph of H is (H')2, the square of H'.
This proposition is easily seen to be true, since the presence of loops leads to


competition between neighbors as well as among those vertices having common
neighbors. This is because in the square H2 of a graph H there is an edge
[it, u] £ E(H) if either [it, u] £ E(H) or [it, u] £ N(w) for some w. The next
proposition characterizes the competition graphs of unit interval graphs in terms
of their clique structure. Conditions (i) and (ii) together are equivalent to the
statement that G has a square root; condition (iii) states that G is unit interval,
by a result of Roberts [79].
Proposition 2.2 Suppose that G is a loopless graph with n vertices. Then G is
a competition graph of a unit interval graph with a loop at each vertex if and only
if G has an edge clique covering C = {C\, C2, , C^} and a labeling of vertices
as v 1,... ,un so that the following conditions hold:
(i) for all i, vt £ Cl;
(ii) for all i 7^ j,Vi £ Cj if and only if Vj £ Cx;
(iii) if i < j < k and £ Cu then Vj £ C{ and Vj £ Ck-
Proposition 2.3 If H is a (loopless) unit interval graph, then H2 is a (loopless)
unit interval graph.
The last result raises immediate questions. For example, what can be said
when H is interval, but not unit interval? This relaxation of the original problem
was solved by Raychaudhuri [75]. Proposition 2.3 gives sufficient conditions, but
not necessary conditions. Necessary conditions remain unknown. The previous
32


work revolved around symmetric digraphs with loops at each vertex. An obvious
question to ask is this what happens when the loops are removed? What
graphs are the competition graphs of symmetric digraphs with no loops, and
under what conditions are these competition graphs interval? It is in pursuit of
the solutions to these questions that the bulk of the work presented in this thesis
was done.
Interval Graphs with Interval Two-Step Graphs
A natural first step in attempting to characterize the competition graphs of
loopless symmetric digraphs, and to investigate conditions under which they are
interval graphs, is to seek results analogous to the three propositions above.
Theorem 2.1 Suppose that D = (V, A) is a loopless symmetric digraph and
H = (V, E) is the undirected graph corresponding to D. Then the competition
graph C(D) is the 2-step graph S2(H).
Proof: [x,y] £ E(C(D)) if and only if there exists z £ V s.t. (x, z),(y,z) £ A
if and only if there exists z £ V s.t. [x,z], [y,z\ £ E(H) if and only if [x,y\ £
E(S2(H)). |
The absence of loops in D is responsible for the difference between Proposition
2.1 and the preceding theorem. It is also possible to characterize competition
graphs of loopless unit interval graphs in a fashion analogous to proposition 2.2
above. The only difference between Proposition 2.2 and the following theorem
33


lies in condition (z).
Theorem 2.2 A graph G is a competition graph of a loopless unit interval graph
if and only if G has an edge clique covering C = {Ci,..., Cn} and a labeling of
vertices as v1,.. ., vn such that the following conditions hold:
(i) Vi ^ Cx;
(ii) Vi £ Cj if and only ifvj £ Ci;
(Hi) if i < j < k and Vf. £ Cl; then Vj £ Cx and Vj £ C*.
Proof: By Theorem 2.1, it suffices to show that the theorem characterizes graphs
that are the 2-step graphs of unit interval graphs. Suppose that G = S2(H) where
H is a unit interval graph. A linear order v\,..., vn of V is called compatible with
H if whenever i < j < k and Uj is adjacent to Vk, then Vj is adjacent to both
and Vk- By a result of Roberts [79], H is a unit interval graph if and only if H
has a compatible linear order u1;... ,vn. Let Ci = N(vi), the neighborhood of Vi.
We will show that C = {(7i,..., Cn} is an edge clique covering (ECC) of G that
satisfies conditions (i)-(iii).
(1) C is an ECC of G: Consider any edge £ E(G). Since G S2(H), there
exists z £ V(H) such that [vi,z\,[vj,z] £ E(H). Then Vi,Vj £ Cz. Moreover, Cz
is a clique in G by definition of S2(H). Thus C = {Ci,..., (7n} is an ECC of G.
(2) C satisfies (i)-(iii):
(i) Vi $ Ci by definition, i.e., Ci = N(vi).
34


(ii) Vi £ Cj if and only if Vj £ Ci, since vl £ Cj if and only if ut £ N(vj) if and
only if Vj £ N(vi) if and only if Vj £ Ci.
(iii) If i < j < k and vk £ Ci, then Vj £ Ci and Vj £ C*. This follows since
Vi,V2,... ,vn is a compatible linear ordering of V(H), i.e., v£ Ci implies
that Vic is adjacent to Vi in H, implying that vj is adjacent to both Vi and
Vj in H, which in turn implies that Vj £ Ci and Vj £ Ck-
Now suppose that G has an ECC C and a labeling of vertices as Vi,... ,vn
satisfying (i)-(iii). We must find H such that G S2(H) and H is a loopless
unit interval graph. Define H = (V,E') to be the graph with V(H) = V(G) and
E'{H) = {,rij]|Vj £ Ci}. We show that G 82(H) and that H is a loopless
unit interval graph.
(1) G = S2(H): We have [vi,vy] £ E(G) if and only if there exists k such that
[uJfcju;]j £ E(H), by (i) and the construction of H. Also [wi,Uj] £ E(S2(H))
if and only if there exists k such that [t^, Ufc], [vj, Vk] £ E(H). Thus Vj) £ E(G)
if and only if £ E(S2(H)).
G = S2(H).
(2) H is a loopless unit interval graph:
That H is loopless is clear from (i) and the construction of H. We show that
v-i,... ,vn is a compatible linear ordering of V(H).
By construction, £ E(H) if and only if Vj £ Ci. Suppose i < j < k and
[vi.t;*] G E(H). Then vk £ Ci. By (iii), Vj £ Ci and vj £ Ck, so [u,, Uj], [u*, Vj\ £
35


d
Figure 2.1: An Interval Graph H with Noninterval Competition Graph.
E(H).
v-y,..., vn is a compatible linear ordering of V(H).
H is a loopless unit interval graph. |
Unfortunately, if H is a unit interval graph, it is not necessarily true that
82(H) is a unit interval graph, so no analogue to Proposition 2.3 exists. In fact,
it it quite simple to construct a graph H that is unit interval whose 2-step graph
82(H) is not even chordal, much less interval. Figure 2.1 shows such a graph. This
raises several questions. What conditions on H will force S2(H) to be interval or
unit interval? What relationships exist between H and 82(H)'?
The next theorem will be useful when we consider the competition graphs of
trees; it follows directly from a result of Greenberg, Lundgren, and Maybee [40],
and is stated without proof.
Theorem 2.3 Suppose that H is connected. Then the following are true.
(i) 82(H) has at most two components.
(ii) 82(H) has two components if and only if H is bipartite.
36


Competition Covers
Our main interest is in determining when 82(H) is either interval or unit
interval. To do this, we will need the following definition.
A family of sets S = {Si,..., 5V} of vertices of H will be called a competition
cover of H if the following conditions are satisfied:
(i) If ^ Vj 6 Sm then there exists Vk £ V(H) s.t. V{,Vj £ N(vk).
(ii) If Vi ^ Vj £ N(vk) for any k then Vi, Vj £ Sm for some m.
A competition cover of a digraph D is similarly defined, with vt, Vj £ N(vk)
replaced by (vi,Vk),(vj,Vk) £ A(D) in (i) and (ii) above.
Observe that if S is the set of open neighborhoods of H, then S is a compe-
tition cover, but other sets will also work. Also note that S is not necessarily a
cover in the usual sense, i.e., a vertex cover or edge cover. S is a cover in that it
covers all of the competition in H.
Competition Covers and Interval Two-Step Graphs
We say that a ranking Si,..., ST of a competition cover of H is consecutive if
whenever a vertex x is in 5, and Sj for i < j, then x £ Sk for alii < k < j, and
refer to a competition cover that allows such an ordering as a consecutive compe-
tition cover. The following result of Lundgren and Maybee [63] is of fundamental
importance.
37


Theorem 2.4 (Lundgren & Maybee) The competition graph G of a digraph D
is an interval graph if and only if D has a competition cover S with consecutive
ordering.
Proof: It must first be shown that the sets C{ E S correspond to the cliques of
G. If u, v E Ck for some k, then by definition of competition cover there exists x
such that (u, x), (v,x) E A, so by definition of competition graph [u, u] E E(G).
Conversely, if [u,u] E E(G) then there exists x such that (u,x),(v,x) E A,
implying that u,v E Ck for some k.
Now suppose that G is an interval graph. Since the set S = {Ci,..., Ck} of
maximal cliques of G covers all edges of G, then by definition S is a competition
cover of D. By the result of Gilmore and Hoffman [29], S has a consecutive
ordering.
Conversely, suppose that D has a competition cover S = {Ci,..., Ck} that
has a consecutive ordering. Since S is a competition cover of D, the sets C{
correspond to cliques in G, and these cliques inherit the consecutive ordering
from S. |
The next theorem relates consecutive competition covers to interval 2-step
graphs.
Theorem 2.5 Let H be a graph. Then S2(H) is an interval graph if and only if
H has a competition cover S with a consecutive ordering.
Proof: By Theorem 2.4, the competition graph of a digraph D is an interval
38


Figure 2.2: Illustration for proof of Theorem 2.5.
graph if and only if D has a competition cover S with a consecutive ordering. By
Theorem 2.1, 82(H) is the competition graph of D(H), the symmetric digraph
obtained by replacing edge [p,q] 6 E(H) with arcs (p, q),(q,p) for all \p,q] 6
E(H). In other words, 82(H) is an interval graph
(i) if and only if the competition graph G of D(H) is an interval graph (by
Theorem 2.1)
(ii) if and only if D(H) has a competition cover with a ranking that is consec-
utive (by Lundgren and Maybee [63])
(iii) if and only if H has a competition cover with a ranking that is consecutive
(by definition of competition cover), completing the proof. |
For an illustration of this theorem, see Figure 2.2. Let Si = {d,/},S2 =
{a,c, d},S3 = {b, c, d}, and S4 = {b, c, e}. Then S {Si, S2, S3, S4} is a compe-
tition cover of H and this ordering is consecutive. Note that S2(H) is interval.
Also note that if we had let S consist of the neighborhoods of H then we could
not have found a consecutive ranking, i.e., {a, c, d}, {6, d}, {&, c, e}, and {d,/}
cannot be consecutively ordered.
39


Figure 2.3: Forced P4 of Lemma 2.1.
Certain Classes of Interval Graphs with Interval Two-Step Graphs
Theorem 2.5 is useful when appropriate restrictions on H force the existence
of a competition cover with a consecutive ranking. The difficulty of applying
the theorem lies in designing the correct competition cover, as the next three
theorems illustrate.
P4-Free Graphs
In this section it is shown that if an interval graph H is P4-free, i.e., if H
contains no induced subgraph isomorphic to a path on four vertices, then S2(H)
is interval. This depends upon the following lemma, itself a somewhat surprising
result. Figure 2.3 illustrates the proof.
Lemma 2.1 If H is P4 free, connected and interval, then there exists some
vertex v that is contained in every maximal clique of H.
Proof: We show that if H is interval and there does not exist v common to
every maximal clique, then H contains a P4. Under the assumptions, H must
contain at least three maximal cliques, since otherwise H would contain some
40


vertex v common to all maximal cliques. Since H is interval, we may find a
consecutive ordering C\,.. ., Cn of the maximal cliques. Given such an ordering,
let Cjy and G*, be maximal cliques satisfying j = max{i\Ci f| Cj ^ 0} and k =
max{i|Cj D / 0}. Clearly there is no vertex common to all three. We may
then find vertices p E (C\ f) Cj)\Ck and q E (Cj f| Ck)\C\.
Since p E Cj and q E Cj, [p, q] E E(H). Since the cliques are maximal, we may
also find u E C\\Cj and v E Ck\Cj such that [u, q] ^ E(H) and [v,p\ $ E(H),
since p Ck and q C\. Since H is interval, hence chordal, [u,v] ^ E(H) and
is the required P4, completing the proof. |
We are now ready to show the following result.
Theorem 2.6 If H is a P4-free connected interval graph, then S2(H) is an in-
terval graph.
Proof: We show that H has a consecutive competition cover. Since H is interval,
we may construct a consecutive ordering Ci,..., Cn of the maximal cliques. Since
H is also P4-free, then by Lemma 2.1 we may select some vertex v that is contained
in every maximal clique.
Let Si = H\{v}. Let S2 = IJ Ci. Clearly |Cil>3
two sets cannot help being so. We must show that S is a competition cover.
For E Si, p,? E N(y) since v E Ci,i = 1,... ,n. For p,q E S2, then if
and g/uwe have p, q E N(v)\ if p = v (without loss of generality q = v)
then, by construction of S2, there exists some vertex r such that p,g E N(r).
41


Figure 2.4: A P4-free interval graph, with dominating vertex c.
If p, q £ Si then 3 r such that p,q £ N(r).
Suppose that p,q £ N{k) for some k. If p ^ v and q ^ v then p, q £ AT('u),
hence in Si. If p = v (without loss of generality q = v) then k ^ v, so p and q
must be in a clique of size at least three containing v, hence p, q £ S2.
.\ If p,q E N(k) for some k then p, q E Si, i = 1 or 2.
Thus S is a competition cover. By Theorem 2.5, S2{H) is interval. g
For an illustration of Theorem 2.6, consider the graph H of Figure 2.4. The
maximal cliques of H can be consecutively ordered as {a, c}, {6, c}, {c, d, e, /},
and {c, e,g}. Vertex c is adjacent to all other vertices, so we let S\ = H\{c}.
We let S2 = {c, d, e, /} U{c, e,g}, the union of all maximal cliques of size at least
three that contain c. Then S {Si, S2} = {{a, b, d, e, /, g}, {c, d, e, /, g}} is easily
seen to be a consecutive competition cover. It should be pointed out that the
condition of being P4-free, while sufficient, is not necessary for the competition
graph to be interval. This will be illustrated in the next section.
42


Bridgeless Interval Graphs
The second class of interval graphs that can be shown to have interval com-
petition graphs, using Theorem 2.5, is the class of interval graphs in which every
edge is contained in a triangle. Since interval graphs are Z\t-free for k > 4, this
is precisely the class of bridgeless interval graphs.
Theorem 2.7 If H is an interval graph such that every edge is contained in a
triangle, then S2(H) is an interval graph.
Proof: Since H is interval, it has a consecutive ordering Cly... ,CT of maximal
cliques. Let Si = U f|C7^0}- Let 5 = {Si,..., Sr}. That S is
m>i
consecutively ordered follows from the consecutive ordering of the maximal cliques
of H. Indeed, suppose there exist i < j < k such that x £ Sif]Sk but x Sj.
Without loss of generality assume that i = max{m\m < j, x £ S'}, so that
x £ C{. It is clear that x £ Cj, since Cj £ Sj but x Sj. Since x £ Sk, there
exists n > k such that x £ Cn, but this contradicts the consecutive ordering of
maximal cliques in H. We must show that S is a competition cover.
First suppose that p, q £ Si for some i. If p,q £ Cj for some j, then there
exists some vertex r s.t. p,q £ N(r)\ this is because every edge is contained
in a triangle. If p,q $ Cj for any j, then the cliques containing p and q must
intersect C{. This results from the construction of Si. Let p £ Ctl and q £ Ci2.
Without loss of generality, assume < i2. Let r £ CiD Ci2. Since the cliques are
consecutively ranked, and since i < i^ < i2, then r £ C^ and so p, q £ N(r).
43



h
H:
a
b
d
b
d
f
e
e
Figure 2.5: A bridgeless interval graph H and 52(ff).
if p,q 6 Si for some i then p, q G N(r) for some r.
Now suppose that p,q G iV(r) for some r. If \p,q] G E(H), then clearly
p,9 G Cj for some j, hence p, 9 G If [p, 9] ^ E(H), then [p,t*], [9,r-] are in
some pair of intersecting cliques Ci,Cj. Then p, q G 5; if i < j and p, 9 G Sj if
j < i.
if p, q G iV(r) for some r then p,q £ Si for some i.
Thus S is a competition cover of H. Since S has a consecutive ordering, we
conclude that, by Theorem 2.5, 52(if) is an interval graph. |
For an illustration of the competition cover constructed in the preceding proof,
consider Figure 2.5. In H, the maximal cliques are C\ = {a, b,h}, C2 = {b,c, h},
is easily seen to be a consecutive competition cover of H. Note that 52(ii) is
interval, and that the maximal cliques in 5'2(ii) correspond precisely to the sets
Si. This, as we see in the next chapter, is no coincidence.
We close this discussion with one more example of a class of interval graphs
44


that can be shown to have interval competition graphs. As in the preceding
cases, a particular competition cover is constructed, allowing the application of
Theorem 2.5.
Caterpillars
While not all trees are interval graphs, those that are interval are easily char-
acterized. Lekkerkerker and Boland [56] showed that an tree is interval if and
only if it is a caterpillar, i.e., removal of all pendant vertices leaves a path. We
show that the competition graph of a caterpillar is an interval graph.
Theorem 2.8 If H is a caterpillar, then 82(H) is interval.
Proof: We label the vertices of H as follows. Let P be a longest path in H. Label
the |P| 2 interior vertices of P as Vi,... ,U|p|_2 in the order in which they are
visited in traversing P. The remaining vertices are all pendant vertices in H]
label them in any order as x1?..., xm, where m = \H\ \P\ + 2.
Let Si = {W(u;)| i even}, and let S2 = {-/V(ui)| i odd}. No vertex of H
appears in both Si and S2, since if x £ N(vi)f]N(vj) where i is even and j is
odd then we must have a cycle in H. Each vertex u;, 2 < i < |P| 3, appears
in exactly two neighborhoods, namely N(v{_i) and N(vi+i). Vertices Vi,V\p\_2,
and each vertex X{ occur in a unique neighborhood, since H is a caterpillar. In
arranging the elements of each set Si, by letting N(vi) precede N(vj) if and only
if i < j we obtain a consecutive ordering of 5,-. Since no vertex appears in both
45


X2( T: 3( > 1 tx5 1 * x6
Xi v[ ^2 < ^3 1 X4 V4 V5 v6 V7 1 X7
X8
Figure 2.6: A Caterpillar T with its competition graph S2'(T) U S2"(T).
sets, then this consecutive ordering extends to S = Si\JS2. Since N(vi) £ 5
for every interior vertex V{, S is a competition cover. By Theorem 2.5, S2(H) is
interval. |
For an illustration of the procedure used in Theorem 2.8, consider the graph
T of Figure 2.6. The graph is shown following completion of the labeling. We
have Si = {{x1,x2,v2},{v2,vi,xA},{vA,vB}i{vex7ixg}}, and
S2 = {{^1,V3,Z3},{2:3,Z5,U5},{U5,X6,'U7}}.
By construction, Si and S2 are distinct, and both are consecutively ordered.
Note that the two components S2'(T) and S2"{T) are both interval, and that
they correspond exactly to the sets S\ and S2, respectively. Note also that the
maximal cliques in S2'(T) and S2\T) correspond to the subsets of of vertices of
T that were used to construct and 52, respectively.
46


Two-Step Graphs of Cycles
Having spent the bulk of this chapter investigating the two-step graphs of
interval graphs, we move briefly to a class of graphs that are, with a single
exception, not interval. The class is that of cycles. It turns out to be a very
simple matter to completely enumerate those cycles that have interval two-step
graphs. The following two lemmas will be useful.
Lemma 2.2 If k > 1, then S2(Z2k+1) = Z2k+i-
Proof: Let G be an odd cycle. Choose any vertex of G, label it as and label
the remaining 2k vertices as v2,... ,v2k+i in the order in which they are visited
in traversing G. Then v1}... ,v2k+i,v2,.. ,v1 is a cycle in S2(G). By the way in
which G is labeled, E E(S2(G)) if and only if |i j \ = 2, so no other edges
are present and the result follows. |
Lemma 2.3 If k > 3, then S2(Z2k) = 2Zk.
Proof: Let G be an even cycle on 2k vertices, k > Z. Label G in the same
fashion used in the preceding lemma. As above, [vi,vf\ E E(S2(G)) if and only if
\i-j\ = 2, so and are induced cycles
in 52(G) and no other edges are present. |
The preceding two lemmas can be used to prove the following theorem, which
completely characterizes those cycles that have interval two-step graphs.
47


Figure 2.7: Graphs with induced ^-cycles, k > 3, and two-step graphs.
Theorem 2.9 The only cycles with interval two-step graphs are Z3, Z4, and Z6.
Proof: By Lemma 2.2, S2(Z3) = Z3. By Lemma 2.3, S2(Z6) = 2Z3. It is trivial to
show that S2(ZA) = 2K2. All of these two-step graphs are interval. Now suppose
that G is a cycle on k vertices, where k $ {3,4,6}. If k is odd then, since k > 5,
G is not interval. By Lemma 2.2, S2(G) is not interval. Suppose, then, that k
is even. Since k > 8 then, by Lemma 2.3, S2(G) = 2Zk/2, but Zk/2 is a cycle of
length at least four, hence not interval. |
Theorem 2.5 implies that consecutive competition covers can be found for Z3,
Z4, and Zq. For each of Z\ and Ze, labeled as in Lemmas 2.2 and 2.3, let Si = {wi|
i odd} and £2 = {^i| i even}. Then S = {5i, 52} is a competition cover, since any
pair of even-labeled vertices are in the neighborhood of an odd-labeled vertex,
and any pair of odd-labeled vertices are in the neighborhood of an even-labeled
vertex. That S is consecutively ordered is immediate, since |S| = 2. For Z3, with
48


vertices Vi,v2, and V3, we simply let S = {ui, v2, U3}. This is clearly a competition
cover and is, trivially, consecutively ordered.
Unfortunately, the results just shown apply only when G is, itself, a cycle. The
results are of no value for graphs containing such cycles as induced subgraphs. For
example, the graph G of Figure 4.12 contains several 4-cycles. S2(G), however, is
not interval. On the other hand, consider the graph H of Figure 4.12. H contains
an induced 5-cycle, yet S2(H) = Ke, an interval graph.
We now return our attention to the competition graphs of interval graphs.
The utility of Theorem 2.5 is limited by the fact that, for each candidate class of
interval graph, we must find the right competition cover. We would like to identify
a competition cover that could be easily constructed for any interval graph and
such that a consecutive ordering would be both necessary and sufficient for the
corresponding competition graph to be interval. This is the topic of the next
chapter, where we show that there indeed exists such a competition cover for
interval graphs.
49


CHAPTER 3
CHARACTERIZATIONS OF INTERVAL GRAPHS WITH
INTERVAL TWO-STEP GRAPHS
Construction of a Special Competition Cover
Whenever Theorem 2.5 was applied, it was necessary to construct a competi-
tion cover for each class of interval graph encountered. At a glance, these covers
seem sufficiently unlike one another that a pattern is difficult to discern. In the
case of the P4-free interval graph the cover consisted of a neighborhood together
with a union of large cliques, while in the case of the bridgeless interval graph
the cover consisted of unions of intersecting cliques. In the case of the caterpillar,
the appropriate cover was the trivial cover consisting of the neighborhoods of all
interior vertices. As it turns out, these are special cases of a cover that can be
constructed for any interval graph.
A Classification of the Nonsimplicial Vertices of a Graph
We begin by introducing a classification of the nonsimplicial vertices of a graph
G. At this stage, we are not concerned with any properties of G, such as whether
it might be interval, with the exceptions that we assume, throughout Chapter 3,
that G is neither empty nor complete. This is because neither condition is at all


II
III
d
I
/
H:
a
Figure 3.1: Classes of nonsimplicial vertices.
interesting in the context of competition; in an empty graph there is no interaction
at all among vertices, while in a complete graph all vertices compete.
(1) Let G be a graph, with maximal cliques C = {C\,..., Cm} and let v £ V
be nonsimplicial. Consider the subset of C that contains v. If every clique Ci
containing v satisfies |C,| > 3, then call v Type I. If every clique Ci containing
v satisfies |Cj| = 2, then call v Type II. If v is an element in cliques of both size
classes, then call v Type III. See Figure 3.1 for an illustration.
(2) Let G be as above, with nonsimplicial vertices Uj,... ,Vk For each non-
simplicial Vi, construct the set(s) Si as follows.
(i) If Vi is Type I, then Si = the closed neighborhood of Uj.
(ii) If Vi is Type II, then Si = N(vi), the open neighborhood of Uj.
(iii) If Vi is Type III, then we construct two sets:
Let Sij = £ Cj, \Cj\ > 3}, and let Si2 = N(vi).
Referring again to Figure 3.1, the resulting sets are S& = {a, c}> 5cL = {c,d,e},
SC2 = {b,d,e}, and Se {c,d,e, f, g}. Note that the collection of sets just
described is a competition cover of the graph G in Figure 3.1.
51


Nonsimplicial Competition Covers
The preceding competition cover of G consisted of sets of vertices that were
constructed on the basis of a classification of nonsimplicial vertices. We now show
that these sets always form a competition cover.
Lemma 3.1 Let G be a graph. Let S{G) be the collection of sets defined above.
Then S(G) is a competition cover of G.
Proof: We must show that S satisfies the definition, i.e., that if u, v £ Sk for any
u,v £ V(G) and Sk £ S then u,v £ jV(x) for some x £ V", and conversely.
First suppose that u,v £ Sk, where Sk £ S. Let Xk be the vertex associated
with Sk in constructing S. Three cases must be considered.
Case 1: Xk is Type I. If u Xk or v = Xk then by construction of Sk there
exists some vertex w such that u, v £ N{w). If both u ^ and v / Xk then
u,v £ N(xk).
Case 2: Xk is Type II. Then Si = N(vk).
Case 3: x* is Type III. If one of u Xk or v = Xk then Sk = Sk,- By the
construction of Sk, there exists w such that u,v £ N(w). If u Xk and v ^ Xk
then u,v £ N(xk)
If u,v £ Sk £ S then u,v £ N(x) for some x £ V(H).
Now suppose that u, v £ N(x) for some x £ V(H). There are two cases,
depending upon whether x is nonsimplicial.
Case 1: x is nonsimplicial. If [it,u] £ E(G) then either u, v £ Sx or u,v esXl,
52


depending on the type of x, which cannot be Type II. If [u,v\ ^ E(G) then either
u,v £ Sx or u, v £ SX2, depending again on the type of x, which cannot be Type I.
Case 2: x is simplicial. Then u, v, and x are contained in some maximal clique
Ci. Since G is connected and not complete, Ci contains at least one nonsimplicial
vertex x*. If Xk is Type I then u, v £ 5*; if Xk is Type III then u, v £ S^- It is
not possible that xj. is Type II, since is a triangle in N(xk).
If u, v £ N(x) for some x £ V(G) then u,v £ Sk for some 5* £ S.
S(G) is a competition cover of G.
This completes the proof of Lemma 3.1. |
We shall refer to S(G) as a nonsimplicial competition cover. The proof of the
following lemma is immediate.
Lemma 3.2 Let S'(G) = {?; £ competition cover of G.
We shall call S'(G) the maximal nonsimplicial competition cover of G. It will
also be shown that a necessary and sufficient condition for an interval graph G
to have an interval competition graph is that S'(G) have a consecutive ordering.
Before doing so, additional tools are required.
Lemma 3.3 Let H be an interval graph. Let S(H) be the nonsimplicial com-
petition cover of H, Si £ S(H), and Vi the vertex associated with Si in con-
struction of S(H). If x is any vertex such that [z,u;] ^ E(H), then the set
C = {v £ 5i|[s,u] £ E(H)} is a clique.
53


Figure 3.2: Illustration for proof of Lemma 3.3.
Proof: Let p, q £ Si, such that [x,p],[x,q] £ E(H), as shown in Figure 3.2. By
construction, p,q £ N(vi). By construction, p,q £ N(vi). H is interval, hence
chordal, and [x,r>;] is missing, so [p, q] £ E(H). |
We are now in a position to prove the following key lemma.
Lemma 3.4 Let H be an interval graph. Let S\H) = {Si,.. ., S'} be the max-
imal nonsimplicial competition cover of H. Let x £ V(H). If x is connected by
a path of length two to every vertex in some Si £ S'(H), then x £ Si.
Proof: Let Vi be the nonsimplicial vertex associated with Si in constructing S.
Case 1: Vi is Type I. Then Si = must contain at least two maximal cliques,
each containing Uj. We distinguish three subcases. It will be shown later that
subcases (ii) and (iii) also apply in the case where Vi is Type III, Vi (£ Si, and Vi
is incident to at least two maximal cliques of size at least three.
(i) First suppose that x is adjacent to no vertex in Si. Then x cannot be
connected to Vi by a path of length two, a contradiction.
x must be adjacent to at least one vertex in Si.
54


X
X
H2
Figure 3.3: Graphs for Case l.ii, Lemma 3.4.
(ii) Now suppose that x is adjacent to one or more vertices of exactly one
maximal clique in Si, say C. Let p £ C and [x,p] £ E(H). Clearly p ^ V{
since then x £ S{. Since x is also connected to p by a path of length two,
there exists q such that [x,g], [p,q] £ E(H). If q £ C, then we have the graph
Hi of Figure 3.3. Note that there exists some vertex r £ Si\C, since V{ is
Type I, and that r cannot be adjacent to any vertex adjacent to x in C. If,
for example, [p,r] £ E(H) then p would be contained in at least two maximal
cliques containing v;. So [p, r], [ t $ Si such that [x,i],[r,t] £ E{H). Clearly ^ E{H) since t 0 5,-. If
\jp, t] (resp.[g, t]) is an edge then (resp.< q, t,r,Vi > is an induced 4-
cycle; if \p,t] (resp.[g,tj) ^ E{H) then we have an induced 5-cycle
(resp.< q,x,t,r,Vi >). But H is an interval graph, so in either case we have a
contradiction.
Now if q C, then q £ Si, and we have the graph H2 of Figure 3.3. As
before, [p, r] ^ E(H). Also [g,Ui] ^ E[H). Now x must be connected to r by
a path of length two, by assumption. If [q,r] £ E(H) then < q,r,Vi,p> is an
induced 4-cycle; if [q,r] ^ E(H) then there exists some t £ Si such that either
55


or is an induced cycle of length at least four, again a
contradiction since H is an interval graph.
x cannot be adjacent to vertices of exactly one maximal clique in Si.
(iii) Suppose that x is adjacent to vertices of at least two maximal cliques
in S{. If [x,u;] £ E(H) then we are done, since then x £ Si. So assume that
[a:,Ui] ^ E(H). Let Cx = N(x)f]Si. By Lemma 3.3, Cx is a clique, so Cx C C*
for some maximal Ck containing Vi. Since Vi is Type I, Ck is not the only maximal
clique in St.
Claim: If Cj / Ck is a maximal clique in Si then Cjf]Cx 7^ 0.
By way of contradiction suppose that there exists Cj £ Si such that Cj f) Cx = 0.
Every vertex v £ Cj\{u,} must be adjacent to some vertex in Cx, for otherwise
we would have edges [x,t], [i,u] where t ^ Si. We then obtain an induced cycle
< x,t,v,Vi,p >, where p £ Cx, but this contradicts the assumption that H is
interval. This is illustrated in graph H1 of Figure 3.4. Now choose r £ Cj\vi
such that r is adjacent to as few vertices of Cx as possible. Since Cj ^ Ck, r 0 Ck-
Choose p £ Cx such that [:r,p) £ E(H), s £ Cj not adjacent to p, and q £ Cx
not adjacent to r. Note that both s and q exist, since p £ Cj and r ^ Cx. If
[s,g] £ E(H) then we obtain an induced 4-cycle as in the graph H2
of Figure 3.4, so assume that [s,g] ^ E(H). It has already been observed that
s must have at least one neighbor t £ Cx. If [t,r] 0 E(H) then we obtain an
induced 4-cycle , as in the graph H3 of Figure 3.4. So for every t £ Cj
satisfying [t, s] £ E(H) we have [t,r] £ E(H). But r is also adjacent to p, so r is
56


Figure 3.4: Subgraphs for Case l.iii, Lemma 3.4.
adjacent to more vertices in Cx than s, a contradiction. Thus Cj f|Cx 7^ 0, and
the claim is proven.
Now if some vertex adjacent to x, say p, is contained in every maximal clique
of Si then Sp 3 -S't Ufx}, contradicting the maximality of S,. This forces 5, to
contain at least two maximal cliques in addition to Ck, say Cj and Cm. Each of
these cliques contains at least one vertex of Cx, and these vertices must be dis-
tinct. Let pe Cj H Ck, p & Cm, q £ CkClCm, q & Cj. Letting r £ Cj\{Ck U Cm}
and s £ Cm\{Cxf]Cj} we may construct one of the induced subgraphs H4, H5
of Figure 3.4. Both contain asteroidal triples, so neither is interval, contradicting
the assumption that H is interval. Thus [x,w;] £ E(H) and so i £ S{.
If Vi is Type I and x is connected by a path of length two to every vertex
in Si, then x £ 5*.
57


Case 2: V{ is Type II. If [x,vi\ E{H) then x Si, so assume not. Now u,- is
adjacent to at least two vertices, say p and q, where [p,g] ^ E(H) since V{ is
Type II. Since x is connected to p and q by paths of length two, then we have
paths x,r,p and x,s,q, where possibly r = s. Both [r,Ui] and are forbidden
since v,- is Type II. If r = s then we have an induced 4-cycle ; if r ^ s
then contains at least one induced cycle of length at least four,
but this is a contradiction. Thus [x,Ui] G E(H) and so x G 5,-.
If Vi is Type II and if x is connected to every vertex of Si by a path of
length two, then x G as claimed.
Case 3: Vi is Type III.
(i) Suppose that Vi g Si. Then Si = Si2 = N(vi). If [x,-u] G E(H) then
x £ Si and we are done, so assume not. Since Vi is Type III we may find at least
one maximal clique C*., |G7fc| > 3, and at least one maximal clique Cj, \Cj\ = 2,
both containing Vi. Let p G C* and r G Cj\ note that [p,r\ ^ E(H). There exists
a path of length two from x to r not using Vi, so there exists some vertex q such
that [x,q], [q, r] G E(H). Note that q Si by our choice of r. Now either q is
connected by an edge to Ck\vi, or x is connected to Ck by another path, not using
q\ in either case we have an induced cycle of length at least four, a contradiction.
[x,Vi] G E{H) and x G Si.
(ii) Now suppose that Vi G Si. Then Si = SIf [x,i>i] G E(H) then x G Si
and we are done, so assume not. Let Cj,Ck,p, and r be as described above. If
[x,r] G E(H) then we get an induced fc-cycle, k > 4, in connecting x to p. So x
58


is connected by an edge to no vertex r ^ V{ that is contained in a maximal clique
C C N[vi] of size two.
In view of this, if Si contains at least two maximal cliques of size at least three
we may apply the Type I proof, subcases (ii) and (iii), verbatim. So assume that
Si contains exactly one maximal clique of size at least three, namely Ck- Either x
is adjacent to at least two vertices in Ck, say p and q, or x is adjacent to exactly
one vertex in Ck, say p, and is connected to p by a path of length two using
some s (f_ Si. In either case, Sp D Si U{cc}5 contradicting maximality of Si. So
[ai,u;] £ E(H), and x Si.
If Vi is Type III and x is connected to every vertex of Si by paths of length
two, then x £ Si. This concludes the proof of Lemma 3.4. |
Corollary 3.1 If Si £ S'(H), where H is interval, then Si is a maximal clique
in S2(H).
Proof: It is clear that the vertices in Si form a clique in S2(H), since S' is a
competition cover. Let C be a maximal clique in S2(H), such that Si C C. Let
x £ C, y £ Si. Since both x,y £ C, there is a path of length two from x to y
in H. Since y was chosen arbitrarily, this is true for all y £ Si. By Lemma 3.4,
x £ Si. Since x was chosen arbitrarily, C C Si, completing the proof. |
The real value of Lemma 3.4 is this connection that it forces between the sets
Si £ in place to prove the result alluded to earlier.
59


Characterization Using Nonsimplicial Competition Cover
Theorem 3.1 Let H be an interval graph and let S'(H) be the maximal non-
simplicial competition cover of H. Then S2(H), the competition graph of H, is
interval if and only if S'(H) has a consecutive ordering.
Proof: First suppose that S2(H) is interval. Then we may find a consecutive
ordering of the maximal cliques of S2(H). By Corollary 3.1, every set S{ G S'(H)
induces a maximal clique in S2(H). But if the maximal cliques of S2(H) are
consecutively ordered, then so is that subset of maximal cliques of S2(H) that
corresponds to S'(H). Thus S'{H) has a consecutive ordering.
Now suppose that S'(H) has a consecutive ordering. By Lemma 3.2 and
Theorem 2.5, S2(H) is an interval graph. |
Extension to Unit Interval Graphs
Roberts [77] showed that an interval graph is a unit interval graph if and
only if it does not contain K li3 as an induced subgraph. It is useful, then, to
determine when S2(H) contains an induced #1,3. The following theorem charac-
terizes graphs G whose two-step graphs have an induced in terms of induced
subgraphs.
Theorem 3.2 Let G be a graph. Then 52(G) has an induced KXtz if and only
if G contains an induced subgraph that is itself either a subgraph of Hx or H2
containing an embedded Hl Q or a subgraph of H2 containing an embedded H2<0,
60


Figure 3.5: Subgraphs for Theorem 3.2.
where these graphs are shown in Figure 3.5 and the embedding of Hip in Hi and
Hz is as shown.
Proof: Refer to Figure 3.6. Suppose that Hi is labeled as shown. Then S2(Hi) is
as indicated, and contains a Kii3 induced by {2,1/1,y2,2/3} Thus any subgraph H'
of Hi containing Hifi will induce a Ki_3 in S2(H'). Now consider the indicated
labeling of Hz and the corresponding S2(H2). Note that the set {23,1/1,2/2,2/3}
induces a Ki|3 in S2(H2)', any subgraph H' of H2 containing H1<0 must therefore
induce a Jf1|3 in S2{H'). Finally, consider the indicated labeling of H3 and the
corresponding S2(H3). The set {2,1/1, y2, y3} induces a Kii3, so any subgraph H'
of H3 containing H2io induces a Kii3 in S2(H').
It must now be shown that any graph G inducing a Kii3 in 52(G) must have
one of the listed subgraphs. Let G be such a graph, and let the induced KJ)3 in
52(G) be labeled {23,1/1,1/2,1/3} as shown in Figure 3.6. Since we have edges [2,3/*]
in 52(G) for i = 1,2,3, then there must exist vertices 2;, i = 1,2,3, where [2,1/i]
is the edge in 52(G) induced by the path 2, 2i,yi in G. Note that the X{ must be
61


y i i
a;
Figure 3.6: Graphs for proof of Theorem 3.2.
62


distinct, since otherwise some edge [yi,yj] would be present in S2(G). There are
now two possibilities.
Case 1: Kit3, as shown in Figure 3.6, is an induced subgraph of S2(G) and
{xi, x2, S3} n{2/i) 2/2) 2/3} = 0- These may be arranged in such a way that [as, 3/*]
is the edge in S2(G) induced by the path x,Xi,yi for i = 1,2,3. Then G must
contain Hli0 as a subgraph, where this subgraph is labeled as shown in Figure 3.6.
Now if [yi, Xj] were an edge for any i ^ j then the edge [yi, yj] would be present
in S2(G). Similarly at most one edge [yi,yj] or [x,j/j] can be present. Edges
[xt-, Xj] do not induce edges [yi,yj]\ all are allowed. Thus we obtain the maximal
preimages Hi, H2.
Case 2: ifli3 is an induced subgraph of S2(G) and {xi, x2, x3} n{l/i3 3/2>2/3} / 0-
Suppose that this intersection contained more than one element, say Xi = yi and
x2 y2 Then x is adjacent to both yi and y2 in G, hence [yi,y2] is an edge in
S2(G). So |{xi,x2,x3} D{2/i5 2/2) 2/3}I = 1. Without loss of generality suppose that
x2 = 2/1. Then #2,0, as labeled in Figure 3.6, must be present in G as a subgraph.
This subgraph cannot contain either an edge [y,-,x] for i ^ 2 or any edge [yi,yj]]
the only additional edge allowed is [xi,x3] and we obtain the maximal preimage
H3. I
We may use Theorem 3.2 to obtain the following result, characterizing those
interval graphs with unit interval two-step graphs.
63


Theorem 3.3 Let H be an interval graph. Then S2{H) is unit interval if and
only if H does not contain an induced H3 or an induced Hip, where these graphs
are as defined in Theorem 3.4-
Proof: First suppose that S2(H) is unit interval. Then S2(H) contains no K13,
by Roberts [77]. By Theorem 3.2, H contains no induced H3 or H2p.
Now suppose that H is interval and contains no induced H3 or H2io- Since H
is interval, it cannot contain any of the listed graphs of Theorem 3.2 as induced
subgraphs other than H3 or H3,o- By Theorem 3.2, S2(H) contains no induced
K\>3. By Roberts [77], S2(H) is unit interval. |
Some Remarks on Computational Complexity
While one might argue that the simplest way to discover whether the com-
petition graph of a graph H is interval is simply to calculate S2 and test it
using the PQ-Tree algorithm of Booth and Lueker [12], it should be pointed out
that the computational complexity of first constructing the clique matrix of H,
then deriving the set S and then testing it for consecutive ordering is compara-
ble. The time complexity of recognizing that H is interval and enumerating its
maximal cliques is 0(|F| + |.E|), using the PQ-Tree algorithm. From the clique
matrix we may construct S(H) in time proportional to |V|2, and apply the PQ-
Tree algorithm again to determine whether S{H) has a consecutive orientation.
Thus the overall complexity of application of Theorem 3.1 is 01V'l2. If we use
64


the approach of computing £2{H) and testing it directly, we must first compute
A2(H) A(H) in 0\V\2 time and then test for consecutive ordering of maximal
cliques in 0(|V| + |E|) time. The difference between these approaches then lies
in the constant of proportionality. On the other hand, the computational value
of Theorem 3.3 is doubtful, since detection of a forbidden subgraph of order k
requires time proportional to |VI*, with a potentially large constant of propor-
tionality. In other words, if a forbidden subgraph has k vertices, then all of the
possible configurations must be tested in each of its fc! possible arangements
before it can be concluded that the forbidden subgraph is not present.
Characterization in Terms of Subgraphs
The previous section featured a characterization of interval graphs with in-
terval competition graphs in terms of a competition cover that had its basis in a
classification of vertices. We now show that this classification enables us to say
more about the structure of such graphs in terms of subgraphs.
Recall that the graph of Figure 2.1, while unit interval, failed to have an inter-
val competition graph. It turns out that this graph is the minimal representative
of an infinite family of interval graphs that have noninterval competition graphs.
This family can be defined in terms of its Type III vertices and related subgraphs.
65


Figure 3.7: Graph G, with edge-induced G and G*.
Limitations on Number and Location of Type III Vertices
For convenience, we shall adopt the following notation. Let G be a graph.
Define G to be G with all bridges and subsequent isolated vertices removed.
Define G* to be the edge-induced subgraph of G induced by its bridges. See
Figure 3.7 for an illustration of a graph G together with both subgraphs.
Lemma 3.5 Let H be an interval graph. If H is disconnected, then Si^H) is not
interval.
Proof: If H is disconnected, then there exist Type III vertices x,y that are joined
in H by a simple path x = vi,...,Vk = y. Without loss of generality we may
assume that d(x,y) is minimal; this ensures that this path is a connected com-
ponent of H*. Note possibly k = 2 in the case where [x,y\ is a bridge. This is
the subgraph H\ of Figure 3.8. If k > 2 then H contains the subgraph of
Figure 3.8. Consider the vertex-set incidence matrix of S(H). Since H contains
one of the subgraphs of Figure 3.8, then the matrix must contain as a subma-
trix one of the matrices of Figure 3.9. Neither could possibly be a submatrix
of a matrix with the consecutive ones property unless zeros are filled in. The
66


Figure 3.8: Induced subgraphs resulting from disconnected H.
c c c c
-'Xl JX2 -j/1 -'j/2
U
X
y
w
1 1
1 0
0 1
0 0
0
1
0
1
MiS'ilh)):
0
1
1
Figure 3.9: Effect on S of disconnected H.
assumption that the path connecting x and y is a connected component of H*
ensures that this cannot occur, i.e., these are induced submatrices. Since H is
interval the vertex-set incidence matrix of S(H) is simply the vert ex-maximal
clique indicence matrix of S2(H), and if this matrix lacks the consecutive ones
property then S2(H) cannot be interval. We conclude that if S2(H) is interval
then H is connected. |
The preceding result, while couched in the language of (0, l)-matrices, has a
simple graph-theoretic interpretation. Figure 2.1 showed that the two-step graph
67


Figure 3.10: H* isomorphic to P5, and 82(H).
S2(H1) of the graph H1 of figure 3.8 contains an induced cycle of length four. It
is straightforward to show that if x and y are Type III vertices in H that are
separated in H* by a path of length k then we find an induced cycle of length
k + 3 in 82(H). Figure 3.10 shows the case where H* is a simple path of length
five.
Corollary 3.2 If H and ) are interval, and if x,y are Type III vertices in
H then x,y lie in the same component of H.
Proof: Every Type III vertex is a vertex of H. If both H and 82(H) are interval
then, by Lemma 3.5, H is connected, and the result follows immediately. g
Lemma 3.6 If H is interval and C C H is a clique, then C contains at most
two Type III vertices.
Proof: If x,y,z are Type III vertices in a clique, then we have the induced sub-
graph G of Figure 3.11, in which x',y', z' are an asteroidal triple, a contradiction
since H is interval. |
It is not hard to see that it is quite possible for a maximal clique C in an
interval graph H to contain two nonsimplicial vertices. Indeed, this is true for
68


Figure 3.11: Cliques containing three (G) and two (H) Type III vertices.
Ci- -l Ci Ci+1 [*>y]
1 1 0 0
0 1 0 1
0 1 1 0
5a SX1 SXi 5b
a 1 1 1 0
X 1 1 0 1
b 0 1 1 1
Figure 3.12: Graphs for Lemma 3.7.
any edge interior to a path in a caterpillar. Graphs Hi and H2 in Figure 3.11
each contain maximal cliques containing two Type III vertices. We will show,
however, that there are severe limitations on H* in such graphs. Before doing so,
there is more to be said about the location and number of Type III vertices in
H. First to be considered is their number.
Lemma 3.7 Let H be an interval graph with interval competition graph S2(H).
Let x be a Type III vertex in H, and let Gi,..., Cy. be a consecutive ordering of
the maximal cliques of H. Then either x (E C\ or x E C*.
69


Proof: Suppose by way of contradiction that x $ Ci and x Ck Then
x £ Ci, 1 < i < k.
Case 1: x is simplicial in H. Since x is Type III, there exists y £ V{H) such that
the edge [x,y\ is a maximal clique in H. No consecutive ordering of maximal
cliques of H is possible, so H cannot be interval, a contradiction. See graph Hi
in Figure 3.12. Hi has the configuration described, and M(Hi) shows the effect
of this configuration on the ordering of maximal cliques, i.e., that the cliques
containing a, x and b cannot be consecutively ordered.
Case 2: x is nonsimplicial in H. This forces k > 4, since otherwise either x £
Ci C\C2 or x £ C2f]C3.So it must be that x £ Cif]Cj for 1 < i,j < k, as shown
in graph H2 of Figure 3.12. Let a £ Ci_i C\Ci, and let b £ Cjf] Cj+1- Both a
and b exist, since H is connected. Since x is Type III, there exists y £ V(H)
such that [x,y] is a maximal clique in H. If y has a neighbor z ^ x £ H*, then
the maximal cliques of H cannot be consecutively ordered, a contradiction. If
Cif]Cj contains another vertex z / x, then once again the maximal cliques of H
cannot be consecutively ordered. So we may assume that y, the neighbor of x in
H*, is a pendant vertex and that Ct D Cj = x. But now a consecutive ordering
of S(H) is impossible, contradicting our assumption that S2(H) is interval. For
an illustration of this, see graph H2 and the matrix M(S(H2)) in figure 3.12. |
The next result will help to identify the limitations on the number of maximal
cliques in H whenever two Type III vertices lie in the same maximal clique.
70


y'
X
H :
'x^y
a
8X 2 Syi Sy2 5.
z M(S'(H)): a 1 1 1 0
b 0 1 1 1
b X 0 1 1 0
y 1 1 0 1
Figure 3.13: Illustration for proof of Lemma 3.8.
Lemma 3.8 Let H be an interval graph with 82(H) interval. If x and y are
Type III vertices lying in the same maximal clique of H, then no other vertex of
H is nonsimplicial in H.
Proof: We distinguish three cases. In each, we assume by way of contradiction
that H contains a nonsimplicial vertex other than x or y.
Case 1: Both x and y are simplicial in H, as in the graph Hi of Figure 3.11. Then
if is a clique, since otherwise no consecutive ordering of the maximal cliques of
H is possible, a contradiction since H is interval. But if H is a clique then an
additional nonsimplicial vertex must be Type III, a contradiction to Lemma 3.6.
Case 2: Both x and y are nonsimplicial in H. Then we have the induced subgraph
H2 of Figure 3.11, in which the maximal cliques are [x,x'], Ct D {a, x,y}, Cj D
{b,x,y}, and [y,y'}. Suppose H contains an additional nonsimplicial vertex. Such
a vertex must lie in Ci or in Cj. To see this, suppose that there exists a maximal
clique C7i_a or Cj+1 in H. Then there must be a nonsimplicial vertex in Ci-1 fl Ci
or in CjC\Cj+i. Since each of Ci and Cj contains two Type III vertices, such a
vertex must be Type I, by Lemma 3.6. Without loss of generality assume that b
71


is a Type I vertex. Then H possesses an additional maximal clique containing b
yet lacking some vertex of Cj, and no consecutive ordering of the maximal cliques
of if is possible, a contradiction.
Case 3: Exactly one of x,y is nonsimplicial in H. Without loss of generality
assume that x E Ci, y E C\ f| C2. Let a E Ci\C2 and b E C^VCi, as shown in
Figure 3.13. Consider S'(H). SXl C Syi, so SXI $ S'(H). The sets SI2, SV1,
and Sya admit a consecutive ordering, but suppose z E C2 is nonsimplicial, either
Type I or Type III. Then b, y E Sz or b, y E SZl, respectively, and no consecutive
ordering of S'(H) is possible, a contradiction. Figure 3.13 illustrates the case
where z is Type III, and shows the effect on 5'(if). |
The preceding lemmas now make it possible to prove the following, rather
startling result.
Theorem 3.4 Let if and S2{H) be interval graphs. Then if contains at most
two Type III vertices.
Proof: If if is a tree, then H contains no Type III vertices. Similarly, if H is
bridgeless then H contains no Type III vertices. If H is neither bridgeless nor a
tree, then by Lemma 3.5 H is connected. If if is a clique then, by Lemma 3.6
it contains at most two Type III vertices. If H is not a clique then suppose
if contains three Type III vertices x,y, and z. Let C\,..., Ck be the maximal
cliques of H. By Lemma 3.7, one of Ci, Ck must contain at least two of x,y, and
z. Without loss of generality, suppose that x,y E C\. Then, by Lemma 3.8, if
72


cannot contain an additional nonsimplicial vertex of any type, a contradiction to
our assumption about H.
H contains at most two Type III vertices. |
Restrictions on Bridge-Induced Subgraphs
If H is connected, and if H and S2(H) are interval graphs, then we have
already seen that there are limitations on the location and number of Type III
vertices. Given such H and S2(H), we now investigate limitations on H*, the
bridge-induced subgraph of H. It is clear from Theorem 3.4 that H* has at most
two components. Each is a tree, by definition of H*. Since an interval tree is
a caterpillar, each must be a caterpillar if there is to be any chance for both H
and S2{H) to be interval. In fact, the limitations are far more strict. There are
several cases to consider, and it is easiest to separate these into two groups. The
results are complete for the case of diamond-free graphs, i.e., those that contain
no induced subgraph isomorphic to the graph H of Figure 3.2.
We first consider the case where H* is connected, i.e., the case in which H
contains a single Type III vertex. As a convenenience, we adopt the following
notation and definitions. If x is a Type III vertex in H, then the component
of H* containing x is denoted H*. The height, ht(H*), of H* is defined to be
max{d(x,y)\y e H*}.
73


----
y a
SV3 Sd Sb
V 0 1 0 1
M(S'(Hi)):c 1 1 0 0
e 0 1 1 0
Sv2 Sv 1 5c 5d 5a
V 0 1 1 0 1
M(S'(H2)):. 1 1 0 0 0
9 0 0 1 1 0
Figure 3.14: Graphs and covers for proof of Theorem 3.5.
Theorem 3.5 Suppose that H is diamond-free and that H and S2(H) are both
interval. Let Ci,... ,Ck be the maximal cliques of H. If v is the unique Type III
vertex in H, then either ht(H*) = 1 or exactly one of the following holds:
(i) v is simplicial in H, and k <2.
(ii) v is nonsimplicial in H, and k < 3.
Proof: Suppose by way of contradiction that 3 y £ V(H*) such that dn> (v, y) = 2.
i) Suppose that v is simplicial in H and that k > 3. Since H is diamond-
free, and using Corollary 3.2 and Lemma 3.7, we may find the induced subgraph
Hi of Figure 3.14. Hi is interval, but consider S'(Hi). In particular, consider
SV2, Sd, Sf, and Sb- Sd must be adjacent to SV2, Sf, and Sb in a consecutive
ordering of S'(Hi). This is clearly impossible, contradicting the assumption that
52(-£f) is interval.
74


ii) Suppose that v is nonsimplicial in H and that k > 4. Since H is diamond-
free, we may find the induced subgraph H2 of Figure 3.14. As before, H2 is
interval, but consider S'(H2) as illustrated by the matrix M(S'(H2)) in Fig-
ure 3.14. Vertex i forces SV2, SVI to be adjacent; vertex v forces SVI, Sc, and
Sa to be adjacent; vertex g forces Sc and Sd to be adjacent. Thus we have SVl
adjacent to both SV2 and Sc, Sc adjacent to both SVl and Sd, and Sa adjacent to
either SVl or Sc, but this is impossible, contradicting the assumption that S2(H)
is interval. |
It is straightforward to verify that, in both cases (i) and (ii), the subgraphs
obtained by deleting either vertex y or both vertices u and w have interval two-
step graphs.
The natural direction in which to go from here is to consider those diamond-
free interval graphs H that have disconnected H*. These, as observed above,
have at two Type III vertices.
Theorem 3.6 Suppose that H is diamond-free and interval, that H is connected,
and that u and v are Type III vertices in H. If ht(H^) = ht(H*) = 1, then S2(H)
is interval.
Proof: By Theorem 3.1, it suffices to show that S'(H) has a consecutive ordering.
By Theorem 2.7, S'(H) has a consecutive ordering Si,..., Sk, where k > 1. Under
the given assumptions, S'(H) = S'(H) U{ } If C'i, ..., Cm is a consecutive
ordering of the maximal cliques of H, then Cy E 75


By Lemmas 3.7 and 3.8, we may assume without loss of generality that u £ C\
and v £ Cm, so u £ Si and v £ Sk- Moreover, all of the vertices of Ci, except u,
lie in SU2, and the remaining vertices of H* appear only in SU2, so SU2, Si,... ,Sk
is still a consecutive ordering. By a symmetric argument, SU2, Si,..., Sk, SV2 is a
consecutive ordering, and the result follows. |
We must now consider those cases in which the height of at least one com-
ponent of H* exceeds one. Theorem 3.5 makes the work a bit easier, by placing
restrictions on the number of maximal cliques in H.
Theorem 3.7 Suppose that H is diamond-free and interval, that H is connected,
and that u and v are Type III vertices in H. Suppose that at least one of
ht(H*), ht(H*) exceeds one. If S2(H) is interval, then either (a) one of H*,H*
has height equal to one, or (b) both if* and H* have height equal to two. In either
case, exactly one of the following is true:
(i) Both u and v are nonsimplicial in H, and H contains exactly three max-
imal cliques.
(ii) Exactly one of u,v is nonsimplicial in H, and H contains exactly two
maximal cliques.
(Hi) Both u and v are simplicial in H, and H is a clique.
Proof: Suppose that u and v are Type III vertices in H. From Theorem 3.6, we
know that if ht(H*) = ht(H*) = 1 then ^(Tf) is interval. We shall suppose,
76


Figure 3.15: Diamond-free graphs for proof of Theorem 3.7, part 1.
then, that at least one of ht(H*), ht(H*) is greater than 1, and show that either
(a) or (b) must hold. We have three cases to consider.
First suppose that both u and v are nonsimplicial in H. By Theorem 3.5,
H has at most three maximal cliques. Under the additional restriction that H
is diamond-free, H must have exactly three maximal cliques. Now suppose that
both H* and H* have height two. Then we may find the induced subgraph Hi
of Figure 3.15. Hi is clearly interval, so we must ensure that S2{Hi) is also. By
Theorem 3.1, it suffices to examine S'(Hi). The sets in S'(Hi) are Sb = {a,u},
$u2 = {b,c,d,e,v}, SUy = {u,c,d,e,v}, Svl = {u,e,f,g,v}, SV2 = {u,e,f,g,h},
and Sh = {i, u}. If Sh and Sb are interchanged in this sequence, the ordering is
consecutive and so is interval. Suppose, then, that an additional vertex
is placed such that one of H*, H* has height greater than two. Without loss
of generality assume that vertex j and edge [i,j] are added. We now have the
induced subgraph H2 of Figure 3.15. The graph is still interval, but notice the
change that is induced in the competition cover. We gain a set Si = {j, h}. For a
consecutive ordering to exist, Si must be adjacent to SV2, since both sets contain
h, but this is impossible. Sb is in the way, and we conclude that S2{H2) is not
77


Cm d
Figure 3.16: Diamond-free graphs for proof of Theorem 3.7, part 2.
interval. If Sb were not present, there would be no problem. Moreover, we could
then increase the height of H* by any amount. See, for example, the graph H3 of
Figure 3.15. In H3, we have ht(H*) = 1 and ht(H*) = 3. S'(H3) = S'(H2)\Sb,
which is consecutively ordered. If we now add a pendant edge [j, A:], we gain a set
Sj = {*, k}. This set can precede Sh in the ordering of S'(H3). Adding another
pendant edge [k, Z] induces a set Sk = {j, 1} that can become the successor to 5,-
in the ordering of S'(H3). This process can be continued indefinitely, with the
newly created sets taking position at alternate ends of the ordering of S'(H3),
and the consecutive ordering is maintained. We conclude that, if u and v are
Type III vertices that are nonsimplicial in H, then H consists of exactly three
maximal cliques and that either one of H*, H* has height one or both have height
two.
Now suppose that exactly one of u, v is nonsimplicial in H. By Theorem 3.5,
H has at most two maximal cliques. Since one of u, v, without loss of generality
78


say v, is nonsimplicial in H, it must be the case that H has exactly two maximal
cliques. The remainder of the proof of this case duplicates the construction used
in the case above, although symmetry has been lost. It must be shown that either
H* or H* can have height greater than three provided the other has height one.
First consider the graph Hi of Figure 3.16. In Hi, both subtrees of H* have
height two. The graph is clearly interval. The sets in S'(Hi) are Sj ~
SU2 = {b,c,v}, SV1 = {c,d,e,u,v}, SV2 = {c,d,e,u,f}, and Sb {a,u}. This
ordering is consecutive, so, by Theorem 3.1, S2(Hi) is interval. Increasing the
height of H* to three enables us to find the induced subgraph H2 of Figure 3.16.
S'(H2) = S'(Hi) U Sg, where Sg = {/, h}, and no consecutive ordering is possible.
If, however, the height of H* is now reduced to one, we obtain the induced
subgraph H3 of Figure 3.16. S'(H3) = S'(H2)\Sb, and the consecutive ordering
is restored. This ordering is now Sf, SU2, Sy1, SV2, Sg.
Now consider what happens to the competition cover if the height of H* is
increased to three while the height of H* is held at two. We have the induced
subgraph HA of Figure 3.16. S^H^) = S'(Hi)(j Sa, where Sa = {^, &} No
consecutive ordering of S'(Hi) is possible. Reducing the height of H* to one, we
obtain the induced subgraph H5 of Figure 3.16. S'(H5) = S'(H4)\Sf, and the
consecutive ordering is restored as Sa, SU2, SVl, SV2 ,Sb. As in the case where both
Type III vertices were nonsimplicial in H, we may extend the height of either
component of H* arbitrarily, provided the height of the other is held at one.
79


Figure 3.17: Diamond-free graphs for proof of Theorem 3.7, part 3.
Finally consider the case where both u and v are simplicial in H. By Theo-
rem 3.6, this restricts H to at most two maximal cliques. It must first be shown
that H cannot have two such cliques if the height of either H* or H* exceeds one.
Suppose, then, that H contains two maximal cliques and that, say, ht(H*) = 2.
We have the induced subgraph Hi of Figure 3.17. Hi is interval, but S'{Hi)
consists of Sb = { No consecutive ordering is possible, so S2{Hi) is not interval. We conclude that,
if either H* or H* has height greater than one, H must be a clique.
We now follow the construction used in the preceding cases. First suppose
that ht{H*) = ht{H*) = 2. We have the induced subgraph f?2 of Figure 3.17.
The sets comprising S'(H2) are Sd = {u,e}, SU2 {6, c, u}, SUI = SV1 = {c,u,u},
SV2 {c,u,d}, and Sb = {o, u}, and this ordering is consecutive. Without loss
of generality suppose that edge [e,/] is added, increasing the height of H* to
three and inducing the subgraph H3 of Figure 3.17. S'(H3) = S'(H2) (J $e, where
Se = {d, /}. No consecutive ordering is possible, so S2(H3) is not interval. If,
however, the height of H* is reduced to one, we may delete the set Sb from
S'(H3), and the consecutive ordering is restored by letting Se take its place. As
80


before, the height of H* may now be increased arbitrarily without affecting the
consecutive ordering. We conclude that, if u and v are Type III vertices in H
both are simplicial in H, then H is a clique and either one of H*, H* has height
one or both have height two.
This completes the proof of Theorem 3.7. |
Examples can be constructed to show that the restrictions on diamond-free
interval graphs do not necessarily apply to interval graphs in general. The preced-
ing three theorems quite clearly depend upon the diamond-free character of the
graphs in question. It is not yet clear what results will arise when this restriction
is relaxed.
81


CHAPTER 4
TWO-STEP GRAPHS OF TREES
In this chapter, the relationship between a tree and its two-step graph is
explored without concern for whether the tree in question is interval. In keeping
with the spirit of this thesis, we begin by considering those trees whose two-
step graphs are interval and present a forbidden subgraph characterization for
such graphs. This is a first step toward characterizing chordal graphs that have
interval two-step graphs. Following this, we drop the condition that the two-step
graph is interval, and investigate the possibility of reconstructing a tree from its
two-step graph.
Trees with Interval Two-Step Graphs
Theorem 2.8 shows that, if T is a tree, then a sufficient condition for ^(T)
Figure 4.1: Noninterval tree T with interval )


to be interval is that T be interval. This condition is fax from necessary. It is
easy to construct infinite families of noninterval trees with interval competition
graphs. See, for example, the tree T of Figure 4.1. T can be viewed as four
copies of Kii3 with a common vertex, labeled v. We may generalize T by taking
m copies of K\>n and choosing one pendant vertex from each copy, labeling this
vertex v. By identifying these labeled vertices, we obtain a tree with a high
degree of symmetry about the central vertex. The tree T of Figure 4.1 is the
case m 4, n = 3. The competition graph S2(T) for such a graph consists of
a windmill containing m copies of Kn with one vertex common to all, and a
single copy of Km. Both components are clearly interval. In order to understand
the conditions under which a tree has an interval competition graph, we must
establish some preliminary results aimed at relating neighborhoods in T to cliques
in S2(T).
Recall that a diamond is a graph consisting of two triangles with two vertices
common to both. The graph H of Figure 4.2 is a diamond. A diamond-free graph
has the property that for any two maximal cliques C, and Cj, |C, fl Cj\ < 1.
Lemma 4.1 IfT is a tree, then S2(T) is diamond-free.
Proof: Suppose not. Then we may find the graph H of Figure 4.2 as an induced
subgraph of S2(T). Since T is a tree, the preimage of H under S2 must be
acyclic. Consider the triangle, o, b, c>, in S2(T). T must contain vertices Xi,x2,
and s3, such that (o, x1} b), (b, x2) c), and (c, x3, a) are paths of length two. If these
83


Figure 4.2: H C S2(T), and acylic preimage.
vertices are distinct, then T contains the cycle a,x1,b,x2,c,x3,a. If two of these
vertices are distinct, say, x^ = x2 ^ x3, then T contains the cycle a, x1}c, x3,a.
In either case, we have a contradiction to the hypothesis that T is a tree. Thus
the only acyclic preimage of a triangle is Ki<3, so the two triangles and
in H have 2Ki>3 as preimage under S2, each copy of K^3 containing b
and c as pendant vertices. Since [a, d] g E(H), v ^ w, so = Z4 in T,
a contradiction, since T is a tree. |
The following result is an analog to one that holds in the case of the square
of any graph, but that unfortunately fails to hold for two-step graphs in general.
Lemma 4.2 If H is a connected subgraph of a tree T then S2(H) is an induced
subgraph of S2(T).
Proof: Let x,y £ V(fl). It is clear that if [s,y] G E(S2{H)) then [x,y] G
E{S2{T)). Now suppose that [x,y] £ E(S2(H)). Then there exists no v G V(H)
such that [x,v], [y,v] G E(H). Suppose that T\H contains a vertex v such that
[x,v\,\y,v] G E(T). Then there would be, in addition to the path from x to y
in H, a path from x to y using v, but this is impossible since T is a tree. Thus
84


{x,y] ( E(Si(T)).
I
We have already seen that it is not reasonable to expect the two-step graph of
a tree to be, itself, acyclic. Nevertheless, we can show that it contains no cycles
Zk for k > 3.
Lemma 4.3 Suppose T is a tree. Then S2(T) is chordal.
Proof: Suppose not. Let , k > 4, be a cycle in S2(T). Then for any
i 7^ j, i,j G {1,..., k}, there are two distinct (u;, i^-paths Px = u;, Vi+x,.. ., Vj
and P2 = Vj,Vj+i,...,u, in S2(T). But then there are two distinct u,, u^-paths in
T. One of these has the form x^, t\+x, Xi+X,... ,Xj_x,Uj, where the appropriate
edges exist, containing all of the vertices of Px. In similar fashion, the other
contains all of the vertices of P2. Since Px and P2 are distinct, then their preimages
in T are also distinct. But this is a contradiction, since T is a tree. |
Lemmas 4.1, 4.2 and 4.3 will be applicable to two distinct problems. They will
prove useful in the problem of reconstruction of a tree, given a candidate two-
step graph. For the moment, we are prepared to give necessary and sufficient
conditions for the two-step graph of a tree T to be interval. These conditions
concern a single forbidden subgraph.
Forbidden Subgraph Characterization
Theorem 4.1 Let T be a tree. Then S2(T) is interval if and only ifT does not
contain an induced H, where H is the graph of Figure 4-S-
85


H:
S2(H):
Figure 4.3: Forbidden subgraph for tree with interval two-step graph.
Proof: Suppose that S2(T) is interval, and suppose by way of contradiction that
H C T. S2(H), shown in Figure 4.3, is not interval. By Lemma 4.2, S2(H) is an
induced subgraph of S2(T), so S2(T) is not interval, a contradiction.
To prove the converse, assume that S2(T) is not interval. By the characteri-
zation due to Lekkerkerker and Boland [56], if S2(T) is not interval then it must
contain either a cycle Zk, k > 4, or an asteroidal triple. By Lemma 4.3, S2(T) is
chordal, so it contains no Zk for k > 4. The minimal chordal graphs containing
asteroidal triples are Hi, H2, Hz,n, and Hi>n, where these graphs are illustrated in
Figure 4.4. By Lemma 4.1, since T is a tree then S2(T) cannot contain Hz,n for
n > 2, nor can it contain H2 or H4,n. So if S2(T) is not interval then it contains
Hi or Hz,2- We show that, in either case, H C T.
(i) Suppose that Hi C S2(T), and label Hi as shown in Figure 4.5, where Hi
is a component of S2(Ti). Since [a, 6] G E(S2(T)) there exists x such that
[a, x], [x,b] G E(T). Similarly there exists y such that [b, y], [y,c] G E{T). Since
[a, c] 0 E(S2(T)) then x ^ y. Continuing in this fashion we obtain the unique
minimal preimage 7\, as shown in Figure 4.5. Thus H C Ti C T. (Note that
S2(Ti) = Hi U Hz,2, also shown in Figure 4.5.)
86


n + 4 vertices,
n> 4
n + 5 vertices,
n > 1
Jfe >4
Figure 4.4: Forbidden subgraphs for interval graphs.
Figure 4.5: Graphs for proof of Theorem 4.1.
87


1: T r2: S2(T1) = S1(T2y. jA
jk 1 , W-V
abed,
age
T~r*d
a c e
Figure 4.6: Nonisomorphic trees with same competition graph.
S2(K1>6):
Ke\JKi
S2(K6[]K1
Figure 4.7: K 1>6 and , 6).
(ii) It is easy to show that the unique minimal preimage under S2 of H32 is
T2 = Ti\{a, e, <7}. The triangle must be the image of a Ki>3 in T, since
T is a tree. The edges [y, x], [z, w] and [s,t] are the images of pendant paths of
length two at y, z, and s, respectively. We thus obtain the minimal preimage
T2 = H. We have shown that if T is a tree and if S2(T) is not interval then
HCT. |
The Reconstruction Problem
It is tempting to think that the acyclic preimage T of a given S2(T) is unique,
up to isomorphism. This is, unfortunately, not the case. For example, given Ti
and T2 of Figure 4.6, = S2(T2). It is also not the case that if T is a tree then
S2(T) is uniquely the two-step graph of a tree. Consider S2{Kln) = Kn{JK\ =
88


S2(Kn U Ki). The case n = 6 is shown in Figure 4.7. It will nevertheless be
shown that, given one component of S2(T), one may reconstruct a connected
subgraph of T. In fact, given both components of S2(T), one may reconstruct
two connected subgraphs of T. The problem of reconstructing T from S2(T) then
lies in determining which vertices of the two components must be identified. This
is a bit like assembling a jigsaw puzzle, but is made more difficult by the absence
of uniqueness. As observed, it might be possible to construct more than one tree
from the two connected subgraphs.
Before looking further into the problem of reconstruction, we prove the fol-
lowing lemma which relates the maximal cliques of S2{T) to the neighborhoods
in T.
Lemma 4.4 Let T be a tree, and suppose that S2(T) contains no isolated vertices.
Then the maximal cliques in S2(T) are in one-to-one correspondence with the
neighborhoods of interior vertices inT.
Proof: Suppose that x is an interior vertex in T. N(x) induces a clique C in S2(T),
by definition of S2. Suppose that C is not maximal. Then there exists v $ N(x)
such that v is joined to every vertex in N(x) by a path of length two, but this
creates a cycle in T, a contradiction. Now suppose that Xi ^ Xj, and that x^Xj
are interior vertices in T. Let Ci and Cj be the cliques in S2(T) corresponding,
respectively, to N(xi) and N(xj). Suppose Ci = Cj. Since S2(T) contains no
isolated vertex, |(7;| = \Cj\ > 2. But then there exist u,v £ N(xi) N(xj), so
89


< Xi,u,Xj,v > contains a cycle in T, a contradiction. We have shown that S2
maps the neighborhoods of interior vertices of T into maximal cliques of S2(T),
and this mapping is one-to-one. We must show that it is onto.
Suppose that C =< v1}..., v*. > is a maximal clique in S2(T). By definition
of S2(T), there is a path of length two in T connecting v, and Vj for each choice
of i ^ j, i,j {1,..., k}. Moreover, all such paths must use the same internal
vertex. Suppose, for example, that V{,Vj, and Vk are vertices in C and that
< Vi, x, Vj >, < Vj, y, Vk >, and < Vk, z, Vi > are paths of length two in T. Suppose
that x y£ y and that either z = x or z = y, say z y. Then < Vi,x,Vj,y >
contains a cycle. So 2 ^ s and z ^ y, but then < Vi,x,Vj,y,Vk, z > contains a
cycle. In either case we have a contradiction, since T is a tree, so x y. By
a symmetric argument, x z, so N(x) = N(y) = N(z) = {ui,..., Vk}. It is
obvious that x = y = z is not an end-vertex, since then C would consist of an
isolated vertex, so C must correspond to the neighborhood of an interior vertex
ofT. |
The preceding lemma begs the question of exactly what happens when ^(T)
contains an isolated vertex. The following lemma answers this question.
Lemma 4.5 Suppose that ^(T) contains an isolated vertex. Then T is either
the trivial graph or a star K\ Proof: If S^T) consists of a single vertex, then T must also. If both components
of S2{T) are isolated vertices, then T is an edge, i.e., K\t\. Suppose, then, that
90