NICHE GRAPHS AND NICHE NUMBERS:
NEW RESULTS AND ALTERNATIVE DEFINITIONS
by
Charles A. Anderson
B.A., University of Colorado at Boulder, 1969
M.S., University of Colorado at Denver, 1986
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1992
I 5 I
j ^'.i
Hi
1992 by Charles A. Anderson
All rights reserved.
This thesis for the Doctor of Philosophy
degree by
Charles A. Anderson
has been approved for the
Department of
Mathematics
by
William J. ''Wolfe
z
Anderson, Charles A. (Ph.D., Applied Mathematics)
Niche Graphs and Niche Numbers: New Results and
Alternative Definitions
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
The niche graph of a digraph has the same vertex
set as the digraph and an edge between two vertices if
and only if, in the digraph, those two vertices both
have arcs to or from a common third vertex. A graph
that is the niche graph of an acyclic digraph is
called a niche graph; the niche number of a graph is
the minimum number of isolated vertices whose disjoint
union with the graph is a niche graph.
Several classes of graphs have been identified as
niche graphs; this thesis identifies several more,
all of which are types of unit interval graphs. As a
consequence of the methods of a proof in this thesis,
a new count of the number of labeled unit interval
graphs on n vertices is obtained.
The niche number of many classes of graphs is
infinite; building upon a suggestion by Suzanne
Seager, we look at several alternative definitions of
the niche number. Each of these makes the niche
IV
number of every graph finite by relaxing the
requirement that additional vertices be isolated. The
niche numbers provided by these definitions are
investigated; for graphs with finite original niche
number there are few changes. The major results of
this thesis provide bounds for these new niche numbers
in terms of the clique cover number of a graph and
develop tighter (and in some cases exact) bounds for
the complete bipartite graphs.
The final section of the thesis, suggested by
similar results in competition graph theory, is an
investigation of how relaxing the acyclic requirement
for the digraph expands the class of niche graphs. We
show that the graphs with arbitrarily large finite
(original) niche numbers, discovered by Fishburn and
Gehrlein, become niche graphs if cyclic digraphs are
allowed, and that unit interval graphs are niche
graphs of digraphs with loops allowed. We provide
several other partial results.
This abstract accurately represents the content of the
candidate's thesis. I reqÂ£
Signed_ _
CT. Richard Lundgrfen
v
DEDICATION
To my wife and best friend, Pat Carney,
whose love, understanding, and encouragement
made it possible to complete this thesis.
ACKNOWLEDGEMENT S
I am grateful to many people and organizations
that helped me during the years of graduate school.
Rich Lundgren first introduced me to graph theory (and
to niche graphs in particular) and gave me a chance to
coauthor several papers. His positive outlook while
this thesis gradually took shape is much appreciated.
Kathy Fraughnaugh offered valuable assistance on niche
graphs, and also, with Jenny Ryan, helped me learn
about tabu search and genetic algorithms. Jenny Ryan
and Harvey Greenberg guided me through the elements of
mathematical programming. Bill Wolfe showed me many
aspects of artificial intelligence and computer sci
ence, and our discussions led to two papers on neural
networks in which I was a minor coauthor. My thanks
also go to my other professors at the University of
Colorado at Denver, and to the university itself, for
making it possible for fulltime workers to pursue
further studies. Not all institutions are as flexi
ble.
I received, and gratefully acknowledge, financial
support from many sources. Jefferson County Public
Schools awarded me two sabbaticals at half salary,
vii
allowing me to complete much of my coursework. The
Colorado Commission on Higher Education helped to
defray tuition several semesters. The Colorado Insti
tute for Artificial Intelligence (now the Colorado Ad
vanced Software Institute) and US WEST provided a re
search assistantship. The National Science Foundation
and the Rocky Mountain Mathematics Consortium funded
several summer institutes at the University of Wyo
ming. The Mathematics Department of UCD and the
Office of Naval Research helped with travel costs to
several conferences. I thank these institutions and
any others I may inadvertently not have mentioned.
viii
CONTENTS
1. Introduction....................................1
1.1 Overview of Thesis Results.................4
2. Definitions and Literature Review................8
2.1 Basic Definitions......................,...8
2.2 Competition Graphs........................13
2.3 Niche Graphs and Niche Numbers............18
3. Niche Graphs and Unit Interval Graphs ..........25
3.1 Types of Unit Interval Graphs That
Are Niche Graphs........................ 27
3.2 Are All Incomplete Unit Interval
Graphs Niche Graphs?......................35
3.3 The Number of Possible Clique Structures
for Labeled Unit Interval Graphs..........44
4. Alternative Definitions for the Niche
Number and Some of Their Consequences ..........50
4.1 Alternatives for the Niche Number
Definition................................52
4.2 Basic Properties of New Niche Numbers ...58
4.3 Summary...................................64
5. Alternative Niche Numbers for Complete
Bipartite Graphs................................65
5.1 The Niche Numbers of Complete Bipartite
Graphs with Both Bipartitions Having
More Than Two Vertices........................ 75
6. Loop Niche Numbers and Cyclic Niche Numbers ...83
7. Bibliography...................................99
IX
1.
Introduction
The primary topic of this paper is the investi
gation of niche numbers of graphs. This first section
of the thesis is intended as an overview of the major
concepts and results contained in the rest of the the
sis. Some knowledge of graph theory will be assumed.
Precise statements of definitions and theorems and
relevant background material will be found in chapter
two.
Niche graphs (and competition graphs) have roots
in ecology, where the study of ecosystems led to the
construction of acyclic digraphs depicting predator
prey relationships among various species. If species
are represented by vertices, an arc from one vertex to
a second vertex indicates that the species represented
by the first vertex preys on the species represented
by the second. Such a digraph is called a food web.
One vertex is said to prey on another (and is called
a predator) if there is an arc from the first to the
second; the second vertex in such a situation is
called a prey. Note that a vertex may be both preda
tor and prey.
1
Every digraph has a competition graph and a niche
graph associated with it; they use the same vertex
set as the digraph. In the competition graph of a
digraph, two vertices are connected by an edge if and
only if those vertices both prey on a common third
vertex. In the niche graph of the digraph, two verti
ces are connected by an edge if either they ha.ve a
common prey, as in the competition graph, or they have
a common predator. While the topic of this thesis is
niche graphs, it will help to first discuss some of
the known facts concerning competition graphs. Many
of the results and open problems about niche graphs
are analogous to, and were first investigated because
of, properties of competition graphs.
Since the food webs which led to the concept of
competition graphs are almost all acyclic, we will
call a graph a competition graph only if it is the
competition graph of an acyclic digraph. An obvious
question to ask is: which graphs are competition
graphs? It is easily shown that, while no connected
graph is a competition graph, every graph is a
component (or set of components) of a competition
graph, all of whose other components are isolated
vertices (i.e., they have no edges connecting them to
any other vertex). In other words, every graph can be
2
made into the competition graph of an acyclic digraph
by adding enough extra isolated vertices.
A natural followup question is, how many extra
isolated vertices must be added to make an arbitrary
graph into a competition graph? For any graph, we
will call this minimum number of isolated vertices its
competition number. Thus, a graph which is already a
competition graph has competition number zero; a graph
(such as, we will see, a complete graph on two or more
vertices) which requires only one additional isolated
vertex to become a competition graph has competition
number one, and so on.
Thus competition graphs are always disconnected,
and the question of how close (in some sense) any
graph is to being a competition graph can be quanti
fied by its competition number. These characteristics
of competition graphs and competition numbers made
them a popular subject of research in the nineteen
seventies and nineteeneighties. Even though the
problem of determining the competition number of a
graph was shown to be NPcomplete in 1982 [28], the
competition numbers of many different classes of
graphs were established. Applications in areas other
than ecology, such as assignment of radio frequencies
in areas crowded with many transmitters, were found.
3
Niche graphs, when first investigated, proved not
to have the same appealing characteristics that compe
tition graphs possessed. Those graphs which are niche
graphs of acyclic digraphs do not have an easily iden
tifiable characteristic such as always possessing an
isolated vertex. The niche number of a graph can be
defined similarly to the competition number, but the
definition raises some problems. Some relatively
simple graphs (such as stars with three or more rays)
cannot be turned into niche graphs by adding isolated
vertices; they are said to have infinite niche
number. Finding niche numbers for classes of graphs
seems to be more difficult than finding competition
numbers; not many are currently known. An additional
difficulty is that, until 1990, the only niche numbers
known to exist were zero, one, two, and infinity.
1.1 Overview of Thesis Results
This thesis will present some new results about
niche numbers of graphs. The second chapter will
provide some basic definitions from graph theory and
review the existing literature regarding competition
graphs, competition numbers, niche graphs, and niche
numbers. This background will emphasize the relation
ship between the theories of competition graphs and
4
niche graphs. In the third chapter, research results
involving unit interval graphs will be presented.
While we have not proved that all unit interval graphs
are niche graphs, many subclasses of unit interval
graphs are shown to be niche graphs. At the end of
the chapter, a method of counting the number of unit
interval graphs which are labeled to make all their
maximal cliques consist of consecutive vertices is
introduced. Surprisingly, the number of such labeled
graphs turns out to be related to the Catalan numbers,
a sequence which turns up in many unexpected places in
combinatorics.
The fourth chapter will discuss alternative defi
nitions for the niche number of a graph and some of
the ramifications of adopting one of these alternative
definitions. One reason for looking at different
definitions is that niche numbers lack the diversity
of competition numbers. All graphs have finite com
petition numbers; many graphs have an infinite niche
number. Graphs with competition numbers of any de
sired size are easily found; the overwhelming majori
ty of graphs so far investigated have niche numbers of
zero, one, or infinity. By looking at other defini
tions, perhaps a more useful niche number, one which
differentiates among more classes of graphs, may be
5
found. An important property of the new definitions
for niche numbers is that they do not conflict with
the wellestablished definition of competition number,
that is, if the competition number were defined analo
gously to the niche number, every graph would still
have the same competition number. The new niche
number definitions simply allow the extra vertices
added to the graph to be connected in different ways,
instead of isolated.
Chapter five concentrates on the new niche num
bers of complete bipartite graphs. This class of
graphs has original niche number infinity; the small
est graph with infinite niche number is a member. Se
veral results show that the alternative niche numbers
of these graphs take on all positive integer values.
For some graphs, we find the exact niche numbers; for
others, restrictive upper and lower bounds are proved.
In the final chapter, we look at another modifi
cation of the definition of niche number. The origi
nal context in which competition graphs were consid
ered was ecology; most of the food webs studied were
acyclic. In the early eighties the requirement of
acyclicity was relaxed, and it was discovered that
virtually every graph (with the exception of those
with more maximal cliques than vertices) is the compe
6
tition graph of an arbitrary digraph. We look at the:
analogous problems for niche graphs, and the answers
are more complicated. Some graphs still have infinite
niche number, while many of those with finite original
niche number, including a class whose niche numbers
grow arbitrarily large, turn out to be niche graphs of
arbitrary digraphs.
7
2. Definitions and Literature Review
2.1 Basic Definitions
A graph G = G(V, E) is a finite set of vertices
V together with a set of edges E which is a subset of
the set of twoelement subsets of V. We think of the
vertices as points in space or on a plane, and the
edges as line segments or curves connecting pairs of
those points. Vertices are generally written as
lowercase letters. If u and v are vertices of G, uv
(or vu) represents the edge connecting u and v, and u
and v are endpoints of uv. An edge and its endpoint
are incident. If G has n vertices, we will frequently
label them {vl7 v2,..., vn}, and edges will be written
in the form v^vj. Two vertices are adjacent if there
is an edge between them; two edges are adjacent if
they share a common vertex. If two edges are adja
cent, we also say that they intersect. The degree of
a vertex is the number of edges incident with it. The
degree of a graph is the maximum of the degrees of its
vertices. If a vertex is not incident to any edge
8
(and thus not adjacent to anyt vertex) it is an
isolated vertex.
Two vertices u and v are connected if there is a
sequence vlf v2,..., vn of vertices such that v^_ and
vi+i are adjacent for each 1 < i < n1, u is adjacent
to vlt and vn is adjacent to v. If the (and u and
v) are all distinct, the sequence of vertices, and
their connecting edges is a path. If we have u = v,
and i > 0, and the v^^ are all distinct, the sequence
of vertices and their connecting edges is a cycle.
The graph which consists of a path on n vertices will
be denoted by Pn; the cycle on n vertices by Cn. A
graph G is connected if all pairs of vertices in it
are connected. Otherwise G is disconnected. A
connected graph without any cycles is a tree.
A subgraph of G is a graph with all its vertices
and edges in G; an induced subgraph of G is a graph
G' (V', E') with all its vertices in G and its edges
exactly the edges of G connecting vertices in V'. A
maximal connected subgraph of G is a component of G.
A graph whose vertex set can be partitioned into
two sets such that every edge of the graph has one
endpoint in each set is a bipartite graph. In a bi
partite graph, all cycles have an even number of ver
tices and edges. A complete graph is one in which
9
every pair of vertices is joinedrby an edge. A com
plete bipartite graph is a bipartite graph in which
every vertex in one bipartition is adjacent to every
vertex in the other. The complete graph on n vertices
is denoted by Kn; the complete bipartite graph with a
bipartition into m and n vertices by *, See figure
2.1 for examples. A complete subgraph of a graph.G is
called a clique of G; we will frequently be interest
ed in the maximal cliques of a graph. A vertex which
is contained in only one maximal clique is called a
simplicial vertex. Any set of cliques {Cx, C2,..., Cm}
containing all the edges of G is called a clique cover
of G. The minimum number of cliques required to cover
the edges of G is called the edge clique cover number
of G, and is written 0e(G).
Figure 2.1 The Graphs P3, C4, K4, and K2 3
Given any family of sets, the intersection graph
of that family has a vertex corresponding to each set
and an edge between two vertices if and only if the
10
i
sets corresponding to those vertices intersect. If we
restrict the sets to intervals on the real line, we
can construct a graph from this set by assigning a
vertex to each interval and then drawing an edge be
tween two vertices if and only if their intervals
overlap. Any graph that can be so constructed is
called an interval graph. A graph that is the inter
section graph of a set of intervale of identical
length is called a unit interval graph1 This class of
graphs is quite important in the theory of competition
graphs and niche graphs. A comprehensive reference is
the book by Golumbic[13].
A directed graph, or digraph, D '= D(V, A) is a
set of vertices together with a set of arcs which are
ordered pairs of vertices. In a digraph we think of
the arcs as lines or curves with directional arrows
connecting two vertices. As with graphs, vertices
will be denoted by lowercase letters, and the arc
connecting vertex x to vertex y by xy., Note that xy
and yx are different arcs. If the context does not
make absolutely clear whether we are referring to an
I
arc or an edge, we will specify "arc xy" or "edge xy."
If xy is an arc, then x is its tail and y is its head;
xy is from x and to y. Furthermore, xy is an outarc
of x and an inarc of y.
11
I
If x arid y are two vertices in a digraph D, then
y is reachable from x if there is a sequence of ver
tices vlr v2/..., vn such that vivi+1 is an arc for all
1 < i < n1, and xvi and vny are also arcs. If all
the vertices are distinct, the sequence of vertices
(and the arcs connecting each to the next) is called
a path; if x = y but all other vertices are distinct,
the sequence (and its arcs) is called a cycle. In a
digraph, as opposed to a graph, cycles of length two
are permitted (for example, arcs xy and yx make a two
cycle) If an arc with the same head and tail, such
as xx, is permitted, it is called a loop. In general,
digraphs will be considered to be loopless unless
otherwise specified. We will say that x and y are
joined if there is a sequence of vertices vl v2,...,
vn such that either v^vi+1 or vi+1vi is an arc, as are
xvj^ or v^x. and vny or yvn. A digraph is strongly
connected if for every pair of vertices x and y, x is
reachable from y and y is reachable from x. A digraph
is weakly connected if every pair of vertices is
joined. For any digraph D, its reverse digraph is the
digraph on the same vertex set with an arc yx for each
arc xy of D. There is no special name for an acyclic
digraph.
12
For other terms in the theory of graphs and
digraphs, one of the many textbooks on graph theory
should be consulted, such as Roberts[31], Bondy and
Murty[3], or Harary, Norman, and Cartwright[18].
2.2 Competition Graphs
Niche graphs, the subject of this thesis, are a
natural extension of competition graphs. Since com
petition graphs have been the subject of mathematical
investigation for a much longer period of time than
have niche graphs, there is a correspondingly larger
body of literature concerning them. Niche graphs are
similar to competition graphs, and many of the early
results involving niche graphs have been discovered by
analogy with known results for competition graphs.
This section will define competition graphs and review
some of the important properties they possess.
Given a digraph D, the competition graph of D is
the graph with vertices the same as those of D, and an
edge between two vertices x and y if and only if there
is a third vertex z such that xz and yz are arcs in D.
Competition graphs were first studied in the con
text of food webs in an ecosystem, and that context
has had a strong influence on the vocabulary of compe
tition graphs. When representing a food web as a di
13
graph, species (or related groups of species) become
vertices, and there is an arc from one vertex to
another whenever the species of the first vertex eats
the species represented by the second. If xz is an
arc, then x is a predator and z is a prey; we say
that x preys on z. If xz and yz are both arcs, then
x and y compete for z.
Figure 2.2 A Digraph and Its Competition Graph
Since most food webs are acyclic, researchers
concentrated on those graphs which were competition,
graphs of acyclic digraphs. (Also, Dutton and Brig
ham[8] and Roberts and Steif[35] settled the question
of which graphs were competition graphs of arbitrary
digraphs; every graph with an edge clique cover of at
most n cliques is the competition graph of some
arbitrary digraph with loops, and K2 is the only
additional exception even if loops are not allowed.)
14
We will say that a graph G is a competition graph if
it is the competition' graph of an acyclic digraph.
Now the question of which graphs are competition
graphs becomes more interesting. Characterizations
were obtained by Lundgren and Maybee[27] and Dutton
and Brigham[8].
This terminology is somewhat confusing but well
established. There is a difference between a graph
being the competition graph of a digraph and a graph
being a competition graph. What it means is that if
we are considering a particular digraph D, we can talk
about its competition graph C(D), which is uniquely
determined by the definition. If, on the other hand,
we are talking about a graph G without reference to a
particular digraph, we will say G is a competition
graph only if there is some acyclic digraph which has
G as its competition graph.
Early researchers noted that almost all of the
competition graphs they studied were interval graphs.
While it is possible to construct competition graphs
which are not interval graphs, most competition graphs
arising in practice have been interval, so it is natu
ral to ask which acyclic digraphs have interval compe
tition graphs. This remains an active area of re
search!; 19, 43]; there have been recent investigations
15
of which arbitrary digraphs and symmetric digraphs
have interval competition graphs as well[29].
It is easy to see that all competition graphs are
disconnected; since the digraph from which the compe
tition graph arises is acyclic by definition, it must
contain a vertex with no outarcs. That vertex cannot
compete with any other vertex, and thus must be.iso
lated in the competition graph. However, Roberts[32]
showed that all graphs can be turned into competition
graphs by adding enough isolated vertices. The idea
of his proof is, for each edge of the graph, add an
extra vertex to the digraph. Then draw arcs from the
endpoints of each edge to the extra vertex for that
edge. Roberts then went on to define the competition
number k(G) of a graph G as the least number of ver
tices such that G together with that number of isola
ted vertices is a competition graph. From the remarks
above we can see that the competition number of a con
nected graph G is between 1 and E(G).
Opsut[28] showed that the computation of the
competition number of an arbitrary graph is an NP
complete problem. However, the competition number is
known for many classes of graphs. For example, the
competition number of any connected interval graph is
1, of any cycle on at least 4 vertices is 2, and of
16
any connected trianglefre^ graph on n vertices and e
edges is e n + 2[32].
Mathematicians have investigated several concepts
closely related to competition graphs and competition
numbers. Scott[37] looked at what she called the
competitioncommon enemy graph of a digraph, in which
there is an edge between two vertices x and y in the
graph when, in the digraph, there are two vertices z
and w such that xz and yz are arcs and wx and wy are
arcs. (w is called a common enemy of x and y.) She
also defined the double competition number of a graph
and showed it was at most one more than the competi
tion number. Preliminary investigations failed to
find any graphs with large double competition numbers,
but Jones, Lundgren, Roberts, and Seager[23] construc
ted a series of examples to show that the double com
petition number could be made as large as desired.
Isaak, Kim, McKee, McMorris, and Roberts[21] have
investigated the pcompetition number of graphs, which
arises from the idea of a pcompetition graph of a
digraph, where two vertices are connected by an edge
only if they compete for at least p different prey.
Anderson, Jones, Lundgren, and McKee[1] investigated
the concept of competition multigraphs and the multi
competition number, where each competition in the
17
digraph resulted in an edge in the multigraph, so that
multiple edges could occur. These ideas are all
discussed more comprehensively in survey articles by
Lundgren[26] and Kim[25].
2.3 Niche Graphs and Niche Numbers
The niche graph of a digraph D is a graph .with
the same vertices as D and an edge xy if and only if
there is a third vertex z such that xz and yz are arcs
in D, or zx and zy are arcs in D. If a graph is the
niche graph of an acyclic digraph, then we will call
it a niche graph. If an edge xy in the niche graph of
a digraph arises from competition between x and y
(that is, if xz and yz are arcs to some third vertex
z) we will call the edge a competition edge; if the
edge arises from a common enemy of x and y (that is,
zx and zy are arcs in the digraph from some vertex z) ,
we will call the edge a commonenemy edge. It is
possible for an edge in a niche graph to be both a
competition and a commonenemy edge.
From these definitions it is clear that each
inneighborhood of the digraph is a clique (not neces
sarily maximal) of competition edges in the niche
graph. Similarly, each outneighborhood of the di
graph is a clique of commonenemy edges. Greenberg,
18
Lundgren, and Maybee[14], in a different context, also
considered in and outneighborhoods, which they
called common predecessors and common successors.
Their work was matrixoriented and the existence of
common successors or common predecessors was important
to the inversion of a signed graph and a digraph. The
paper, last in a series of five, was directed toward
artificially intelligent modeling of largescale eco
nomic models.
Following the analogy with competition graphs,
the niche number of a graph G, n(G), is the minimum
number of isolated vertices whose disjoint union with
G forms a niche graph. A digraph which has as its
niche graph the disjoint union of G and n(G) isolated
vertices will be called a generating digraph for G.
While these definitions show clearly that niche graphs
are a variant of competition graphs, investigation
quickly reveals that their properties are quite
different.
Figure 2.3 A Digraph and Its Niche Graph
19
The paper that introduced niche graphs, by Cable,
Jones, Lundgren, and Seager[6], appeared in 1989.
They immediately established two rather surprising
facts about niche numbers: the niche number of a
connected graph could be zero, and it could be infi
nite. (An infinite niche number means that the graph
in question cannot be made into a niche graph by the
addition of any number of isolated vertices.) Neither
of these situations can occur with competition num
bers. Cable, Jones, Lundgren, and Seager found finite
niche numbers for several classes of graphs, and also
succeeded in showing that a nova, a graph obtained by
replacing the edges of a star (% with various
cliques on two or more vertices, has infinite niche
number. Sakai[36] proved that the complete bipartite
graph with min{m,n} > 3, has infinite niche
number as well. Bowser and Cable[4] added wheels (one
central vertex adjacent to each vertex of a cycle)
with at least nine vertices to the list of graphs with
infinite niche number; the niche number of wheels
with five through eight vertices they showed to be
zero. Since these are, with a few exceptions, the
only families of graphs with known niche numbers, we
20
summarize these results in the following theorem. (Wm
is the wheel with m+l vertices.)
Theorem 2.1.
n(Km) = 1 for m > 2
* = 0 for m > 3
n = 0 for m > 9 and m = 7
n(C8) = 1 and n(C4) = n(C5) = n(c6) =2.
n 3
n > 3
* 8.
Seager[39, 40] also achieved several results in
volving trees. Theorem 2.2, to be given below, guar
antees that no tree of maximum degree 5 or more is a
niche graph. Seager has shown that all trees of
maximum degree 3 or less are niche graphs with the
exception of K2 and % She has several partial
results on trees with maximum degree 4, but in the
general case the niche numbers of such trees are still
unknown.
The existence of so many classes of graphs with
infinite niche number makes characterizing the graphs
which have a finite niche number, or a niche number of
zero, desirable. No useful characterization is yet
known, however. Sakai[36] showed that no forbidden
21
subgraph characterization is possible by discovering
this theorem:
Theorem 2.2. The disjoint union of a graph and its
line graph is a niche graph.
Sakai proved this by construction; she also pro
vided a method of starting with any graph G and con
structing a digraph whose niche graph is connected and
has G as an induced subgraph.
The authors of the original niche graph paper
found a sufficient (but not necessary) condition to
cause a graph G to have an infinite niche number[6]:
Theorem 2.3. If G is Km+1free and n(G) < , then
G has maximum degree at most 2m(ml).
They also established an upper bound on finite
niche numbers for a graph G of V(G)  ; Bowser and
Cable[4] later refined this to twothirds of V(G).
This bound is rarely approached; substantial improve
ment may be possible. In practice, all of the graphs
that were first investigated and found to have finite
niche numbers had niche numbers of zero, one, or two.
This naturally suggested the question of whether there
were graphs with larger finite niche numbers. Bowser
(personal communication) wrote a computer program
22
which established that only five nonisomorphic graphs
with fewer than seven vertices had niche number two,
and none had a larger finite niche number. The
existence of graphs with large finite niche numbers
was one of the major open questions in niche graphs
until 1991.
The question was settled by Fishburn and Gehr
lein[ll], who produced a graph on 11 vertices with
niche number four, and a graph on 14 vertices with
niche number three. They also confirmed Bowser's
computer results (including the fact that there are 21
connected graphs on seven vertices with niche number
two, and none with higher niche number). While this
answered the question of whether there were graphs
with finite niche number greater than two, Fishburn
and Gehrlein accomplished even more. They produced an
infinite family of graphs which had members with arbi
trarily large niche numbers. The actual niche numbers
of these graphs are not known; however, they are
bounded below and are finite. In a recent paper[12],
Fishburn and Gehrlein extended their computer search
to graphs with eight vertices and discovered the two
smallest graphs with niche number three. On eight
vertices there are 11,302 unlabeled graphs without
isolated vertices. Of these 9,560 are niche graphs;
23
565 have niche number 1; 174 have niche number 2;
1,001 have infinite niche number, and only two have
niche number three. The question of the order of the
i .
smallest graph with niche number four is still open,
though it must be9, 10, or 11.
This summary of known facts about niche graphs
and niche numbers indicates that there are many prob
lems which have not been resolved. New results in
this thesis fall into three major categories. Many
types of unit interval graphs are proved to be niche
graphs in the next chapter. Later chapters explore
alternative definitions of the niche number of a graph
which (by relaxing the extraverticesisolated re
quirement) give every graph a finite niche number.
Using these definitions, new niche numbers are estab
lished for several classes of graphs, and bounds on
the new niche numbers of complete bipartite graphs are
found. A different relaxation (allowing cycles or
loops) gives rise to the cyclic and loop niche num
bers; some preliminary results regarding them are
presented. In addition, a serendipitous observation
made while proving a sequence of theorems provides a
new way of labeling unit interval graphs, and counting
the number of different labeled graphs reveals a well
known combinatorial formula in an unexpected context.
24
3
NICHE GRAPHS AND UNIT INTERVAL GRAPHS
Unit interval graphs are the intersection graphs
of intervals of equal length on the real line. Each
interval is represented by a vertex, and two vertices
are connected by an edge if and only if their inter
vals overlap. Unit interval graphs have several well
known properties:
Theorem 3.1. (Roberts[33]) i) A graph G is a unit
interval graph if and only if there is an ordering of
the vertices of G, {v1#v2,..., vn}, such that if vL and
Vj are adjacent and i
adjacent to both Vj and v^
ii) If a graph G is a unit interval graph, then its
vertices, {vx,v2,...,vn}, and maximal cliques, {Cx,
C2,..., Cm}, can be ordered so that each clique con
sists of consecutively ordered vertices, and, if i
C contains a vertex of lower index than any vertex of
Cj, and Cj contains a vertex of higher index than any
vertex of
25
iii) An interval graph is unit interval if and only
if K13 is not an induced subgraph.
Although Roberts[32] proved that the competition
number of every interval graph (without an isolated
vertex) is one, the situation for niche numbers of in
terval graphs is not as simple. Complete graphs have
niche number one; paths (on at least three vertices)
have niche number zero; stars (with at least three
rays) have infinite niche number. Nevertheless, all
are interval graphs.
Since the problem of determining niche numbers of
interval graphs appears to be quite difficult, we will
investigate a smaller set of graphs. Since unit in
terval graphs are precisely those interval graphs
which do not have stars as induced subgraphs (and thus
remove from consideration a large class of graphs with
infinite niche number), they provide a promising
starting point. We note again that complete graphs
are not niche graphs, but have niche number one. Our
investigation will focus on incomplete unit interval
graphs and attempt to determine which of these graphs
are also niche graphs.
26
3.1 Types of Unit Interval Graphs That Are Niche
Graphs
Our first result allows us to assume, for the
remainder of this chapter, that the unit interval
graphs we consider are connected:
Theorem 3.2. If each component of a disconnected unit
interval graph G is either a niche graph or a complete
graph, then G is a niche graph.
Proof: We will construct a digraph on V(G) that
has G for its niche graph. By Theorem 3.1, the ver
tices of G can be ordered so that every maximal clique
consists of consecutively numbered vertices; such an
ordering induces an ordering of the components. The
incomplete components are niche graphs by hypothesis,
so on the vertices of each such component there is an
acyclic digraph whose niche graph is that component.
Specifically, among the vertices of every incomplete
component are a vertex with no inarcs and a vertex
with no outarcs. To specify the arcs of the digraph
on V(G) that will have G as its niche graph, begin
with the arcs of each of these digraphs on the incom
plete components. Then, if there are any complete
components of G which are not the last component of G,
choose a vertex in the next component which has no in
27
arcs and add arcs from each vertex of : the complete
component to the chosen vertex. Finally, if the last
component of G is complete, choose a vertex with no
outarcs (if there is one) in the preceding component
and add arcs from it to each vertex of the last compo
nent. If there is no such vertex, the preceding com
ponent of G is also complete; choose any vertex in it
and add arcs from it to each vertex of the last compo
nent.
We claim the digraph described is acyclic and has
G as its niche graph. That it is acyclic is clear:
the individual digraphs for the incomplete components
are acyclic by hypothesis, and all other arcs go only
from one component to a succeeding component, so there
can be no cycles within components nor between compo
nents. The niche graph of the digraph, again by hypo
thesis, contains all the edges of the incomplete com
ponents. It also contains the edges of each complete
component, for (except possibly for the last compo
nent) the vertices of each complete component have a
common prey. Since this common prey has no other
predators, and since the predators of it have no other
prey, no additional edges are induced. If the final
component of G is complete, some vertex of the pre
ceding component preys on each vertex, so all the
28
edges of the final component are induced. If the pre
ceding component was not complete, the predator vertex
had no other prey, and no vertex of the final compo
nent has any other predator, so no extraneous edges
can be induced. If the preceding component was com
plete, some vertex of the last component is preyed
upon by all the vertices of the preceding component,
but since the predator vertex for the final component
is already adjacent to every other vertex of the
preceding component, again no additional edges are
induced.
Note that the above proof and construction work
even if the unit interval graph consists entirely of
complete components. In the rest of this chapter, we
will assume, unless otherwise specified, that the unit
interval graphs considered are incomplete and connect
ed. We will also assume that when we refer to the
vertices of a unit interval graph G as {vl, v2, . vn}
and its maximal cligues as {C^, C2,..., Cm} the ver
tices and cliques are ordered as indicated in Theorem
3.1, so that maximal cliques consist of consecutively
numbered vertices, and each maximal clique has a first
(lowestnumbered) and a last (highestnumbered) ver
tex. We now show that unit interval graphs with cer
tain properties are niche graphs.
29
Theorem 3.3. A unit interval graph G with exactly two
maximal cliques is a niche graph.
Proof: Let the unit interval graph G have ver
tices V = {vl, v2,..., vn} and maximal cliques C^ and
C2. Let Vj^ be the first vertex of C2 and Vj the last
vertex of C3. Construct a digraph on V as follows:
draw arcs from each vertex of ^ to Vj+1, and addition
al arcs from v.^ to each vertex of C2. Clearly the
niche graph of this digraph is G: the vertices of Cl
have a common prey, so are all adjacent to each other;
the vertices of C2 have a common enemy; no other ver
tex has either an inneighborhood or an outneighbor
hood of more than one vertex, so there are no more
adjacencies in the niche graph.
Theorem 3.4. A unit interval graph G with exactly
three maximal cliques is a niche graph.
Proof: As before, let the vertices of G be V =
{Vi, v2,..., vn}; let the maximal cliques be {Clf C2,
C3}. We consider two cases depending on whether the
intersection of and C3 is or is not empty.
Case 1: C1nc3 = 0. Define an acyclic digraph on
V as follows: draw arcs from the vertices of C1C2 to
the vertices of C2, and from ^13^ to the vertices of
C3. This digraph is clearly acyclic, and has G as its
30
niche graph. SincerC3 and C2 are not disjoint (remem
ber we are dealing with connected graphs) all the
vertices of C^ have a common prey. Thus C2 is a com
petition clique, and both C2 and C3 are commonenemy
cliques. No other edges can occur in the niche graph.
All arcs originate in C1# so no competition edges can
have a vertex outside of as an endpoint. All arcs
end in C2uC3, so no commonenemy edge can have an end
point in ClC^; furthermore, no vertex in C2C3 can be
adjacent to a vertex of C3C2, for their predators are
disjoint.
Case 2: Cj^ and C3 are not disjoint. We will
partition V into five subsets: = C1C2, V2 = C2C3,
v3 = ClD^PIC^ v4 = C2C^, and V5 = C3C2. Note that
this is a partition; every element of V is in one of
these subsets, no subset is empty, and these subsets
are mutually disjoint. Also note that Cj^ = V1uV2uV3,
c2 = V2uV3uV4, an<3 c3 = V3uV4uV5. Construct a digraph
on V as follows: each vertex in C3 preys on each ver
tex in V4, each vertex in C2 preys on each vertex in
V5, and each vertex in V2 preys on each vertex in V3.
We claim that the niche graph of this digraph is G.
Clearly C1 is a competition clique, as is C2. Since
V2 has at least one vertex in both C3 and C2, that ver
tex preys on each vertex of V4uV5uV3, which is just
31
equal to C3, so C3ris a commonenemy clique. Thus all
the edges of G are accounted for.
We still need to verify that there are no ad
ditional edges in the niche graph of this digraph.
First note that, since V^, V2, and V3 are already in
one clique, as are V2, V3, and V4, any additional
competition edge in the niche graph would have to.come
from a vertex in and a vertex in V4 with a common
prey, but the vertices of and the vertices of V4
prey on disjoint sets. In a similar fashion, no extra
commonenemy edge is possible; the only vertices with
predators are in C3.
We will prove one more theorem in this vein, but
there does not appear to be any immediately obvious
way to extend these arguments. The next theorem has
five different cases to consider, and the proof will
only be sketched. The proliferation of cases does not
cease at five; to prove a similar theorem in the same
fashion for a unit interval graph with five cliques
would involve fourteen cases. After noting two spe
cial types of clique structure which will allow us to
prove that the unit interval graph is a niche graph
and investigating what properties a unit interval
graph that is not a niche graph would possess, we will
consider the question of how many different clique
32
structures an ordered unit interval graph with a given
number of cliques can have.
Theorem 3.5. A connected unit interval graph G with
four maximal cliques is a niche graph.
Proof: As noted above, we will only sketch the
proof. There are four maximal cliques, {Cx, C2,. C3,
C4}. We look at five cases.
Case 1: The four cliques have a common vertex.
This is a special case of Theorem 3.6, proved below.
Case 2: CjO^ = 0 and C2nc4 = 0, i.e., there is
minimal overlap of the cliques. This is a special
case of Theorem 3.7, proved below.
Case 3: Cx intersects only C2; C2, C3, and C4
have a common vertex. We partition the vertices of G
as follows: Vl = C1C2; V2 = C2flC1; V3 = C2C3C1
(and may be empty) ; V4 = C3C4; V5 = C2nc3nc4; V6 = C3
C2; and V7 = C4C3. Note that all sets are nonempty
except possibly the one noted. The arcs of the di
graph on V(G) are: from to V4, from C2 to V6, from
C3 to V7, and from V4 to V5. It is easy to verify that
the niche graph of this digraph is G.
Case 4: The first three cliques intersect; C4
only intersects C3. This is just the reverse of case
33
The appropriate
3 where C2 plays the role of Cg..^.
adjustments to construct the digraph are easy.
Case 5: C2 intersects c2 and C3 but not C4; C4
intersects C2 and C3 but not Ci . Let V2 = C2C2;
V2 = C2C3V3 = Cinc3; v4 = C3C4C2; v5 = c2nc4;
V6 = C3C2; and V7 = C4C3. Only V4 may be empty. The
arcs of the digraph on V(G) are from C2 to V5, frpm C2
to Vg, and from C3 to V7. Note that V3 already preys
on C4. This digraph can be shown to have G as its
niche graph.
Although induction on the number of cliques does
not appear to be a promising line of attack, some
special structures can be treated. For example, in
the next section we will extend the method used in
case 2 of Theorem 3.4 to establish the existence of a
family of unit interval graphs with an arbitrarily
large number of cliques which are also niche graphs.
3.2 Are All Incomplete Unit Interval Graphs
Niche Graphs?
Results in this section are fragmentary, and
represent efforts to establish by induction the truth
of the question in the title. While no final answer
is yet available, one of the consequences of the par
tial results is that the clique structure of any mini
34
mal counterexample is established. (A minimal coun
terexample is the smallest incomplete unit interval
graph that is not a niche graph.) From Theorem 3.2 we
know that such a counterexample must be connected,
since any disconnected unit interval graph composed of
components which are themselves niche graphs (or com
plete graphs) must be a niche graph. Additionally,
the digraphs in the previous proofs, constructed to
have a desired niche graph, have the property that
each clique of the niche graph is either an in
neighborhood or an outneighborhood of a single ver
tex. This property will be true of the digraphs we
construct in the proofs of this section as well.
These observations will guide our assumptions in the
final Theorem. We will begin by showing that some
families of unit interval graphs are niche graphs, and
finish by summarizing what we know would have to be
true of the smallest unit interval graph that is not
a niche graph.
Theorem 3.6. Every unit interval graph 6 whose
maximal cliques have a nonempty intersection is a
niche graph.
35
Proof: With the usual labeling of vertices V =
{vx, v2,..., vn} and cliques {Cx, C2,..., Cm},
partition V into 2ml nonempty subsets as follows:
II r > CiCi+1 for i = 1, m1;
Vm = 0^002^1
Vm+i = Ci+iCi for i = 1,..., m1.
other words, for i
does not overlap the succeeding clique, Vm is the ver
tices which all the cliques have in common, and, for
i>m, Vi is that part of Cm_i+1 which does not overlap
the preceding clique. Remember that these cliques are
maximal and consist of consecutively numbered verti
ces so that Ci Ci+1 consists of the set of consecutive
vertices beginning with the first vertex of CL and
going up to, but not including, the first vertex of
the next maximal clique, Ci+1. When we get to Vm, it
consists of all the vertices beginning with the first
vertex of Cm and going up to, and including, the last
vertex of C^. The subsets after Vm are almost mirror
images of the subsets before it; consists of
the vertices from, but not including, the last vertex
of to, and including, the last vertex of Ci+1.
Clearly these subsets are all disjoint, and each
clique C.^ is the union of the m consecutive subsets
beginning with and ending with Vm+i_1.
36
Now create a digraph on V by drawing arcs from
each vertex of C^_ to each vertex of Vm+i for i = 1, ,
m1, and arcs from each vertex of Vm1 to each vertex
of Vm. We claim that this digraph has G as its niche
graph. Clearly each of the first m1 cliques is a
competition clique in the niche graph. Since Vm_1 is
in each of the first m1 cliques, each of its vertices
has arcs to every vertex in Vm+1uVm+2u.. uV2m_1, as well
as to Vm. This just says that it has arcs to every
vertex of Cm, so Cm is a commonenemy clique in the
niche graph. It is easy to verify, as in the proof of
Theorem 3.4, that no extraneous edges are present.
A unit interval graph which has the property that
the intersection of all its maximal cliques is non
empty is in some sense at the far end of the spectrum
from a unit interval graph whose cliques intersect
minimally. However, a unit interval graph of this
second type also is a niche graph, as the following
theorem proves. (This theorem appears in Bowser and
Cable[5] in a slightly different form, with a differ
ent proof.)
Theorem 3.7. If the intersection graph of the maximal
cliques of a unit interval graph G is a path, then G
is a niche graph.
37
Proof: With the usual numbering of maximal
cliques {C^, C2,..., Cm}, the hypothesis of the theorem
says that C;j_nci+2 = 0 for i = 1, , m2, that is, each
clique intersects only the immediately preceding and
immediately succeeding clique. The main idea of the
proof is to construct a digraph in which each odd
numbered clique preys on a vertex in the succeeding
clique, and each evennumbered clique is preyed upon
by a vertex in the preceding clique. One slight ad
justment for the final clique (if oddnumbered) com
pletes the proof.
Set up a digraph on V(G) according to the follow
ing rules: for i odd (and less than m) create an arc
from each vertex of Ci to the lowestnumbered vertex
succeeding the vertices of C^. For i even (and less
than or equal to m), create an arc to each vertex of
from the highestnumbered vertex preceding the ver
tices of Ci. If m is even, this digraph has G as its
niche graph. (The case where m is odd is considered
in the next paragraph.) It is clear that each maximal
clique of G is in the niche graph. Since there are
outarcs only from vertices in oddnumbered cliques,
and these are disjoint by hypothesis, and the arcs
from different oddnumbered cliques go to different
vertices, no additional competition edges can be in
38
the niche graph. Similarly, inarcs go only to even
numbered cliques, and no additional commonenemy edges
can exist in the niche graph.
If m is odd, so that the vertices of Cm have no
succeeding vertex on which to prey, there are two
cases to consider. If has no simplicial vertex,
every vertex in it is also in Cm_2 or in Cm (but cannot
be in both). Then, by the previous construction, the
vertices of Cm_2 all prey on the first vertex in Cm,
and one vertex of Cm_2 preys on the vertices of
Simply have the last vertex of Cm_2 prey on the ver
tices of Cm, and the construction is complete. The
clique Cm is in the niche graph, and the only arcs to
vertices in are from the last vertex of Cm_2,
so no extra commonenemy edges appear in the niche
graph.
If Cm_1 has simplicial vertices, then the previous
construction resulted in creating arcs from Cm_2 to the
first of those vertices. Remove those arcs, and in
stead draw arcs from each vertex of Cm_2 to the first
vertex of Cm. Keep the arcs from the vertex of Cm_2
immediately preceding Cm_1 to the vertices of Cj^.
Finally, draw arcs from the last vertex of Cm_2 to each
vertex of Cm. Now Cm_2 is a competition clique, and
and Cm are commonenemy cliques in the niche
39
graph. Furthermore, since all arcs ?to vertices in the
last two cliques come from vertices in Cm_2, there are
no extraneous competition edges in the niche graph;
since the vertices of CmCm_1 have arcs only from the
last vertex of Cm_2 and the vertices of have
inarcs only from a vertex preceding that, no extrane
ous commonenemy edges can exist in the niche graphJi
Theorem 3.8 If a unit interval graph with the usual
labeling has the set of first vertices (or the set of
last vertices) of each maximal clique labeled consecu
tively, then the unit interval graph is a niche graph.
Proof: Let {Clr C2,..., Cm} be the maximal
cliques of G with first vertices {vx, v2,..., vm}. We
define the arcs of a digraph D on V(G) as follows:
for i = 1,..., m1 let each vertex of prey on the
vertex following the last vertex of C^. Also let the
vertex immediately preceding Cm prey on all the ver
tices of Cm. We claim that G is the niche graph of D.
Clearly all maximal cliques of G are in the niche
graph of D; we must show there are no additional
edges. First, suppose va and vb attack vc, with a
Then either vc is the vertex immediately following a
maximal clique containing va (in which case vb is in
that clique, and vavb is an edge of G) or vc is in Cm
40
and va immediately precedes Cm. But in this case,
since vb also preys on vc, vc is the vertex immediately
succeeding a clique containing vb, and since that
clique must contain va, vavb is again an edge of G.
Now consider the possibility of an additional
commonenemy edge, where va attacks vb and vc. If va
is the immediate predecessor of Cm, then vbvc is an
edge of G. Otherwise, both vb and vc are vertices
immediately following maximal cliques containing va,
say Cp and Cg, respectively. But then, since the
first vertices of the maximal cliques are consecutive,
vb and vq belong to Cg+1: cq+i must begin with the
vertex succeeding va or an earlier vertex (i.e., vb or
an earlier vertex), and must include at least vc,
since it must extend beyond Cg. Thus vbvc is an edge
of G, and the niche graph of the digraph D has no
edges not in G. Therefore G is a niche graph. (To
prove the theorem for the case where the last vertices
of the cliques are consecutive, all that need be done
is to reverse the numbering of the vertices and
cliques.)
The last theorem has an inductive flavor, but
unfortunately requires something similar to a simpli
cial vertex to allow us to show that the next larger
graph is also a niche graph. However, it does help to
41
l
further characterize the minimum counterexample, if
one exists.
Theorem 3.9. If all incomplete unit interval graphs
on n or fewer vertices are niche graphs of acyclic
digraphs with each maximal clique an in or out
neighborhood of some vertex, then any unit interval
graph G on n+1 vertices, with a vertex x that is
neither the first nor the last vertex of any maximal
clique, is a niche graph.
Proof: G x is a unit interval graph, and thus
by hypothesis has a generating digraph D of the type
described. Since x was neither the first nor the last
vertex of any maximal clique, G x has the same num
ber of maximal cliques as G. With our usual ordering,
each clique C^(G x) is either the same as Ci(G) (if
neither contains x), or is just C^JG) {x>. We will
modify the digraph D so that it is a digraph whose
niche graph is G. Each clique of G x is an in or
out neighborhood of some vertex of D. Let D' be the
digraph obtained from D by setting V(D') = V(D) u {x}
and A(D') = A(D) u {xy  x e Ci(G) and Ci(Gx) is the
inneighborhood of y in D} u {zx  x e Ci(G) and C^G
x) is the outneighborhood of z in D}. We claim the
niche graph of D' is G. Clearly every edge of G is in
42
the niche graph of D'. Suppose that some other edge
not in G is in the niche graph of D'. Either it has
x as an endpoint or it does not. Assume first it has
x. If the edge (call it ax) is a competition edge,
then there are arcs ay and xy in D' for some vertex y.
But the only arcs xy are to vertices which are preyed
upon by the members of a maximal clique to which x
belongs, so ax must be an edge of G. A similar argu
ment holds if ax is a commonenemy edge.
If the edge does not have x as an endpoint, call
it ab. If ab is a competition edge, then ax and bx
are arcs in D', and x is in a maximal clique which is
the outneighborhood of a, and in a maximal clique
which is the outneighborhood of b. But the inter
section of these two maximal cliques cannot be only x,
else x would be the first element of one clique and
the last element of the other. So a and b have an
other common prey, and ab is already an edge of G.
Now we have several theorems which are quite sug
gestive; unfortunately, the result they suggest
remains unproven. At this point, however, we can
state with some precision what an incomplete unit
interval graph which is not a niche graph must look
like. The smallest such example would have to have at
least 5 maximal cliques, each vertex would have to be
43
either the first vertex or the last vertex of some
maximal clique, at least two cliques must be disjoint,
and neither the set of first vertices nor the set of
last vertices of the maximal cliques could be consec
utive. Such a unit interval graph can be constructed
easily enough, but all examples investigated have
proved to be niche graphs. While we have not yet been
able to actually prove that the cliques of any unit
interval graph can be made the appropriate in and
out neighborhoods of a generating acyclic digraph, we
think there is sufficient evidence to conjecture: all
incomplete unit interval graphs are niche graphs.
3.3 The Number of Possible Clique Structures for
Labeled Unit Interval Graphs
In several of the proofs of the preceding sec
tions, the structure of the maximal cliques of the
unit interval graph is of substantial importance. If
the first clique intersects the last, for example,
application of Theorem 3.6 guarantees that the graph
is a niche graph as well. Furthermore, the proofs of
Theorems 3.3, 3.4, and 3.5 show that the number of
cliques and the ways in which they intersect each
other are important to the construction of a digraph
44
which has the target unit interval graph as its niche
graph.
Given the importance of this intersection struc
ture, the question of how many different structures
are possible for a given number of maximal cliques
naturally arises. By clique structure we just mean
which cliques intersect each other (essentially the
clique graph of the graph). To make these ideas more
precise, let us begin with a few definitions. A unit
interval graph G of order n is properly labeled if its
vertices are numbered {v^ v2,..., vn} and its maximal
cliques are numbered {Clr C2,..., Cm} so that each
clique consists of consecutively numbered vertices
and, for i
If the properly labeled unit interval graphs G and H
each have m maximal cliques, {Cl, C2,..., Cm}, we will
say that G and H are cliquesimilar if there do not
exist i and j such that Ci and Cj are disjoint in one
of G and H but intersect in the other. It is clear
that this induces a partition of the labeled unit in
terval graphs with m maximal cliques into equivalence
classes of cliquesimilar graphs. The question we
want to answer is, for a given m, how many classes of
cliquesimilar labeled unit interval graphs are there?
45
An important consideration is that in unit inter
val graphs with the usual notation of this chapter,
the cliques consist of consecutively numbered vertices
and so are naturally ordered by their first (or last)
vertices. If we look at the vertices {v^, v2,;.., vn}
of a unit interval graph and restrict our attention to
the subscripts of the first vertex of each maximal
clique, we get an increasing sequence {a1=l,a2, . am>;
looking at the subscripts of the last vertex of each
maximal clique we get an increasing sequence {blf
b2,..., bm=n}. Combine these two sequences into one
nondecreasing sequence S of length 2m, breaking ties
by the rule: if a^ = bj, then a.^ precedes bj in S. Now
(we are transforming the problem into another problem
with a wellknown solution) replace each a.^ by a plus
1, and each b.^ by a minus 1. We have a sequence of m
positive and m negative ones of length 2m. Note that
it is easy to reconstruct the clique structure of the
unit interval graph from its sequence of plus and
minus ones; the first clique intersects the same num
ber of cliques as the number of plus ones preceding
the first minus one, and so on.
We wish to establish a onetoone correspondence
between the sequences of m positive and m negative
ones in which the partial sums are all nonnegative
46
and the classes of cliquesimilar unit interval graphs
on m maximal cliques. It is clear that any two
cliquesimilar unit interval graphs will produce the
same sequence of plus and minus ones. It is also
clear that any sequence derived from a unit interval
graph can have no negative partial sum; each clique
begins with a plus one and ends with a negative one,
so a negative partial sum would indicate that some
clique ended before it began. If we start with any
sequence of m plus ones and m minus ones with no neg
ative partial sums, we can construct a unit interval
graph producing that sequence easily. The i posi
tive one indicates the beginning of the i maximal
clique; it will intersect all the maximal cliques Ck,
k
all the maximal cliques Cj, j>i, for which the j +1
occurs before the i 1. So the onetoone corres
pondence is established. We can now state a theorem.
Theorem 3.10. The number of different clique struc
tures possible for a labeled unit interval graph with
m maximal cliques is the m Catalan number,
(1/(m+1))(2m!)/(m!m!).
Proof: We have established a onetoone corre
spondence between the clique structures (i.e., the
47
cliquesimilar classes) and the sequences of m posi
tive and m negative ones with no partial sums nega
tive. But this is already known to be the m Catalan
number, a result established in 1946 by Erdos and
Kaplansky[9]. An elegant proof can be found in
Honsberger[20].
It is easy to see that a unit interval graph, or,
more precisely, all the graphs of a cliquesimilar
equivalence class, are disconnected if and only if the
corresponding sequence of plus and minus ones has at
least one partial sum of zero (in addition to the tri
vial zero sums at the start and end of the sequence).
This observation makes it easy to determine the number
of cliquesimilar equivalence classes of connected
labeled unit interval graphs with m maximal cliques:
the number is just the number of sequences with no
nontrivial partial sums of zero. But since each
sequence must begin with +1 (and end with 1), if we
discard these two end numbers, what we require is that
the remaining sequence of 2m2 plus and minus ones
must have no negative partial sums. This will be suf
ficient to keep the partial sums of the whole sequence
greater than zero, and the number of such sequences,
from the discussion of the previous theorem, is just
the (m1) Catalan number. We have just proved
48
Theorem 3.11
. The number of different clique struc
tures on connected labeled unit interval graphs with
m maximal cliques is the (m1) Catalan number,
(1/m)(2m2)!/((m1)!(m1)!).
49
4. Alternative Definitions for the Niche Number, and
Some of Their Consequences
Although the niche number of a graph is well
defined, the concept has some characteristics which
are not necessarily desirable. Not only are niche
numbers difficult to compute, but many classes of
graphs turn out to have infinite niche number. In
fact, Cable, Jones, Lundgren, and Seager [6] showed
that, if a graph G is Km+1free with maximum degree
greater than 2m(ml) it must have infinite niche
number. In a sense, there isn't room to add enough
isolated vertices. Are there reasonable alternatives?
This chapter discusses some possibilities. It has
been published, in slightly different form, in Con
gressus Numerantium jointly by the author with Jones,
Lundgren, and Seager[2].
The original niche number definition is certainly
usable, and sensibly parallels the definition of com
petition number. It leads to an interesting theory.
However, if the niche number is viewed as a measure of
how "close" a graph is to being a niche graph, a niche
number of infinity seems unsatisfactory, especially
for a graph like K1j3 : it can be turned into a niche
50
graph by adding a pendant edge, or by the disjoint;
union with itself, or by the disjoint union with a
triangle. To say that Klf3 is infinitely far from
being a niche graph does not do the situation justice.
Figure 4.1 Digraphs Whose Niche Graphs Contain Kj 3
Some alternative definitions of niche number are
suggested in this chapter. We show that these defini
tions, which retain the flavor of the original niche
number definition, have the desirable characteristic
of being finite for all graphs. Furthermore, the
related alternative definitions of competition number
would not change the more widely known results in that
theory.
51
4.1 Alternatives for the Niche Number Definition
Why search for alternative definitions of niche
number? We are primarily interested because the
current definition allows a niche number of infinity.
The niche number should in some sense measure how
difficult it is to turn a given graph into a niche
graph, and "infinitely difficult" doesn't seem the
proper answer. For example, we will show that every
graph is an induced subgraph of a niche graph which
has no more than 9e(G) additional vertices, where
0e(G) is the minimum number of cliques needed to cover
the edges of the graph. Additionally, Sakai[36] has
shown that the disjoint union of any graph with its
line graph is a niche graph. It is only when requir
ing additions to the graph to be isolated vertices
that some graphs cannot be changed into niche graphs.
The addition of isolated vertices is natural in
the context of competition graphs. To create an edge
between two vertices in a competition graph, all that
need be done is to add arcs in the food web from the
two predators to a prey with no other predators. If
no such prey exists, adding a new prey to the food web
simply creates an isolated vertex in the competition
graph. Thus every edge in the competition graph can
52
be created with only the addition of isolated vertices
as a side effect. A food web for the graph has been
created with new prey, but no new predators, and so no
undesired new edges, appear.
In contrast to the competition graph situation,
in a niche graph additional edges cannot always be
added just by appending an extra vertex and drawing
two more arcs. The difficulty is that not only common
prey, but also common enemies, create edges. Thus,
adding arcs from existing vertices to a new vertex,
which will certainly create desired edges among the
existing Vertices, may also have the undesired effect
of creating edges joining the new vertex (which should
be isolated) to some previously existing vertices
which are also prey of the vertices preying on the new
vertex. This is the reason that many graphs have
infinite niche number. We have proposed relaxing the
requirement that additional vertices must be isolated.
We will denote the (original) niche number by n0.
Suzanne Seager, in a communication to Kathryn Fraugh
naugh[41], suggested the following alternative defini
tions of niche number.
The first niche number of a graph G, nx(G), is
the minimum nonnegative integer k such that the dis
53
I
joint union of G and k vertices in complete components
(not connected to G) is a niche graph.
The second niche number of a graph G, n2(G), is
the minimum norinegative integer k such that the dis
joint union of G and k vertices in other components is
a niche graph.
The third niche number of a graph G, n3(G), is
the minimum norinegative integer k such that G is an
induced subgraph of a niche graph on (V(G)  + k)
vertices.
In other words, each new niche number still
counts the number of extra vertices required to make
G into a niche graph. The first requires these extras
to be in their own complete components; the second to
be in components' separate from G though not necessari
ly complete; the third allows the extras to be con
nected to G as lpng as G is an induced subgraph. This
chapter and the next explore some of the ramifications
of these definitions.
Note that these new niche numbers will not make
much difference when G has a finite (original) niche
number of zero, ione, or two. If any niche number is
zero, they all are: G is a niche graph. If n0(G) is
1, so is each other niche number. (But n3(G) can be
1 while n0(G) is infinite; see figure 4.1 above.) If
54
n0(G) = 2, then n^G) = 2 and n2(G)=2; n3(G} is 1 or
!
2. (The fourcycle is an example of a graph which has
n0(G) = 2 and n3(G) = 1; see figure 4.2.) Thus we
already know, for example, from, the original paper
[6], that the niche number (any niche number) of a
complete graph on more than 2 vertices is 1, of a path
on more than 2 vertices is 0, and of a cycle on.more
than 8 vertices is 0.
1
Figure 4.2 n0(C4) = 2, but n3(C4) = 1
The cases where n0(G) is infinite are more inter
esting; the new niche numbers should help differenti
ate among the many different families. Among the
known graphs with infinite (original) niche numbers
are wheels [4], some variations of stars called novas
[ 6 ], and complete bipartite graphs with at least three
55
vertices in one.partition [36]. New niche numbers for
these graphs are largely unknown at present. If n0(G)
is infinite, the other niche numbers may be quite
small, or, as shown in a theorem to be presented in
this chapter, arbitrarily large. K13, for example,
has first and second niche numbers equal to 3, and its
third niche number is only 1, as figure 4.1 shows.
The concept of niche graphs originally derived
from work with Competition graphs, and many of the
initial results, problems, and conjectures were sug
gested by analogy with known results in competition
graphs. The original definition of the niche number
of a graph was chosen to be similar to the definition
of competition number. If we consider the possibility
of changing the. definition of competition number to
parallel these new niche number definitions, a rather
surprising result emerges.
Define the first competition number of a graph G,
k1(G), to be the minimum number of extra vertices, in
complete components, such that the disjoint union of
G and these components is a competition graph. Simi
I
larly the second competition number, k2(G), is the
minimum number of extra vertices (in components,
whether complete or not) such that the disjoint union
of G and these components is a competition graph, and
56
the third competition ntlmber, k3(G), is the minimum
number of extra vertices such that G is an induced
subgraph of a competition graph of order V(G) +
k3(G). It is clear that k(G) > k1(G) > k2(G) > k3(G),
since any set of isolated vertices is also a set of
complete components, thus a set of components, and G,
as a component of a graph, is automatically an induced
subgraph. Less obvious is that these four numbers
must be equal. The following theorem was first proved
by Suzanne Seager[41].
Theorem 4.1. For any graph G,
k(G) = kr(G) = k2(G) = k3(G).
Proof: Consider any food web whose competition
graph has G as an induced subgraph. We construct a
food web on the same number of vertices whose compe
tition graph is the disjoint union of G and isolated
vertices, showing that k(G) < k3(G). Then by the
remark above we !will have equality of all four com
petition numbers.
Eliminate all arcs which do not come from a
i
vertex of G. The remaining digraph has as its
competition graph G (since all competitions within G
I
remain) and some ;isolated vertices (with no outarcs,
!
the remaining vertices can have no competitions).
57
Therefore k(G) j < k3(G), and k(G) = kx(G) = k2(G) =
k3(G) .
Whether this result could prove useful for
determining unknown competition numbers has not been
investigated.
4.2 Basic Properties of Mew Niche Numbers
The principal objection to the original defini
tion of niche number was that it is infinite for some
graphs. Each of the new definitions answers that ob
jection. In some of the proofs that follow, food webs
which have a given graph G as a subgraph of their
niche graphs are constructed. When referring to the
vertices of the. food web, the vertices which corre
spond to vertices of G will be called graph vertices;
the other vertipes of the food web will be called
extra vertices. !
Theorem 4.2. For every graph G,
(1) n1(G),n2(G), and n3(G) are finite.
(2) nx(G) < 0e(G) + 1.
(3) n2(G) < 0e(G).
Proof: First note that if n0(G) = k, then G and
k isolated extra vertices form a niche graph. Since
each extra vertex is in its own complete component,
58
n^G) < k, for G and k extra vertices in complete
components form a niche graph. That is, n0(G) >
n^G). Similarly, nx(G) > n2(G), since n1(G) is the
number of extra vertices in complete components which,
together with G, form a niche graph, and n2(G) is the
minimum number of extra vertices in components (com
plete or not) which suffice. Clearly n2(G) > n3(G) as
well, for if G and k vertices in other components form
a niche graph, G is an induced subgraph of that niche
graph. In other words, if a digraph D demonstrates
that n1(G) is k; or less, the same digraph gives k as
an upper bound for n2(G) and n3(G). Therefore showing
that n3(G) is finite for all graphs G will prove part
(1)
Let G be an arbitrary graph. Construct a digraph
for G as follows: select an edge clique cover of the
graph. To the vertex set of the graph, add a new
vertex for each element of the edge clique cover, and
add one additional vertex (the sink) This (the union
of the graph vertices, the clique vertices, and the
sink) will constitute the vertices of the digraph.
Arcs in the digraph will be from each graph vertex to
each clique vertex whose clique contains the graph
vertex, and from each clique vertex to the sink. The
niche graph of this digraph will have no edges between
59
the vertices of G and any other vertices, because
nothing preys oh the graph vertices (hence there are
no commonenemy edges involving any graph vertex),
graph vertices prey only on clique vertices, and
clique vertices prey only on the sink vertex ( so no
common prey edge can connect a graph vertex to an
extra vertex). If x and y are graph vertices, there
will be an edge between them in the niche graph of the
digraph if and only if they both prey on the same
clique vertex, that is, if and only if they are in the
same edge clique, and so have an edge between them in
G. Clearly the clique vertices form a complete graph,
since they all prey on the sink, and the sink is an
isolated vertex in the niche graph. Thus there is a
niche graph consisting of G, a complete graph on the
clique vertices, and an isolated vertex. Hence n1(G),
and therefore also n2(G) and n3(G), are finite.
The construction also gives upper bounds on the
first and second niche numbers mentioned in the theo
rem. We used precisely (0e(G) + 1) extra vertices to
construct the digraph showing that n^G) is finite,
and the sink vertex is unnecessary if the clique ver
tices need not be in complete components.
An example of the construction can be seen below
in figure 4.3.
60
Figure 4.3 A Graph and the Digraph and Niche
Graph Constructed in Theorem 4.2.
While an upper bound is fairly easy to construct,
we have obtained a lower bound only when the maximum
degree of the graph is larger than twice the maximum
clique size. We state a theorem for trianglefree
graphs, and then generalize to other graphs.
Theorem 4.3. For any trianglefree graph G with
maximum degree k (where k > 4), n2(G) > (k 2).
Proof: Let D be a digraph with G as a component
(or components) of its niche graph. Consider a vertex
v in G of degree k, k > 4. Each edge incident to v is
created by a common prey of v and another vertex of G,
or a common enemy of v and another vertex of G. These
(common prey and common enemies) must all be distinct,
for otherwise G would have a triangle. Now consider
the set of all prey of v. This forms a clique in the
niche graph, so at most two vertices of G can be in
61
this set. Furthermore, if the set has any extra ver
tex, it cannot have any graph vertex, because there
are no edges between extra vertices and graph ver
tices. Thus if the set has more than two vertices,
they are all extras. Similar considerations apply to
the set of predators of v. Since k > 4, at least one
set has more than two vertices, so at most two of the
predators and prey of v can be vertices of G. Then
there must be at least k 2 extra vertices, showing
that n2(G) > (k 2).
This result sometimes gives excellent bounds.
Figure 4.4 shows a graph for which the lower bound of
Theorem 4.3 is exactly the niche number.
Figure 4.4
The proof of Theorem 4.3 depends on the fact
l
that, since G is trianglefree, each edge of G must
represent an inneighborhood of exactly two arcs, or
i
an outneighborhood of exactly two arcs. If G has
62
I
larger cliques, then each edge may arise from larger
neighborhoods, and (if G is Kj^ free) as many as m
edges incident with a vertex v may all be created by
one arc from (or to) v in the digraph. Theorem 4.3
may be generalized to take these facts into account.
Theorem 4.4 If a graph G is Km+1free with maximum
degree k and k: > 2m(ml), then n2(G) is at least
(fk/(ml)lm).
Proof: The proof is similar to the proof of
Theorem 4.3. Consider a vertex v of maximum degree in
G, and any digraph D which has G as a component (or
components) of its niche graph. Since G is Km+1free,
no vertex preyed on by any vertex of G has more than
m inarcs, and no vertex preying on any vertex of G
has more than m outarcs. Hence at most (m 1) edges
incident to v in G can be from the same prey (or
common enemy) In D, v can have at most m inarcs
from vertices in G, and also at most m outarcs to
vertices in G. This can create at most 2m (m 1)
edges. If v has greater degree, there must be an arc
to or from an extra vertex. But if any arc goes to an
extra vertex from v, all arcs from v must go to extra
vertices, so v can have at most m arcs from vertices
of G, and they can account for only m(ml) edges inci
63
dent to v in G. Then the remaining (k m(ml) ) edges
must come from arcs to extra vertices, and since each
creates at most (m1) edges in G, there must be at
least (fk/(ml)"m) extra vertices, and n2(G) is at
least (fk/(ml)"jm) If any arc comes from an extra
vertex to v, a similar argument holds.
4.3 Summary
We have suggested some alternative definitions
for the niche number of a graph. These definitions
have the advantages of giving each graph a finite
niche number, retaining the spirit of the original
definition of niche number, and, when adapted to re
define the competition number of a graph, not changing
that more widely studied and firmly entrenched notion.
We have demonstrated further that these alter
native niche numbers have reasonable upper and lower
bounds, and have shown some graphs for which these
bounds are sharp.
The new niche numbers of graphs with original
niche number zero, one, or two, as previously dis
cussed, are already known. Graphs with higher origi
nal niche numbers will be studied in the next chapter,
and we will concentrate on complete bipartite graphs.
64
5. Alternative:Niche Numbers for
Complete Bipartite Graphs
We next look at niche numbers for specific fami
lies of graphs. For graphs with infinite original
niche number, a few results have been discovered. We
concentrate on complete bipartite graphs. Theorems
4.2 and 4.3 give upper and lower bounds on the niche
numbers of these graphs; we make these bounds more
I
precise. For stars (complete bipartite graphs of the
form KlfI1) we will show that the second niche number
is equal to the'upper bound of Theorem 4.2, but for
complete graphs of the form Kj^ the niche numbers
diverge from this theoretical bound substantially.
Theorem 5.1. For n > 2, n) = n2 (Kx n) = n and
n3 = n 2.
Proof: Let, v0 be one of the bipartitions of Klffl
(the center) and {vx, v2,..., vn} be the other (the rim
vertices). Consider first the second niche number.
Since K;j^n is trianglefree, v0 must have a different
common enemy or i common prey with each of the n rim
I
vertices. Sincenone of the rim vertices is adjacent
i
to any other, no more than one (call it V]_) can be,
65
i
say, a prey of v0. If so, then v0 cannot prey on any
other vertex whatsoever, and must be the prey of at
least n 1 other vertices, of which at most one can
be one of the remaining rim vertices. But that would
create edges from that rim vertex to extra vertices,
so all the n 1 other vertices are extras. Now con
sider the question: how can the edge between v0 and
vl be created? They must have a common predator or a
common prey. Since all predators of v0 must be ex
tras, a common predator is impossible because there
would be an edge between it and vQ. A common prey is
also impossible since there would be an edge between
it and v1# Thus v0 does not prey on any rim vertex,
nor is it preyed upon by any rim vertex. Since there
are n rim vertices, each requiring a different common
prey or common predator with v0, there must be at
least n extra vertices in any digraph that has K1>n as
a component of its niche graph. That n extras suffice
is shown by the digraph below: v0 preys on all n
extra vertices and each v_ preys on the corresponding
xi. This also shows that n1(K1^n) = n, since the
resulting niche graph consists of K2 n and n extra
vertices in a complete component.
To show that n3(Kljn) = n 2, note that each rim
vertex must have a distinct common prey or common
66
I
j
enemy with v0. ; At most one prey of v0 can be a rim
vertex; at most 'one predator also, else there would be
an edge between two rim vertices in the niche graph.
Thus at least n 2 extras are necessary, and the
general construction, illustrated for K14 in the
figure below, shows that n 2 are sufficient.
0 1234 1034
WI fW
Xi X2 X3 X4 XL X2
Figure 5.1 4 and Its Digraphs for the
Second; and Third Niche Number
Theorem 5.2. ni(R2,n^ < n + l.
Proof: We construct, on 2n + 3 vertices, an
acyclic digraph D that has a niche graph consisting of
K2fn as one component and the remaining n + 1 vertices
in a single complete component. Let U = {ulf u2} be
one of the bipartitions of K2n, V = {v^ v2, . vn}
the other, and X = {xlf x2, . xn+1} a set of extra
vertices. The union of these three sets is the vertex
set of D. The arc set consists entirely of arcs to or
from the extra vertices. For each extra xif (i =

1,..., n 1), draw arcs u1xi, v^^, Xj_u2, and xivi+1.
67
I
In the niche graph, these arcs will create all edges
Uj^Vj except ujVn and u2v1. Draw arcs u1xn, vnxn,
xn+iu2 / and xn+1vn to create those edges. Note that
extras prey on (and are preyed upon by) only graph
vertices, and graph vertices prey on (and are preyed
upon by) only extras. Clearly there are no edges
between extras and graph vertices, between Uj^ and u2
(since ^ is only a predator, and u2 is only a prey) ,
or between any vertices in V (since each vi preys on
a different extra, and is preyed upon by a different
extra). By adding one final arc xnu2 (which creates
no new edges among graph vertices since xn preys on no
other vertex), all the extras prey on u2. Thus they
form a clique, and the niche graph consists of the
disjoint union of K2n and Kn+1.
This construction is illustrated in figure 5.2.
Figure 5.2 The Construction Described in Theorem
5.2 Applied to K2 4: nx(K2 4) < 5
I
68
The construction illustrated in figure 5.2 has
several suggestive features. One of the bipartitions
has each vertex with an equal number of in and out
arcs; in the other each vertex has only inarcs or
only outarcs. Perhaps the most interesting aspect of
the construction is that no graph vertex has any arc
to or from any other graph vertex. It is somewhat
surprising that we cannot eliminate one or more extras
by increasing the predatorprey relationships among
graph vertices.
We will call arcs in D with both head and tail
vertices in V(G) graph arcs. In the proof that fol
lows we show that the existence of graph arcs can only
increase the number of extra vertices needed to con
struct a digraph with a complete bipartite graph in
its niche graph.
Theorem 5.3. n1(K2 n) = n2(K2 ) = n + l.
Proof: The proof is in three main parts. First,
Theorem 5.2 establishes an upper bound of n + 1 for
the niche numbers. Then we show that no digraph
without graph arcs can have fewer than n + 1 extras.
i
Finally we prove by a number of cases that the use of
graph arcs to create edges of the bipartite graph
always requires at least n + 1 extras.
69
Theorem 5.2 guarantees that the niche number is*
no more than n + 1. Now suppose we have an acyclic
digraph D with K2>n as a component of its niche graph.
Let U = {ulf u2} be one of the bipartitions of K2^n, V
= {vi/ v2,..., vn} the other, and X = {xlf x2,...,
xn+i} a set of extra vertices. If there are no edges
in K2n created by graph arcs, there must be at least
n extras: K2^n has 2n edges and no triangles so each
edge must come from an in or outneighborhood with
exactly two arcs and each extra can have at most two
neighborhoods. Suppose, then, that D has only n
extras. Each extra must have two inarcs and two out
arcs. This means that, in the topological ordering of
D, at least one u (call it u2) and one v (v2) must
precede the first extra, x. Then each arc at u2, and
at vlf is an outarc, since ul and precede all
extras. But u^ has to have n arcs since it has n
edges in the niche graph. Since each extra has an in
arc from Uj, each must (in order to create the n edges
incident to u2) have an outarc to u2, that is to say,
each arc at u2 is an inarc. This means that vl and
u2 cannot be connected in the niche graph, since one
has only outarcis and the other only inarcs. This
contradiction shows that n extras will not work; at
70
least n+1 are necessary ifthere are no graph arcs
creating edges in the niche graph.
Finally, suppose that we have an acyclic digraph
D which has K2/n as a component of its niche graph G
and some of the: edges of K2>n in the niche graph are
created by graph arcs in D. We show, by considering
cases, that at least n+1 extras are still necessary.
We will assume that the edge created by graph arcs is
a competition edge. (If only a commonenemy edge ex
ists, the reverse digraph gives the same niche graph
but changes that: edge to a competition edge.) We call
the two predator vertices uj^ and vlf and the prey ver
tex is given the index 2.
Case 1: ul and vx prey on u2, and ul has no other
prey. Since we assume there are at least three v's,
ux must have at least n1 (> 2) predators, and hence
all must be extras. See figure 5.3.
Figure 5.3 Diagram for Proof of Theorem 5.3
71
Each extra must prey on one of the v's as well. Now
edge u2v1 is impossible. There can be no commonenemy
edge since u2 has two predators already, and v1 cannot
prey on itself / and u^ has no other prey by assump
I
tion. There can be no competition edge since a common
prey of uwould form a cycle, u2 a loop, any other v
a triangle with! an extra, and any extra an edge with
x and u2.
Case 2: ul and v^ prey on u2; ul also preys on
v^. We look at three subcases.
Case 2a: v^ has another predator. This must be
another v since there will be an edge with u^ call
it v2. Now edge v2u2 is impossible by an argument
similar to case 1.
Case 2b: v2 has no other predator, and no other
prey. In this case u2 needs n1 predators since it
has only one competition edge. All must be extras as
argued before. u2 has two predators, but v1 creates
no edges in the niche graph since it preys only on u2.
So u2 needs nT prey, and all must be extras. None
can be the same extras as those preying on u^ else
there would be a cycle. Therefore at least 2n2 ex
tras are needed; and since n > 2, at least n + l.
Case 2c: v1 has no other predator, and one other
prey. The prey must be a v (say v2) since an edge
72
with u2 is forced. But now edge u2v2 is impossible.
v2 can't prey on u2's prey (v2 would make a cycle, u2
a triangle) u2 can't have a common prey with v2 (v2
or u2 would make a cycle, any other v a prohibited w
]
edge, and any x a vx edge).
Case 3: u[ and v2 prey on u2; u2 also preys on
j
v2. This is a little complicated but eventually leads
to a contradiction. First, how can we create edge
u2vi? The only possibility is a common prey, and it
j
must be a v, say v3 (v2 and v2 are not possible) Now
we consider edge u1v3. Again there is only one possi
bility: v2 as a common prey. But at this point edge
I
i
uiv2 (the only missing edge in the K2 3 subgraph we are
constructing) is1 impossible. v2 has two predators al
!
ready and neither can prey on u2; u2 has two prey al
ready and v2 can prey on neither.
In the remaining cases u2 and v2 prey on v2 in
stead of u2.
Case 4: u2 and v2 prey on v2; u2 has no other
prey. First consider edge u2v2: it can't come from
competition because u2 has no other prey than v2, and
since v2 already has two predators (one of which is
u2) the common predator must be v2. Now consider
edge u2v3: no common prey is possible since arc v3v2
would create a triangle. The only possible common
I 73
I
I
predator is u2, ; since already has two prey and any
predator of ux will have an edge with v. After these
arcs are forced, edge u2v3 is impossible. u2 already
has two prey, neither of which can prey on v3 (i^
would create edge v2v3, and isn't allowed any other
prey anyway; v3 would create a loop). v3 already has
two predators, and neither can prey on u2 (u2 would
i
create a loop and v2 would create a cycle).
Case 5: u^ and vx prey on v2; ul also preys on
u2. This is the only remaining possibility. Consid
ering edge ujV2 i gives us two subcases, depending on
I
whether edge u^ is created by a common enemy or by
a common prey, j The only possible common prey for u^
and v2 is u2; the only possible common enemy is
t
I
Case 5a: y2 also preys on u2. Now edge ^vl is
impossible: no common predator (u^ gives a triangle,
v2 a cycle) and no common prey (v2 a cycle, ux a cycle,
vl a loop, any y a vv2 edge, any x an xv2 edge) .
Case 5b: v3 also preys on u2. To get edge ^vl
the only possibility is a common enemy which must be
i
another v, say v3. But now edge u2v3 is impossible.
v3 already has two prey, but u2 can prey on neither;
i
u2 already has two predators, but neither can prey on
i
v3. Since ^ and vx must prey on either v2 or u2, all
possible cases have been exhausted.
74
5.1 The Niche Numbers of Bipartite Graphs with Both
Bipartitions Having More Than Two Vertices
!
The new niche numbers of several complete bipar
tite graphs are already known. In the case of the
smaller graphs, Klfl has all niche numbers 1; K12 has
all niche numbers 0; K2,2 ^as n0' ni' anc* n2 e<3ual to
2 and n3 equal to 1. We have also proved that Kl
(for n>2) has n0 infinite, n^^ and n2 equal to n, and n3
equal to n2, and that K2>n (for n>2) has ^ and n2
equal to n+l. We now turn our attention to complete
bipartite graphs in which both bipartitions have at
least three vertices.
Theorem 5.3 was proved in part by demonstrating
that graph arcs (that is, arcs in the digraph from one
vertex of K2/n to another) were unnecessary. A digraph
with K2^n as a component of its niche graph, with the
minimum number of extra vertices, and without graph
arcs, always existed. The proof considered all possi
ble configurations of graph arcs which would create
edges in the niche graph. Most resulted in contradic
tions, showing the configuration under discussion did
not exist in any: digraph having K2n as a component of
its niche graph. These configurations are still im
possible for any:digraph having Km n (2 < m < n) rather
than K2^n as a icomponent of its niche graph; the
75
proofs can be reproduced word for word. To show that
graph arcs are not necessary to create minimum di
graphs with as a component of the niche graph we
need only consider the lone K2jn case in which graph
arcs are possible. The next theorem does so, and
shows that graph arcs do not exist in minimal digraphs
whose niche graph has as a component.
An arc in a digraph will be called functional if
it helps create, an edge in the niche graph, i.e., if
its tail has any other outarcs or its head any other
inarcs.
Theorem 5.4. If a digraph D has Km n (3 < m < n) as a
component of its niche graph, then D has no functional
graph arcs.
Proof: Let {ul, u2,..., um> be one bipartition of
Kjj, n and {v2, v2,..., vn} the other. If D has a func
tional graph arc, then either its head has an in
neighborhood of two graph vertices or its tail has an
outneighborhood of two graph vertices. Assume the
head has an inneighborhood of two graph vertices, and
call them ux and v^ (We can always consider the re
verse digraph if the tail has the neighborhood.) By
the proof of Theorem 5.3, only one configuration is
possible, namely^ that ^ and v1 prey on u2, u2 preys on
76
vlr and vl has no other predator and no other prey.
But then edge u3V2 is not possible, for v^s only
predator (u3) can not prey on u3 and v^'s only prey
(u2) can not be preyed upon by u3; either situation
creates a triangle.
This result shows that we may restrict our search
for digraphs with as a component of the niche
graph to those digraphs with no graph arcs. In other
words, the digraphs which illustrate the (n2) niche
number of will only have arcs from graph vertices
to extras and vice versa.
Theorem 5.5 For m even and 4 < m < n,
(m/2)n + 1 < n2(Kmn) < (m/2)(n + 1).
Proof: Since Kjj, n is trianglefree, every edge in
the graph must be created by an in or outneighbor
hood of precisely two arcs in the digraph. None of
the edges are created by graph arcs, so each of the mn
edges represents a pair of arcs from an extra (which
has no other outarcs) or to an extra (which has no
other inarcs)., Thus each extra can be matched with
at most two of the edges of n, and at least mn/2
extras are required in the digraph. However, since
the digraph is required to be acyclic, the extra that
creates the edge between the first element in one bi
77
partition of Kj^ and the last element of the other
must either precede that first element (if the edge is
a competition edge) or follow that last element (if
i
the edge is a commonenemy edge) In either case, the
extra cannot create a second edge of If the
extra precedes the first element of one bipartition,
i
no other element of that bipartition can prey on it,
since each vertex preys only on vertices following it.
A similar argument holds in the other case. Therefore
there are at least two extras which can create only
one edge between graph vertices, and thus there must
be at least mn/2 + 1 extras in the digraph, and that
means n2(Km n) >; (m/2)n + 1.
I
To establish the upper bound, consider the fol
lowing digraph oh m = n = (m/2) (n + 1) vertices, which
has as a component of its niche graph. Let the
vertices in the j bipartitions of be {u1# u2,...,
um} and {v2, v2,.!.., vn} and label the extras xij where
0 < i < n and l!< j < m/2. Now assign arcs on this
vertex set in the following fashion:
I
for i = 1,..., n and j = 1,..., m/2 draw arcs
from u to Xj ^ and from x, A to u
ID
mj+1'
for i = 1,.
.., n1 and j = 1,..., m/2 draw arcs
from vL to xLj and from xij to vi+1;
78
for j = I/..., m/2 draw arcs from x0j to u^j+i
and from x0j to v2.
Note how is generated by this digraph. Each
Xj^j, for 1 < i < n 1 and 1 < j < m/2, has exactly
two predators and Uj) and exactly two prey (vi+1
and um_j+1) That produces all edges except those
between v^ and the highersubscripted half of the u.L
and those between vn and the lowersubscripted half of
the nL. The arcs from x0j take care of the former and
the arcs to xnj take care of the latter. The digraph
has no cycles, for each arc from a graph vertex is to
an extra with an equal subscript (the first component
of the subscript for Vj^j arcs and the second
component for Uj'x^ arcs) and each arc from an extra
is to a graph vertex with a higher subscript. No
graph vertex is connected to an extra in the niche
graph, for graph vertices prey only on extras while
extras prey only on graph vertices: no common enemies
or common prey are possible. No graph vertex is con
nected to another in its bipartition, for each preys
on a set of extras with a different first element in
its subscript; the predators are similarly disjoint.
Thus we have constructed a digraph which has Km^n as a
component of its niche graph and uses (m/2)(n+1) extra
vertices, so ^(I^ ) has the desired upper bound.
79
For complete bipartite graphs with an odd number
of vertices in the smaller bipartition, the situation
is more complicated. The fact that m/2 is no longer
an integer makes obtaining a good upper bound more
difficult, and so far we have found no general bound
which is any better than rounding m/2 up to the next
integer and using Theorem 5.5. However, a cursory
consideration of the proof of the lower bound of
Theorem 5.5 reveals that it can be applied to these
graphs with only a slight modification.
i
Theorem 5.6 For m and n odd and 3 < m < n,
2(Vn) r*n/2l +1.
Proof: As : in Theorem 5.5, two edges in the com
plete bipartite! graph must be created by arcs to or
from extras which do not create other edges. But then
there must be at least (mn 2)/2 other extras, and
since mn 2 is odd, the minimum number of extras is
f (mn 2) /2~ + 2, or fmn/2" +1.
This lower bound is reached by at least one com
plete bipartite graph; the second niche number of K3^3
can be shown to I be 6 (= f9 / 2" + 1) by the digraph in
figure 5.4.
80
Figure 5.4 n2(K3,3) = 6
Many open questions remain in this area. No good
upper bound has been proved for n2 (1^ n) when m is odd,
but finding one should be possible using some of the
proof techniques of this chapter. The later theorems
of this chapter deal with the second niche number of
complete bipartite graphs, but similar results for the
first niche number are missing. We now know that
n1(K2,n) = n2(Km,n)* Nevertheless, the only upper
bound we know for n1(Km^n) is that given by Theorem
4.2, which is mn + 1. That leaves a large gap between
the upper bounds for the first and second niche number
of large symmetric complete bipartite graphs, and this
is a very promising place to look for a (as yet undis
covered) graph with different first and second niche
numbers. Of course, we have only established upper
and lower bound^ for the second niche number of
(and then only when m is even and 4 < m < n) not
found the exact answer. From studying various exam
81
pies, we tend to think it is the upper bound, but as
yet no proof exists. Also in the realm of open prob
lems is the question of the third niche number for
these graphs; no work has been done on this question.
I
i
82
I
6. Loop Niche Numbers and Cyclic Niche Numbers
In previous chapters we have discussed known
results about (original) niche numbers and proved some
new results concerning the niche numbers of classes of
unit interval graphs. The original definition of the
niche number of a graph was the minimum number of
additional isolated vertices whose disjoint union with
the graph was a niche graph. This definition was
inspired by the;analogous (and wellknown) definition
for the competition number of a graph. It proved to
be less efficacious for two reasons: some graphs can
not be turned into niche graphs in this fashion (their
niche number is infinity) and very few graphs (of
those whose niche number is known) have niche numbers
other than 0, 1, or m.
Seager's alternative definitions avoid these dif
I
ficulties, because with any of the new definitions,
all graphs have finite niche numbers, and there are
several classes] of graphs which have large niche
I
I
numbers. Seager's definitions also have the desirable
property that the analogous definitions for competi
tion numbers result in complete agreement with the
V
\
83
original (already widely studied and wellestablished)
i
competition number on all graphs. We investigated
i
some consequences of these new definitions in previous
chapters.
Other modifications of the competition number
definition .have been studied. One possibility that
!
immediately! suggests itself is to relax' the re
1
quirement that the digraph be acyclic. If, when
determining the competition number of some graph,
loops or cycles are allowed in the digraph whose
competition jgraph is the graph in question, clearly
the competition number can not increase. In fact, the
!
class of competition graphs expands substantially, as
the following theorems show.
Theorem 6.1 i(Dutton and Brigham[8]) A graph 6 with
n vertices is the competition graph of an arbitrary
i
i
digraph (loops allowed) if and only if G has an edge
covering of at most n cliques.
Theorem 6.2 (Roberts and Steif[35]) A graph G with
i
1
n vertices is jthe competition graph of an arbitrary
i
digraph without loops if and only if G is not K2 and
I
G has an edge covering of at most n cliques.
1
1
1
1
84
These, results show that allowing arbitrary di
graphs to generate competition graphs reduces the
problem of deciding whether a graph is a competition
graph to finding an edge clique cover with cardinality
at most the number of vertices in the graph. In this
chapter we will briefly examine related questions for
niche graphs: which graphs are the niche graphs of
digraphs with cycles allowed, and which are the niche
graphs of arbitrary digraphs with both loops and
cycles?
These questions do not have the encompassing
answers their cognates in competition graph theory
possess. It is:easy to show, for example, that many
classes of graphs still have infinite niche number.
Current results ;are fragmentary, but we show that unit
interval graphs are niche graphs of arbitrary digraphs
with loops (no other cycles are necessary), and sev
eral interesting avenues for further research exist.
We will say that a graph G is a cyclic niche
graph if G is the niche graph of an arbitrary loopless
digraph. We define the cyclic niche number of a graph
G, nc(G), to be the least number of vertices such that
the disjoint union of G with those vertices is a
cyclic niche graph. Furthermore, G is a loop niche
graph if it is the niche graph of an arbitrary digraph
85
with loops allowed; the loop niche number of G,
n2(G), is the minimum number of extra vertices such
that the disjoint union of G and those isolated
vertices is a loop niche graph. Note that the loop
niche number of any graph can not exceed the cyclic
niche number. As in the case of the original niche
number, if a graph can not be made into a cyclic or
loop niche graph by appending isolated vertices, its
cyclic or loop niche number is o.
The class of cyclic niche graphs is not as all
inclusive as the class of cyclic competition graphs;
we will first look at some graphs whose cyclic niche
number is infinity. The smallest such graph is the by
now familiar example K.^3. Consider the central vertex
(the one adjacent to each of the others). It is inci
dent with three edges. Since the graph is triangle
free, each edge!represents a commonenemy or common
prey pair of vertices in any digraph whose niche graph
is Klf3 (with, perhaps, some isolated vertices). Thus
the central vertex must either prey on at least two
other vertices, or be preyed on by at least two other
vertices. Iri either case those other vertices are
connected by an edge in the niche graph, which is
impossible. So K1j3 is not a cyclic niche graph, with
86
or without additional isolated vertices, and hence has
infinite cyclic niche number.
The argument above is essentially that of Cable,
Jones, Lundgren, and Seager[6] in their original
paper, used to prove that n0(Klf3) is infinite. Note
that the argument does not apply to loop niche graphs,
because the central vertex need not prey on two other
vertices; one of the vertices it preys on may be
itself. In fact, both K1>3 and K1>4 are loop niche
graphs, as the diagram below illustrates.
Figure 6.1 Klf3 and Klf4 Are Loop Niche Graphs
Not all stars are loop niche graphs; even K3 5
has an infinite loop niche number. This is a result
of the following theorem, and the proof is virtually
identical to the proof of a similar theorem in Cable
et al.[6].
87
Theorem 6.3 If G is a graph with largest clique size
m vertices, and maximum degree greater than 2m(m 1),
then nc(G) = (G) = .
Proof: Let v be a vertex of G with maximum de
gree at least 2m (m 1) +1. Assume G has a finite
loop niche number. Since the largest clique of G has
m vertices, at  most m vertices can attack (or be
attacked by) any one vertex. If m vertices attack v,
each can attack at most (m 1) other vertices of G.
Then at most m(m 1) vertices can be adjacent to v by
commonenemy edges. Similarly, at most m(m  1)
vertices can be adjacent to v by competition edges.
Thus at most 2m(m 1) vertices can be adjacent to v;
since the degree of v is greater than that, G can not
be a graph with finite loop niche number. Since every
graph with a finite cyclic niche number has a finite
loop niche number as well, G must have infinite cyclic
niche number.
This theorem demonstrates that many graphs have
infinite cyclic niche numbers. However, some graphs
do have cyclic niche number less than their original
niche number. The following theorem gives three cases
1
in which graphs are cyclic niche graphs, but not niche
graphs for any of the previously considered defini
!
tions.. The first result is not surprising. The
88
second result, on cycles, is noted because the cycles
C4, C5, and C6 provided the first graphs with niche
number 2. The FishburnGehrlein graphs to which the
theorem refers are the graphs which Peter Fishburn and
Bill Gehrlein constructed showing there are graphs
with arbitrarily large finite niche numbers[11]. Thus
one interesting conseguence of the theorem is that the
difference between the original niche number and the
cyclic niche number can be made as large as desired by
selecting the right graph.
Theorem 6.4 For graphs with three or more vertices,
i) if n0(G) = 1, then nc(G) =0;
ii) if G is a cycle, then nc(G) =0;
iii) if G is one of the FishburnGehrlein graphs,
then nc(G) = 0.
Proof: For part i), assume that in a digraph D
with its niche graph consisting of G and one isolated
vertex, the extra is a prey. (Of course, we can re
verse all the arcs in the digraph to make this so.)
Then, if all graph vertices prey on the extra (so that
G is the complete graph), replace the digraph with the
complete symmetric digraph on the vertices of G, and
the niche graph of this digraph is G. Otherwise,
since n0(G) is finite, a topological ordering of the
89
vertices of D is guaranteed to exist, in which each
vertex preys only on vertices succeeding it. Take the
first vertex v which doesn't prey on the extra, and
let all the extra's predators prey on v. Note that v
had no previous predators, since every vertex preced
ing it in the topological ordering preyed on the
extra, and therefore had no other prey. Eliminate the
extra, and D now has G as its niche graph. The in
neighborhood of v now creates the edges previously
created by the inneighborhood of the extra, and since
v had no other predators (and the predators of v no
other prey), no new edges are created.
To show that the cycle Cn is a cyclic niche
graph, create a digraph on the vertices of Cn by
having arcs from to vi+1 and vi+2, modulo n.
The proof that FishburnGehrlein graphs are cyc
lic niche graphs follows from the construction of the
graphs, so we first describe that construction. Each
graph (plus isolated vertices) in the family is the
niche graph of a digraph which consists of the verti
ces of G plus an even number of extras. Half the ex
tras are predators, half prey. Half the graph verti
ces are preyed on by an extra; the other half prey on
an extra. The graph vertices that prey on an extra
are preyed on only by other graph vertices, none of
90
which, of course, prey on any extra. We.will modify
this digraph. First match each prey extra with a
distinct predator extra. Then redirect the arcs that
attacked each prey extra to its associated predator
extra, and delete the prey extras. This leaves a di
graph (with cycles) in which each extra is both preda
tor and prey. Following a construction of Bowser and
Cable[4], we now proceed by choosing one predator and
one prey for each remaining extra. Have the chosen
predator prey on all the extra's prey, and have all
the extra's predators prey on the chosen prey. Then
eliminate the extras. We claim this new digraph D has
G as its niche graph. Note that all arcs which for
merly were directed from a graph vertex to an extra
are now directed from the graph vertex to another
graph vertex which had no previous predators except
one of the predator extras. There are no loops,
because no vertex preyed on by an extra attacked an
extra. Each inneighborhood of an extra (which
created a clique in the niche graph) is now an in
neighborhood of a graph vertex (whose only previous
predator was an extra); each outneighborhood of an
extra is now the outneighborhood of a graph vertex
(which formerly had no prey except an extra). An
example is illustrated in figure 6.2.
91

PAGE 1
NICHE GRAPHS AND NICHE NUMBERS: NEW RESULTS AND ALTERNATIVE DEFINITIONS by Charles A. Anderson B.A., University of Colorado at Boulder, 1969 M.S., University of Colorado at Denver, 1986 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 1992
PAGE 2
by Charles A. Anderson All rights reserved.
PAGE 3
This thesis for the Doctor of Philosophy degree by Charles A. Anderson has been approved for the Department of Mathematics by I
PAGE 4
Anderson, Charles A. (Ph.D., Applied Mathematics) Niche Graphs and Niche Numbers: New Results and Alternative Definitions Thesis directed by Professor J. Richard Lundgren ABSTRACT The niche graph of a digraph has the same vertex set as the digraph and an edge between two vertices if and only if, in the digraph, those two vertices both have arcs to or from a common third vertex. A graph that is the niche graph of an acyclic digraph is called a niche graph; the niche number of a graph is the minimum number of isolated vertices whose disjoint union with the graph is a niche graph. Several classes of graphs have been identified as niche graphs; this thesis identifies several more, all of which are types of unit interval graphs. As a consequence of the methods of a proof in this thesis, a new count of the number of labeled unit interval graphs on n vertices is obtained. The niche number of many classes of graphs is infinite; building upon a suggestion by suzanne Seager, we look at several alternative definitions of the niche number. Each of these makes the niche iv
PAGE 5
number of every graph finite by relaxing the requirement that additional vertices be isolated. The niche numbers provided by these definitions are investigated; for graphs with finite original niche number there are few changes. The major results of this thesis provide bounds for these new niche numbers in terms of the clique cover number of a grapl). and develop tighter (and in some cases exact) bounds for the complete bipartite graphs. The final section of the thesis, suggested by similar results in competition graph theory, is an investigation of how relaxing the acyclic requirement for the digraph expands the class of niche graphs. We show that the graphs with arbitrarily large finite (original) niche numbers, discovered by Fishburn and Gehrlein, become niche graphs if cyclic digraphs are allowed, and that unit interval graphs are niche graphs of digraphs with loops allowed. We provide several other,partial results. This abstract accurately represents the content of the candidate's thesis. S.LyHt=U_ v
PAGE 6
DEDICATION To my wife and best friend, Pat Carney, whose love, understanding, and encouragement made it possible to complete this thesis.
PAGE 7
ACKNOWLEDGEMENTS I am grateful to many people and organizations that helped me during the years of graduate school. Rich Lundgren first introduced me to graph theory (and to niche graphs in particular) and gave me a chance to coauthor several papers. His positive outlook while this thesis gradually took shape is much appreciated. Kathy Fraughnaugh offered valuable assistance on niche graphs, and also, with Jenny Ryan, helped me learn about tabu search and genetic algorithms. Jenny Ryan and Harvey Greenberg guided me through the elements of mathematical programming. Bill Wolfe showed me many aspects of artificial intelligence and computer science, and our discussions led to two papers on neural networks in which I was a minor coauthor. My thanks also go to my other professors at the University of Colorado at Denver, and to the university itself, for making it possible for fulltime workers to pursue further studies. ble. Not all institutions are as flexiI received, and gratefully acknowledge, financial support from many sources. Jefferson County Public Schools awarded me two sabbaticals at half salary, vii
PAGE 8
allowing me to complete much of my coursework. The Colorado Commission on Higher Education helped to defray tuition several semesters. The Colorado Institute for Artificial Intelligence (now the Colorado Advanced Software Institute) and US WEST provided a research assistantship. The National Science Foundation and the Rocky Mountain Mathematics Consortium funded several summer institutes at the University of Wyoming. The Mathematics Department of UCD and the Office of Naval Research helped with travel costs to several conferences. I thank these institutions and any others I may inadvertently not have mentioned. viii
PAGE 9
CONTENTS 1. Introduction .................................... 1 1.1 Overview of Thesis Results ............... 4 2. Definitions and Literature Review .............. 8 2.1 Basic Definitions ....................... 8 2. 2 Competition Graphs ...................... 13 2.3 Niche Graphs and Niche Numbers .......... 18 3. Niche Graphs and Unit Interval Graphs ......... 25 3.1 Types of Unit Interval Graphs That Are Niche Graphs ........................ 27 3.2 Are All Incomplete Unit Interval Graphs Niche Graphs? .................... 35 3.3 The Number of Possible Clique Structures for Labeled Unit Interval Graphs ........ 44 4. Alternative Definitions for the Niche Number and Some of Their Consequences ......... 50 4.1 Alternatives for the Niche Number Definition .............................. 52 4.2 Basic Properties of New Niche Numbers ... 58 4. 3 summary ................................. 64 5. Alternative Niche Numbers for Complete Bipartite Graphs .............................. 65 5.1 The Niche Numbers of Complete Bipartite Graphs with Both Bipartitions Having More Than Two Vertices .................. 7 5 6. Loop Niche Numbers and Cyclic Niche Numbers ... 83 7. Bibliography .................................. 99 ix
PAGE 10
1. Introduction The primary topic of this paper is the investigation of niche numbers of graphs. This first section of the thesis is intended as an overview of the major concepts and results contained in the rest of the thesis. Some knowledge of graph theory will be assumed. Precise statements of definitions and theorems and relevant background material will be found in chapter two. Niche graphs (and competition graphs) have roots in ecology, where the study of ecosystems led to the construction of acyclic digraphs depicting predatorprey relationships among various species. If species are represented by vertices, an arc from one vertex to a second vertex indicates that the species represented by the first vertex preys on the species represented by the second. Such a digraph is called a food web. One vertex is said to prey on another (and is called a predator) if there is an arc from the first to the second; the second vertex in such a situation is called a prey. Note that a vertex may be both predator and prey. 1
PAGE 11
Every digraph has a competition graph and a niche graph associated with it; they use the same vertex set as the digraph. In the competition graph of a digraph, two vertices are connected by an edge if and only if those vertices both prey on a common third vertex. In the niche graph of the digraph, two vertices are connected by an edge if either they have a common prey, as in the competition graph, or they have a common predator. While the topic of this thesis is niche graphs, it will help to first discuss some of the known facts concerning competition graphs. Many of the results and open problems about niche graphs are analogous to, and were first investigated because of, properties of competition graphs. Since the food webs which led to the concept of competition graphs are almost all acyclic, we will call a graph a competition graph only if it is the competition graph of an acyclic digraph. An obvious question to ask is: which graphs are competition graphs? It is easily shown that, while no connected graph is a competition graph, every graph is a component (or set of components) of a competition graph, all of whose other components are isolated vertices (i.e., they have no edges connecting them to any other vertex). In other words, every graph can be 2 b<<
PAGE 12
made into the competition graph of an acyclic digraph by adding enough extra isolated vertices. A natural followup question is, how many extra isolated vertices must be added to make an arbitrary graph into a competition graph? For any graph, we will call this minimum number of isolated vertices its competition number. Thus, a graph which is already a competition graph has competition number zero; a graph (such as, we will see, a complete graph on two or more vertices) which requires only one additional isolated vertex to become a competition graph has competition number one, and so on. Thus competition graphs are always disconnected, and the question of how close (in some sense) any graph is to being a competition graph can be quantified by its competition number. These characteristics of competition graphs and competition numbers made them a popular subject of research in the nineteenseventies and nineteeneighties. Even though the problem of determining the competition number of a graph was shown to be NPcomplete in 1982 [ 28], the competition numbers of many different classes of graphs were established. Applications in areas other than ecology, such as assignment of radio frequencies in areas crowded with many transmitters, were found. 3
PAGE 13
.:L Niche graphs, when first investigated, proved not to have the same appealing characteristics that competition graphs possessed. Those graphs which are niche graphs of acyclic digraphs do not have an easily identifiable characteristic such as always possessing an isolated vertex. The niche number of a graph can be defined similarly to the competition number, but the definition raises some problems. Some relatively simple graphs (such as stars with three or more rays) cannot be turned into niche graphs by adding isolated vertices; they are said to have infinite niche number. Finding niche numbers for classes of graphs seems to be more difficult than finding competition numbers; not many are currently known. An additional difficulty is that, until 1990, the only niche numbers known to exist were zero, one, two, and infinity. 1.1 overview of Thesis Results This thesis will present some new results about niche numbers of graphs. The second chapter will provide some basic definitions from graph theory and review the existing literature regarding competition graphs, competition numbers, niche graphs, and niche numbers. This background will emphasize the relationship between the theories of competition graphs and 4
PAGE 14
niche graphs. In the third chapter, research results involving unit interval graphs will be presented. While we have not proved that all unit interval graphs are niche graphs, many subclasses of unit interval graphs are shown to be niche graphs. At the end of the chapter, a method of counting the number of unit interval graphs which are labeled to make all their maximal cliques consist of consecutive vertices is introduced. Surprisingly, the number of such labeled graphs turns out to be related to the Catalan numbers, a sequence which turns up in many unexpected places in combinatorics. The fourth chapter will discuss alternative definitions for the niche number of a graph and some of the ramifications of adopting one of these alternative definitions. One reason for looking at different definitions is that niche numbers lack the diversity of competition numbers. All graphs have finite competition numbers; many graphs have an infinite niche number. Graphs with competition numbers of any desired size are easily found; the overwhelming majority of graphs so far investigated have niche numbers of zero, one, or infinity. By looking at other defini tions, perhaps a more useful niche number, one which differentiates among more classes of graphs, may be 5
PAGE 15
found. An important property of the new definitions for niche numbers is that they do not conflict with the wellestablished definition of competition number, that is, if the competition number were defined analogously to the niche number, every graph would still have the same competition number. The new niche number definitions simply allow the extra vertices added to the graph to be connected in different ways, instead of isolated. Chapter five concentrates on the new niche numbers of complete bipartite graphs. This class of graphs has original niche number infinity; the smallest graph with infinite niche number is a member. Several results show that the alternative niche numbers of these graphs take on all positive integer values. For some graphs, we find the exact niche numbers; for others, restrictive upper and lower bounds are proved. In the final chapter, we look at another modification of the definition of niche number. The original context in which competition graphs were considered was ecology; most of the food webs studied were acyclic. In the early eighties the requirement of acyclicity was relaxed, and it was discovered that virtually every graph (with the exception of those with more maximal cliques than vertices) is the compe6
PAGE 16
tition graph of an arbitrary digraph. We look at the analogous problems for niche graphs, and the answers are more complicated. Some graphs still have infinite niche number, while many of those with finite original niche number, including a class whose niche numbers grow arbitrarily large, turn out to be niche graphs of arbitrary digraphs. 7
PAGE 17
2. Definitions and Literature Review 2.1 Basic Definitions A graph G = G(V, E) is a finite set of vertices V together with a set of edges E which is a subset of the set of twoelement subsets of V. We think of the vertices as points in space or on a plane, and the edges as line segments or curves connecting pairs of those points. Vertices are generally written as lowercase letters. If u and v are vertices of G, uv (or vu) represents the edge connecting u and v, and u and v are endpoints of uv. An edge and its endpoint are incident. If G has n vertices, we will frequently label them {v1 v 2 ... vn}, and edges will be written in the form vivj. Two vertices are adjacent if there is an edge between them; two edges are adjacent if they share a common vertex. If two edges are adjacent, we also say that they intersect. The degree of a vertex is the number of edges incident with it. The degree of a graph is the maximum of the degrees of its vertices. If a vertex is not incident to any edge 8 ....
PAGE 18
(and thus not adjacent to any vertex), it is an isolated vertex. Two vertices u and v are connected if there is a sequence v 1 v 2 ... vn of vertices such that vi and vi+l are adjacent for each 1 i n1, u is adjacent to v1 and vn is adjacent to v. If the vi (and u and v) are all distinct, the sequence of vertices. and their connecting edges is a path. If we have u = v, and i > 0, and the vi are all distinct, the sequence of vertices and their connecting edges is a cycle. The graph which consists of a path on n vertices will be denoted by Pni the cycle on n vertices by en. A graph G is connected if all pairs of vertices in it are connected. Otherwise G is disconnected. A connected graph without any cycles is a tree. A subgraph of G is a graph with all its vertices and edges in G; an induced subgraph of G is a graph G'(V', E') with all its vertices in G and its edges exactly the edges of G connecting vertices in V'. A maximal connected subgraph of G is a component of G. A graph whose vertex set can be partitioned into two sets such that every edge of the graph has one endpoint in each set is a bipartite graph. In a bipartite graph, all cycles have an even number of vertices and edges. A complete graph is one in which 9
PAGE 19
every pair of vertices is joined by an edge. A complete bipartite graph is a bipartite graph in which every vertex in one bipartition is adjacent to every vertex in the other. The complete graph on n vertices is denoted by Kn; the complete bipartite graph with a bipartition into m and n vertices by Km,n See figure 2.1 for examples. A complete subgraph of a graph.G is called a clique of G; we will frequently be interested in the maximal cliques of a graph. A vertex which is contained in only one maximal clique is called a simplicial vertex. Any set of cliques {C1 c2 ... Cm} containing all the edges of G is called a clique cover of G. The minimum number of cliques required to cover the edges of G is called the edge clique cover number of G, and is written 9e(G). Given any family of sets, the intersection graph of that family has a vertex corresponding to each set and an edge between two vertices if and only if the 10
PAGE 20
sets corresponding to those vertices intersect. If we restrict the sets to intervals on the real line, we can construct a graph from this set by assigning a vertex to each interval and then drawing an edge between two vertices if and only if their intervals overlap. Any graph that can be so constructed is called an interval graph. A graph that is the intersection graph of a set of intervals of identical length is called a unit interval graph. This class of graphs is quite important in the theory of competition graphs and niche graphs. A comprehensive reference is the book by Golumbic[13]. A directed graph, or digraph, D = D(V, A) is a set of vertices together with a set of arcs which are ordered pairs of vertices. In a digraph we think of the arcs as lines or curves with directional arrows connecting two vertices. As with graphs, vertices will be denoted by lowercase letters, and the arc connecting vertex x to vertex y by xy. Note that xy and yx are different arcs. If the context does not make absolutely clear whether we are referring to an arc or an edge, we will specify "arc xy" or "edge xy." If xy is an arc, then x is its tail and y is its head; xy from x and toy. Furthermore, xy is an outarc of x and an inarc of y. 11
PAGE 21
If x and y are two vertices in a digraph D, then y is reachable from x if there is a sequence of vertices v1 v2 vn such that vivi+l is an arc for all 1 s i S n1, and xvi and vny are also arcs. If all the vertices are distinct, the sequence of vertices (and the arcs connecting each to the next) is called a path; if x = y but all other vertices are distinct, the sequence (and its arcs) is called a cycle. In a digraph, as opposed to a graph, cycles of length two are permitted (for example, arcs xy and yx make a twocycle). If an arc with the same head and tail, such as xx, is permitted, it is called a loop. In general, digraphs will be considered to be loopless unless otherwise specified. We will say that x and y are joined if there is a sequence of vertices v 1 v 2 ... vn such that either vivi+l or vi+lvi is an arc, as are xvi or vix and VnY or yvn. A digraph is strongly connected if for every pair of vertices x andy, x is reachable from y and y is reachable from x. A digraph is weakly connected if every pair of vertices is joined. For any digraph D, its reverse digraph is the digraph on the same vertex set with an arc yx for each arc xy of D. There is no special name for an acyclic digraph.
PAGE 22
For other terms in the theory of graphs and digraphs, one of the many textbooks on graph theory should be consulted, such as Roberts[31], Bondy and Murty[3], or Harary, Norman, and Cartwright[18]. 2.2 Competition Graphs Niche graphs, the subject of this thesis, are a natural extension of competition graphs. Since competition graphs have been the subject of mathematical investigation for a much longer period of time than have niche graphs, there is a correspondingly larger body of literature concerning them. Niche graphs are similar to competition graphs, and many of the early results involving niche graphs have been discovered by analogy with known results for competition graphs. This section will define competition graphs and review some of the important properties they possess. Given a digraph D, the competition graph of D is the graph with vertices the same as those of D, and an edge between two vertices x and y if and only if there is a third vertex z such that xz and yz are arcs in D. Competition graphs were first studied in the context of food webs in an ecosystem, and that context has had a strong influence on the vocabulary of competition graphs. When representing a food web as a di13 
PAGE 23
graph, species (or related groups of species) become vertices, and there is an arc from one vertex to another whenever the species of the first vertex eats the species represented by the second. If xz is an arc, then x is a predator and z is a prey; we say that x preys on z. If xz and yz are both arcs, then x and y compete for z. Figure 2.2 A Digraph and Its Competition Graph Since most food webs are acyclic, researchers concentrated on those graphs which were competition. graphs of acyclic digraphs. (Also, Dutton and Brigham[8] and Roberts and Steif[35] settled the question of which graphs were competition graphs of arbitrary digraphs; every graph with.an edge clique cover of at most n cliques is the competition graph of some arbitrary digraph with loops, and K 2 is the only additional exception even if loops are not allowed.) 14
PAGE 24
We will say that a graph G is a competition graph if it is the competition graph of an acyclic digraph. Now the question of which graphs are competition graphs becomes more interesting. Characterizations were obtained by Lundgren and Maybee[27] and Dutton and Brigham[8]. This terminology is somewhat confusing but wellestablished. There is a difference between a graph being the competition graph of a digraph and a graph being a competition graph. What it means is that if we are considering a particular digraph D, we can talk about its competition graph C(D), which is uniquely determined by the definition. If, on the other hand, we are talking about a graph G without reference to a particular digraph, we will say G is a competition graph only if there is some acyclic digraph which has G as its competition graph. Early researchers noted that almost all of the competition graphs they studied were interval graphs. While it is possible to construct competition graphs which are not interval graphs, most competition graphs arising in practice have been interval, so it is natural to ask which acyclic digraphs have interval competition graphs. This remains an active area of research[l9, 43]; there have been recent investigations 15
PAGE 25
of which arbitrary digraphs and symmetric digraphs have interval competition graphs as well[29]. It is easy to see that all competition graphs are disconnected; since the digraph from which the competition graph arises is acyclic by definition, it must contain a vertex with no outarcs. That vertex cannot compete with any other vertex, and thus must be .isolated in the competition graph. However, Roberts[32] showed that all graphs can be turned into competition graphs by adding enough isolated vertices. The idea of his proof is, for each edge of the graph, add an extra vertex to the digraph. Then draw arcs from the endpoints of each edge to the extra vertex for that edge. Roberts then went on to define the competition number k(G) of a graph G as the least number of vertices such that G together with that number of isolated vertices is a competition graph. From the remarks above we can see that the competition number of a connected graph G is between 1 and JE(G) I. Opsut[28] showed that the computation of the competition number of an arbitrary graph is an NP complete problem. However, the competition number is known for many classes of graphs. For example, the competition number of any connected interval graph is 1, of any cycle on at least 4 vertices is 2, and of 16
PAGE 26
any connected trianglefree graph on n vertices and e edges is e n + 2[32]. Mathematicians have investigated several concepts closely related to competition graphs and competition numbers. Scott[37] looked at what she called the competitioncommon enemy graph of a digraph, in which there is an edge between two vertices x and y in the graph when, in the digraph, there are two vertices z and w such that xz and yz are arcs and wx and wy are arcs. (w is called a common enemy of x andy.) She also defined the double competition number of a graph and showed it was at most one more than the competition number. Preliminary investigations failed to find any graphs with large double competition numbers, but Jones, Lundgren, Roberts, and Seager[23] constructed a series of examples to show that the double competition number could be made as large as desired. Isaak, Kim, McKee, McMorris, and Roberts[21] have investigated the pcompetition number of graphs, which arises from the idea of a pcompetition graph of a digraph, where two vertices are connected by an edge only if they compete for at least p different prey. Anderson, Jones, Lundgren, and McKee[l] investigated the concept of competition multigraphs and the multicompetition number, where each competition in the 17
PAGE 27
digraph resulted in an edge in the multigraph, so that multiple edges could occur. These ideas are all discussed more comprehensively in survey articles by Lundgren[26] and Kim[25]. 2.3 Niche Graphs and Niche Numbers The niche graph of a digraph D is a graph .with the same vertices as D and an edge xy if and only if there is a third vertex z such that xz and yz are arcs in D, or zx and zy are arcs in D. If a graph is the niche graph of an acyclic digraph, then we will call it a niche graph. If an edge xy in the niche graph of a digraph arises from competition between x and y (that is, if xz and yz are arcs to some third vertex z) we will call the edge a competition edge; if the edge arises from a common enemy of x and y (that is, zx and zy are arcs in the digraph from some vertex z), we will call the edge a commonenemy edge. It is possible for an edge in a niche graph to be both a competition and a commonenemy edge. From these definitions it is clear that each inneighborhood of the digraph is a clique (not necessarily maximal) of graph. Similarly, competition edges in the niche each outneighborhood of the digraph is a clique of commonenemy edges. 18 Greenberg,
PAGE 28
Lundgren, and Maybee[14], in a different context, also considered inand outneighborhoods, which they called common predecessors and common successors. Their work was matrixoriented and the existence of common successors or common predecessors was important to the inversion of a signed graph and a digraph. The paper, last in a series of five, was directed toward artificially intelligent modeling of largescale economic models. Following the analogy with competition graphs, the niche number of a graph G, n(G), is the minimum number of isolated vertices whose disjoint union with G forms a niche graph. A digraph which has as its niche graph the disjoint union of G and n(G) isolated vertices will be called a generating digraph for G. While these definitions show clearly that niche graphs are a variant of" competition graphs, investigation quickly reveals that their properties are quite different. v6 Figure 2.3 v6 A Digraph and Its Niche Graph 19
PAGE 29
The paper that introduced niche graphs, by Cable, Jones, Lundgren, and Seager[6], appeared in 1989. They immediately established two rather surprising facts about niche numbers: the niche number of a connected graph could be zero, and it could be infinite. (An infinite niche number means that the graph in question cannot be made into a niche graph by the addition of any number of isolated vertices.) Neither of these situations can occur with competition numbers. Cable, Jones, Lundgren, and Seager found finite niche numbers for several classes of graphs, and also succeeded in showing that a nova, a graph obtained by replacing the edges of a star (K1,n) with various cliques on two or more vertices, has infinite niche number. Sakai[36] proved that the complete bipartite graph Km,n with min{m,n} 2 3, has infinite niche number as well. Bowser and Cable[4] added wheels (one central vertex adjacent to each vertex of a cycle) with at least nine vertices to the list of graphs with infinite niche number; the niche number of wheels with five through eight vertices they showed to be zero. Since these are, with a few exceptions, the only families of graphs with known niche numbers, we 20
PAGE 30
summarize these results in the following theorem. (Wm is the wheel with m+l vertices.) Theorem 2 .1. n (Km) = 1 for m 2 n (Pml = 0 for m 3 n(Cm) = 0 for m 9 and m = 7 n(C8 ) = 1 and n(C4 ) = n (C5 ) = n(C6 ) = 2. n(Kl,ml = 00 for m 3 n (Km,n> = 00 for min{m,n} 3 n(Wml = 00 for m 8. I Seager[39, 40] also achieved several results involving trees. Theorem 2.2, to be given below, guarantees that no tree of maximum degree 5 or more is a niche graph. Seager has shown that all trees of maximum degree 3 or less are niche graphs with the exception of K 2 and K 1 3 She has several partial results on trees with maximum degree 4, but in the general case the niche numbers of such trees are still unknown. The existence of so many classes of graphs with infinite niche number makes characterizing the graphs which have a finite niche number, or a niche number of zero, desirable. known, however. No useful characterization is yet Sakai[36] showed that no forbidden 21
PAGE 31
subgraph characterization is possible by discovering this theorem: Theorem 2.2. The disjoint union of a graph and its line graph is a niche graph. I Sakai proved this by construction; she also provided a method of starting with any graph G and .constructing a digraph whose niche graph is connected and has G as an induced subgraph. The authors of the original niche graph paper found a sufficient (but not necessary) condition to cause a graph G to have an infinite niche number[6]: Theorem 2.3. If G is Km+1free and n(G) < then G has maximum degree at most 2m(ml). I They also established an upper bound on finite niche numbers for a graph G of IV(G) I; Bowser and Cable[4] later refined this to twothirds of IV(G) I. This bound is rarely approached; substantial improvement may be possible. In practice, all of the graphs that were first investigated and found to have finite niche numbers had niche numbers of zero, one, or two. This naturally suggested the question of whether there were graphs with larger finite niche numbers. Bowser (personal communication) wrote a computer program 22
PAGE 32
which established that only five nonisomorphic graphs with fewer than seven vertices had niche number two, and none had a larger finite niche number. The existence of graphs with large finite niche numbers was one of the major open questions in niche graphs until 1991. The question was settled by Fishburn and Gehrlein[11], who produced a graph on 11 vertices with niche number four, and a graph on 14 vertices with niche number three. They also confirmed Bowser's computer results (including the fact that there are 21 connected graphs on seven vertices with niche number two, and none with higher niche number). While this answered the question of whether there were graphs with finite niche number greater than two, Fishburn and Gehrlein accomplished even more. They produced an infinite family of graphs which had members with arbitrarily large niche numbers. The actual niche numbers of these graphs are not known; however, they are bounded below and are finite. In a recent paper[12], Fishburn and Gehrlein extended their computer search to graphs with eight vertices and discovered the two smallest graphs with niche number three. On eight vertices there are 11,302 unlabeled graphs without isolated vertices. Of these 9,560 are niche graphs; 23
PAGE 33
565 have niche number 1; 17 4 have niche number 2; 1,001 have infinite niche number, and only two have niche number three. The question of the order of the smallest graph with niche number four is still open, though it must be 9, 10, or 11. This summary of known facts about niche graphs and niche numbers indicates that there are many problems which have not been resolved. New results in this thesis fall into three major categories. Many types of unit interval graphs are proved to be niche graphs in the next chapter. Later chapters explore alternative definitions of the niche number of a graph which (by relaxing the extraverticesisolated requirement) give every graph a finite niche number. Using these definitions, new niche numbers are established for several classes of graphs, and bounds on the new niche numbers of complete bipartite graphs are found. A different relaxation (allowing cycles or loops) gives rise to the cyclic and loop niche numbers; some preliminary results regarding them are presented. In addition, a serendipitous observation made while proving a sequence of theorems provides a new way of labeling unit interval graphs, and counting the number of different labeled graphs reveals a wellknown combinatorial formula in an unexpected context. 24
PAGE 34
3. NICHE GRAPHS AND UNIT INTERVAL GRAPHS unit interval graphs are the intersection graphs of intervals of equal length on the real line. Each interval is represented by a vertex, and two vertices are connected by an edge if and only if their intervals overlap. Unit interval graphs have several wellknown properties: Theorem 3.1. (Roberts[33]) i) A graph G is a unit interval graph if and only if there is an ordering of the vertices of G, {v1,v2 ,v0 } 1 such that if vi and vj are adjacent and i
PAGE 35
iii) An interval graph is unit interval if and only if K 1 3 is not an induced subgraph. I Although Roberts[32] proved that the competition number of every interval graph (without an isolated vertex) is one, the situation for niche numbers of interval graphs is not as simple. Complete graphs have niche number one; paths (on at least three vertices) have niche number zero; stars (with at least three rays) have infinite niche number. are interval graphs. Nevertheless, all Since the problem of determining niche numbers of interval graphs appears to be quite difficult, we will investigate a smaller set of graphs. Since unit interval graphs are precisely those interval graphs which do not have stars as induced subgraphs (and thus remove from consideration a large class of graphs with infinite niche number), they provide a promising starting point. We note again that complete graphs are not niche graphs, but have niche number one. Our investigation will focus on incomplete unit interval graphs and attempt to determine which of these graphs are also niche graphs. 26
PAGE 36
3.1 Types of Unit Interval Graphs That Are Niche Graphs Our first result allows us to assume, for the remainder of this chapter, that the unit interval graphs we consider are connected: Theorem 3.2. If each component of a disconnected unit interval graph G is either a niche graph or a complete graph, then G is a niche graph. Proof: We will construct a digraph on V(G) that has G for its niche graph. By Theorem 3.1, the vertices of G can be ordered so that every maximal clique consists of consecutively numbered vertices; such an ordering induces an ordering of the components. The incomplete components are niche graphs by hypothesis, so on the vertices of each such component there is an acyclic digraph whose niche graph is that component. Specifically, among the vertices of every incomplete component are a vertex with no inarcs and a vertex with no outarcs. To specify the arcs of the digraph on V(G) that will have G as its niche graph, begin with the arcs of each of these digraphs on the incomplete components. Then, if there are any complete components of G which are not the last component of G, choose a vertex in the next component which has no in27
PAGE 37
arcs and add arcs from each vertex of the complete component to the chosen vertex. Finally, if the last component of G is complete, choose a vertex with no outarcs (if there is one) in the preceding component and add arcs from it to each vertex of the last component. If there is no such vertex, the preceding component of G is also complete; choose any vertex in it and add arcs from it to each vertex of the last component. We claim the digraph described is acyclic and has G as its niche graph. That it is acyclic is clear: the individual digraphs for the incomplete components are acyclic by hypothesis, and all other arcs go only from one component to a succeeding component, so there can be no cycles within components nor between components. The niche graph of the digraph, again by hypothesis, contains all the edges of the incomplete components. It also contains the edges of each complete component, for (except possibly for the last component) the vertices of each complete component have a common prey. Since this common prey has no other predators, and since the predators of it have no other prey, no additional edges are induced. If the final component of G is complete, some vertex of the preceding component preys on each vertex, so all the 28
PAGE 38
edges of the final component are induced. If the preceding component was not complete, the predator vertex had no other prey, and no vertex of the final component has any other predator, so no extraneous edges can be induced. If the preceding component was complete, some vertex of the last component is preyed upon by all the vertices of the preceding component, but since the predator vertex for the final component is already adjacent to every other vertex of the preceding component, again no additional edges are induced. Note that the above proof and construction work even if the unit interval graph consists entirely of complete components. In the rest of this chapter, we will assume, unless otherwise specified, that the unit interval graphs considered are incomplete and connected. We will also assume that when we refer to the vertices of a unit interval graph Gas {v1 v 2 ... vn} and its maximal cliques as {C1 c 2 ... Cm} the vertices and cliques are ordered as indicated in Theorem 3.1, so that maximal cliques consist of consecutively numbered vertices, and each maximal clique has a first (lowestnumbered) and a last (highestnumbered) vertex. We now show that unit interval graphs with certain properties are niche graphs. 29
PAGE 39
Theorem 3.3. A unit interval graph G with exactly two maximal cliques is a niche graph. Proof: Let the unit interval graph G have vertices V = {v1 v 2 ... vn} and maximal cliques c 1 and c 2 Let vi be the first vertex of c 2 and vj the last vertex of c1 Construct a digraph on V as follows: draw arcs from each vertex of c 1 to vj+l' and additional arcs from vil to each vertex of c 2 Clearly the niche graph of this digraph is G: the vertices of c 1 have a common prey, so are all adjacent to each other; the vertices of c2 have a common enemy; no other vertex has either an inneighborhood or an outneighborhood of more than one vertex, so there are no more adjacencies in the niche graph. I Theorem 3 4 A unit interval graph G with exactly three maximal cliques is a niche graph. Proof: As before, let the vertices of G be V = {v1 v 2 ... vn}; let the maximal cliques be {C1 c 2 We consider two cases depending on whether the intersection of C 1 and c3 is or is not empty. Case 1: c 1nc3 = 0. Define an acyclic digraph on Vas follows: draw arcs from the vertices of c 1c2 to the vertices of c 2 and from c 1nc2 to the vertices of c3. This digraph is clearly acyclic, and has G as its 30
PAGE 40
niche graph. since c3 and c2 are not disjoint (remember we are dealing with connected graphs), all the vertices of c1 have a common prey. Thus c1 is a competition clique, and both c2 and c3 are commonenemy cliques. No other edges can occur in the niche graph. All arcs originate in c1 so no competition edges can have a vertex outside of c1 as an endpoint. All arcs end in c2ve3 so no commonenemy edge can have an endpoint in c1c2 ; furthermore, no vertex in c2c3 can be adjacent to a vertex of c3c2 for their predators are disjoint. Case 2: c1 and C 3 are not disjoint. We will partition v into five subsets: V 1 = c 1c2 V 2 = c 2c3 V 3 = c1nc2nc3 v 4 = c2c1 and v 5 = c 3c2 Note that this is a partition; every element of V is in one of these subsets, no subset is empty, and these subsets are mutually disjoint. Also note that c 1 = V 1 vV 2vV3 c 2 V 2 vV 3vV4 and c 3 = V 3vV4vv5 Construct a digraph on V as follows: each vertex in c 1 preys on each vertex in V 4 each vertex in c 2 preys on each vertex in v 5 and each vertex in V 2 preys on each vertex in V 3 We claim that the niche graph of this digraph is G. Clearly c 1 is a competition clique, as is c 2 Since v 2 has at least one vertex in both c 1 and c2 that vertex preys on each vertex of v 4vv5vv3 which is just 31
PAGE 41
equal to c3 so c3 is a commonenemy clique. Thus all the edges of G are accounted for. We still need to verify that there are no additional edges in the niche graph of this digraph. First note that, since v1 v2 and v3 are already in one clique, as are v2 v3 and v4 any additional competition edge in the niche graph would have to.come from a vertex in v 1 and a vertex in v 4 with a common prey, but the vertices of v 1 and the vertices of v 4 prey on disjoint sets. In a similar fashion, no extra commonenemy edge is possible; the only vertices with predators are in c3 I We will prove one more theorem in this vein, but there does not appear to be any immediately obvious way to extend these arguments. The next theorem has five different cases to consider, and the proof will only be sketched. The proliferation of cases does not cease at five; to prove a similar theorem in the same fashion for a unit interval graph with five cliques would involve fourteen cases. After noting two special types of clique structure which will allow us to prove that the unit interval graph is a niche graph and investigating what properties a unit interval graph that is not a niche graph would possess, we will consider the question of how many different clique 32
PAGE 42
structures an ordered unit interval graph with a given number of cliques can have. Theorem 3.5. A connected unit interval graph G with four maximal cliques is a niche graph. Proof: As noted above, we will only sketch the There are four maximal cliques, We look at five cases. Case 1: The four cliques have a common vertex. This is a special case of Theorem 3.6, proved below. case 2: c 1nc3 = 0 and c 2nc4 = 0, i.e., there is minimal overlap of the cliques. This is a special case of Theorem 3.7, proved below. Case 3: c 1 intersects only c 2 ; c 2 c 3 and C 4 have a common vertex. We partition the vertices of G as follows: v 1 = ccc2 ; v 2 = c 2nc1 ; v 3 = C 2C3c1 (and may be empty); V 4 = c 3c4 ; v 5 = c 2nc3nc4 ; V 6 = C 3 c2; and v 7 = c 4c3 Note that all sets are nonempty except possibly the one noted. The arcs of the digraph on V(G) are: from c 1 to v 4 from c 2 to v 6 from c 3 to v 7 and from v 4 to v 5 It is easy to verify that the niche graph of this digraph is G. Case 4: The first three cliques intersect; C 4 only intersects c 3 This is just the reverse of case 33
PAGE 43
3 where ci plays the role of c5_i. The appropriate adjustments to construct the digraph are easy. Case 5: c1 intersects c2 and c3 but not c4 ; c4 intersects c2 and c3 but not c1 Let V 1 = c1c2 ; v6 = c 3c2 ; and v7 = c4c3 Only v4 may be empty. The arcs of the digraph on V(G) are from c 1 to V 5 from c 2 to V 6 and from c 3 to v7 Note that V 3 already preys This digraph can be shown to have G as its niche graph. I Although induction on the number of cliques does not appear to be a promising line of attack, some special structures can be treated. For example, in the next section we will extend the method used in case 2 of Theorem 3.4 to establish the existence of a family of unit interval graphs with an arbitrarily large number of cliques which are also niche graphs. 3.2 Are All Incomplete Unit Interval Graphs Niche Graphs? Results in this section are fragmentary, and represent efforts to establish by induction the truth of the question in the title. While no final answer is yet available, one of the consequences of the partial results is that the clique structure of any mini34
PAGE 44
mal counterexample is established. (A minimal counterexample is the smallest incomplete unit interval graph that is not a niche graph.) From Theorem 3.2 we know that such a counterexample must be connected, since any disconnected unit interval graph composed of components which are themselves niche graphs (or complete graphs) must be a niche graph. Additionally, the digraphs in the previous proofs, constructed to have a desired niche graph, have the property that each clique of the niche graph is either an inneighborhood or an outneighborhood of a single vertex. This property will be true of the digraphs we construct in the proofs of this section as well. These observations will guide our assumptions in the final Theorem. We will begin by showing that some families of unit interval graphs are niche graphs, and finish by summarizing what we know would have to be true of the smallest unit interval graph that is not a niche graph. Theorem 3. 6. Every unit interval graph G whose maximal cliques have a nonempty intersection is a niche graph. 35
PAGE 45
Proof: With the usual labeling of vertices V = {v1 v 2 ... vn} and cliques {C1 c 2 ... Cm}, partition V into 2m1 nonempty subsets as follows: vi = ci ci+l fori= 1, ... m1; vm = clnc2n ... ncm vm+i = ci+1ci for i = 1, ... m1. In other words, for im, Vi is that part of Cmi+l which does not overlap the preceding clique. Remember that these cliques are maximal and consist of consecutively numbered vertices, so that Cici+l consists of the set of consecutive vertices beginning with the first vertex of Ci and going up to, but not including, the first vertex of the next maximal clique, Ci+l When we get to Vm, it consists of all the vertices beginning with the first vertex of em and going up to, and including, the last vertex of c 1 The subsets after Vm are almost mirror images of the subsets before it; Ci+lci consists of the vertices from, but not including, the last vertex of Ci to, and including, the last vertex of Ci+l Clearly these subsets are all disjoint, and each clique Ci is the union of the m consecutive subsets beginning with Vi and ending with Vm+il 36
PAGE 46
Now create a digraph on V by drawing arcs from each vertex of Ci to each vertex of Vm+i fori= 1, ... m1, and arcs from each vertex of Vm_1 to each vertex of Vm. We claim that this digraph has G as its niche graph. Clearly each of the first m1 cliques is a competition clique in the niche graph. Since Vm_1 is in each of the first m1 cliques, each of its vertices has arcs to every vertex in Vm+1uvm+2 u ... uv2m_1 as well as to Vm. This just says that it has arcs to every vertex of em, so em is a commonenemy clique in the niche graph. It is easy to verify, as in the proof of Theorem 3.4, that no extraneous edges are present. I A unit interval graph which has the property that the intersection of all its maximal cliques is nonempty is in some sense at the far end of the spectrum from a unit interval graph whose cliques intersect minimally. However, a unit interval graph of this second type also is a niche graph, as the following theorem proves. (This theorem appears in Bowser and Cable[5] in a slightly different form, with a different proof.) Theorem 3.7. If the intersection graph of the maximal cliques of a unit interval graph G is a path, then G is a niche graph. 37
PAGE 47
Proof: With the usual numbening of maximal cliques {C1 c2 ... Cm}, the hypothesis of the theorem says that cinci+2 = o fori= 1, ... m2, that is, each clique intersects only the immediately preceding and immediately succeeding clique. The main idea of the proof is to construct a digraph in which each oddnumbered clique preys on a vertex in the succeeding clique, and each evennumbered clique is preyed upon by a vertex in the preceding clique. One slight adjustment for the final clique (if oddnumbered) completes the proof. Set up a digraph on V(G) according to the following rules: for i odd (and less than m), create an arc from each vertex of Ci to the lowestnumbered vertex succeeding the vertices of Ci. For i even (and less than or equal tom), create an arc to each vertex of Ci from the highestnumbered vertex preceding the vertices of ci. If m is even, this digraph has G as its niche graph. (The case where m is odd is considered in the next paragraph.) It is clear that each maximal clique of G is in the niche graph. Since there are outarcs only from vertices in oddnumbered cliques, and these are disjoint by hypothesis, and the arcs from different oddnumbered cliques go to different vertices, no additional competition edges can be in 38
PAGE 48
the niche graph. Similarly, inarcs go only to evennumbered cliques, and no additional commonenemy edges can exist in the niche graph. If m is odd, so that the vertices of em have no succeeding vertex on which to prey, there are two cases to consider. If eml has no simplicial vertex, every vertex in it is also in em_2 or in ern (but cannot be in both). Then, by the previous construction, the vertices of ern_2 all prey on the first vertex in ern, and one vertex of ern_2 preys on the vertices of ern_1 Simply have the last vertex of ern_2 prey on the vertices of ern, and the construction is complete. The clique ern is in the niche graph, and the only arcs to vertices in ernern_1 are from the last vertex of ern_2 so no extra commonenemy edges appear in the niche graph. If ern_1 has simplicial vertices, then the previous construction resulted in creating arcs from em_2 to the first of those vertices. Remove those arcs, and instead draw arcs from each vertex of ern_2 to the first vertex of ern. Keep the arcs from the vertex of ern_2 immediately preceding em_1 to the vertices of ern_1 Finally, draw arcs from the last vertex of em_2 to each vertex of em. Now em_2 is a competition clique, and em_1 and em are commonenemy cliques in the niche 39
PAGE 49
graph. Furthermore, since all arcs to vertices in the last two cliques come from vertices in Crn_2 there are no extraneous competition edges in the niche graph; since the vertices of Cmcrn_1 have arcs only from the last vertex of crn_2 and the vertices of crn_1 crn have inarcs only from a vertex preceding that, no extraneous commonenemy edges can exist in the niche Theorem 3.8 If a unit interval graph with the usual labeling has the set of first vertices (or the set of last vertices) of each maximal clique labeled consecutively, then the unit interval graph is a niche graph. Proof: Let { c 1 c 2 ... Crn} be the maximal cliques of G with first vertices {v1 v 2 ... vm} We define the arcs of a digraph D on V(G) as follows: fori= 1, ... m1 let each vertex of Ci prey on the vertex following the last vertex of Ci. Also let the vertex immediately preceding em prey on all the vertices of em. We claim that G is the niche graph of D. Clearly all maximal cliques of G are in the niche graph of D; we must show there are no additional edges. First, suppose va and vb attack vc, with a
PAGE 50
and va immediately precedes em. Bui;: in this case, since vb also preys on vc, vc is the vertex immediately succeeding a clique containing vb, and since that clique must contain va, vavb is again an edge of G. Now consider the possibility of an additional commonenemy edge, where va attacks vb and vc. If va is the immediate predecessor of em, then vbvc is an edge of G. Otherwise, both vb and vc are vertices immediately following maximal cliques containing va, say ep and eq, respectively. But then, since the first vertices of the maximal cliques are consecutive, vb and v q belong to eq+l: eq+l must begin with the vertex succeeding va or an earlier vertex (i.e., vb or an earlier vertex), and must include at least vc, since it must extend beyond eq. Thus vbvc is an edge of G, and the niche graph of the digraph D has no edges not in G. Therefore G is a niche graph. (To prove the theorem for the case where the last vertices of the cliques are consecutive, all that need be done is to reverse the numbering of the vertices and cliques.) I The last theorem has an inductive flavor, but unfortunately requires something similar to a simplicial vertex to allow us to show that the next larger graph is also a niche graph. However, it does help to 41
PAGE 51
further characterize the minimum CG>unterexample, if one exists. Theorem 3.9. If all incomplete unit interval graphs on n or fewer vertices are niche graphs of acyclic digraphs with each maximal clique an inor outneighborhood of some vertex, then any unit interval graph G on n+l vertices, with a vertex x that is neither the first nor the last vertex of any maximal clique, is a niche graph. Proof: G x is a unit interval graph, and thus by hypothesis has a generating digraph D of the type described. Since x was neither the first nor the last vertex of any maximal clique, G x has the same number of maximal cliques as G. With our usual ordering, each clique Ci(G x) is either the same as Ci(G) (if neither contains x), or is just Ci(G) {x}. We will modify the digraph D so that it is a digraph whose niche graph is G. Each clique of G x is an inor outneighborhood of some vertex of D. Let D' be the digraph obtained from D by setting V(D') = V(D) u {x} and A(D') = A(D) u {xy I x E Ci(G) and Ci(Gx) is the inneighborhood of yin D} u {zx I x E Ci(G) and Ci(Gx) is the outneighborhood of z in D}. We claim the niche graph of D' is G. Clearly every edge of G is in 42
PAGE 52
the niche of D'. Suppose that some other edge notinG is in the niche graph of D'. Either it has x as an endpoint or it does not. Assume first it has x. If the edge (call it ax) is a competition edge, then there are arcs ay and xy in D' for some vertex y. But the only arcs xy are to vertices which are preyed upon by the members of a maximal clique to which x belongs, so ax must be an edge of G. A similar argument holds if ax is a commonenemy edge. If the edge does not have x as an endpoint, call it ab. If ab is a competition edge, then ax and bx are arcs in D', and x is in a maximal clique which 1s the outneighborhood of a, and in a maximal clique which is the outneighborhood of b. But the intersection of these two maximal cliques cannot be only x, else x would be the first element of one clique and the last element of the other. So a and b have another common prey, and ab is already an edge of G. I Now we have several theorems which are quite suggestive; unfortunately, the result they suggest remains unproven. At this point, however, we can state with some precision what an incomplete unit interval graph which is not a niche graph must look like. The smallest such example would have to have at least 5 maximal cliques, each vertex would have to be 43
PAGE 53
either the, first vertex or the last vertex of some maximal clique, at least two cliques must be disjoint, and neither the set of first vertices nor the set of last vertices of the maximal cliques could be consecutive. Such a unit interval graph can be constructed easily enough, but all examples investigated have proved to be niche graphs. While we have not yet been able to actually prove that the cliques of any unit interval graph can be made the appropriate inand outneighborhoods of a generating acyclic digraph, we think there is sufficient evidence to conjecture: all incomplete unit interval graphs are niche graphs. 3.3 The Number of Possible Clique structures for Labeled Unit Interval Graphs In several of the proofs of the preceding sections, the structure of the maximal cliques of the unit interval graph is of substantial importance. If the first clique intersects the last, for example, application of Theorem 3.6 guarantees that the graph is a niche graph as well. Furthermore, the proofs of Theorems 3.3, 3.4, and 3.5 show that the number of cliques and the ways in which they intersect each other are important to the construction of a digraph 44
PAGE 54
which has the,target unit interval graph as its niche graph. Given the importance of this intersection structure, the question of how many different structures are possible for a given number of maximal cliques naturally arises. By clique structure we just mean which cliques intersect each other (essentially. the clique graph of the graph). To make these ideas more precise, let us begin with a few definitions. A unit interval graph G of order n is properly labeled if its vertices are numbered {v1 v 2 ... vn} and its maximal cliques are numbered {e1 e2 ... em} so that each clique consists of consecutively numbered vertices and, for i
PAGE 55
An important consideration is that in unit interval graphs with the usual notation of this chapter, the cliques consist of consecutively numbered vertices and so are naturally ordered by their first (or last) vertices. If we look at the vertices {v1 v 2 ... vn} of a unit interval graph and restrict our attention to the subscripts of the first vertex of each maximal clique, we get an increasing sequence { a 1 =1, a 2 ... am}; looking at the subscripts of the last vertex of each maximal clique we get an increasing sequence { b 1 b 2 ... bm=n}. Combine these two sequences into one nondecreasing sequence S of length 2m, breaking ties by the rule: if ai = bj, then ai precedes bj inS. Now (we are transforming the problem into another problem with a wellknown solution) replace each ai by a plus 1, and each bi by a minus 1. We have a sequence of m positive and m negative ones of length 2m. Note that it is easy to reconstruct the clique structure of the unit interval graph from its sequence of plus and minus ones; the first clique intersects the same number of cliques as the number of plus ones preceding the first minus one, and so on. We wish to establish a onetoone correspondence between the sequences of m positive and m negative ones in which the partial sums are all nonnegative 46
PAGE 56
and the of cliquesimilar unit interval graphs on m maximal cliques. It is clear that any two cliquesimilar unit interval graphs will produce the same sequence of plus and minus ones. It is also clear that any sequence derived from a unit interval graph can have no negative partial sum; each clique begins with a plus one and ends with a negative one, so a negative partial sum would indicate that some clique ended before it began. If we start with any sequence of m plus ones and m minus ones with no negative partial sums, we can construct a unit interval graph producing that sequence easily. The ith positive one indicates the beginning of the i th maximal clique; it will intersect all the maximal cliques ck, ki, for which the jth +1 occurs before the ith 1. So the onetoone correspondence is established. We can now state a theorem. Theorem 3.10. The number of different clique structures possible for a labeled unit interval graph with m maximal cliques is the mth Catalan number, (1/ (m+1)) (2m!) 1 (m!m!). Proof: We have established a onetoone correspondence between the clique structures (i.e. the 47
PAGE 57
cliquesimilar classes) and the sequences of m positive and m negative ones with no partial sums negative. But this is already known to be the mth Catalan number, a result established in 1946 by Erdos and Kaplansky[9]. An elegant proof can be found in Honsberger [ 2 0] I It is easy to see that a unit interval graph, or, more precisely, all the graphs of a cliquesimilar equivalence class, are disconnected if and only if the corresponding sequence of plus and minus ones has at least one partial sum of zero (in addition to the trivial zero sums at the start and end of the sequence). This observation makes it easy to determine the number of cliquesimilar equivalence classes of connected labeled unit interval graphs with m maximal cliques: the number is just the number of sequences with no nontrivial partial sums of zero. But since each sequence must begin with +1 (and end with 1), if we discard these two end numbers, what we require is that the remaining sequence of 2m2 plus and minus ones must have no negative partial sums. This will be sufficient to keep the partial sums of the whole sequence greater than zero, and the number of such sequences, from the discussion of the previous theorem, is just the (m1)5t Catalan number. We have just proved 48
PAGE 58
Theorem 3.11. The number of different clique structures on connected labeled unit interval graphs with m maximal cliques is the (m1) st Catalan number, (1/m) (2m2)! I ( (m1)! (m1)!). 49
PAGE 59
4. Alternative Definitions for the Niche Number, and some of Their consequences Although the niche number of a graph is welldefined, the concept has some characteristics which are not necessarily desirable. Not only are niche numbers difficult to compute, but many classes of graphs turn out to have infinite niche number. In fact, Cable, Jones, Lundgren, and Seager [6] showed that, if a graph G is Km+1free with maximum degree greater than 2m(ml), it must have infinite niche number. In a sense, there isn't room to add enough isolated vertices. Are there reasonable alternatives? This chapter discusses some possibilities. It has been published, in slightly different form, in Congressus Numerantium jointly by the author with Jones, Lundgren, and Seager[2]. The original niche number definition is certainly usable, and sensibly parallels the definition of competition number. It leads to an interesting theory. However, if the niche number is viewed as a measure of how "close" a graph is to being a niche graph, a niche number of infinity seems unsatisfactory, especially for a.graph like K 1 3 : it can be turned into a niche 50
PAGE 60
graph by adding a pendant edge, or by the disjoint union with itself, or by the disjoint union with a triangle. To say that K 1 3 is infinitely far from being a niche graph does not do the situation justice. v2 v4 xl x3 xl vl v4 v4 v3 v3 x2 x4 x3 /rA2 A2 vl vl xl 2 v4 v3 v4 v3 x4 x3 Figure 4.1 Digraphs Whose Niche Graphs Contain K 1 3 Some alternative definitions of niche number are suggested in this chapter. we show that these definitions, which retain the flavor of the original niche number definition, have the desirable characteristic of being finite for all graphs. Furthermore, the related alternative definitions of competition number would not change the more widely known results in that theory. 51
PAGE 61
4.1 Alternatives for the Niche Number Definition Why search for alternative definitions of niche number? We are primarily interested because the current definition allows a niche number of infinity. The niche number should in some sense measure how difficult it is to turn a given graph into a niche graph, and "infinitely difficult" doesn't seem the proper answer. For example, we will show that every graph is an induced subgraph of a niche graph which has no more than 9e(G) additional vertices, where 9e(G) is the minimum number of cliques needed to cover the edges of the graph. Additionally, Sakai[36] has shown that the disjoint union of any graph with its line graph is a niche graph. It is only when requiring additions to the graph to be isolated vertices that some graphs cannot be changed into niche graphs. The addition of isolated vertices is natural in the context of competition graphs. To create an edge between two vertices in a competition graph, all that need be done is to add arcs in the food web from the two predators to a prey with no other predators. If no such prey exists, adding a new prey to the food web simply creates an isolated vertex in the competition graph. Thus every edge in the competition graph can 52
PAGE 62
be created with only the addition of isolated vertices as a side effect. A food web for the graph has been created with new prey, but no new predators, and so no undesired new edges, appear. In contrast to the competition graph situation, in a niche graph additional edges cannot always be added just by appending an extra vertex and drawing two more arcs. The difficulty is that not only common prey, but also common enemies, create edges. Thus, adding arcs from existing vertices to a new vertex, which will certainly create desired edges among the existing vertices, may also have the undesired effect of creating edges joining the new vertex (which should be isolated) to some previously existing vertices which are also prey of the vertices preying on the new vertex. This is the reason that many graphs have infinite niche number. We have proposed relaxing the requirement that additional vertices must be isolated. We will denote the (original) niche number by n 0 suzanne Seager, in a communication to Kathryn Fraughnaugh[41], suggested the following alternative definitions of niche number. The first niche number of a graph G, n 1(G), is the minimum nonnegative integer k such that the dis53
PAGE 63
. r I joint union of G and k vertices in complete components (not connected to G) is a niche graph. The second niche number of a graph G, n 2(G), is the minimum nonnegative integer k such that the disjoint union of G and k vertices in other components is a niche graph. The third niche number of a graph G, is the minimum nonnegative integer k such that G is an induced subgraph of a niche graph on ( /V(G) / + k) vertices. In other words, each new niche number still counts the number of extra vertices required to make G into a niche graph. The first requires these extras to be in their own complete components; the second to be in components separate from G though not necessarily complete; the third allows the extras to be connected to G as long as G is an induced subgraph. This chapter and the next explore some of the ramifications of these definitions. Note that these new niche numbers will not make much difference when G has a finite (original) niche number of zero, one, or two. If any niche number is zero, they all are: G is a niche graph. If n 0 (G) is 1, so is each other niche number. (But n 3 (G) can be 1 while n 0 (G) is infinite; see figure 4.1 above.) If 54
PAGE 64
n 0 (G) = 2, then n 1 (G) = 2 and n 2(G)=2; n 3 (G) is 1 or 2. (The fourcycle is an example of a graph which has see figure 4. 2. ) Thus we already know, for example, from the original paper [6], that the niche number (any niche number) of a complete graph on more than 2 vertices is 1, of a path i on more than 2 vertices is 0, and of a cycle on.more f than 8 vertices is 0. 10' 4 3 The cases where n 0 (G) is infinite are more interesting; the new niche numbers should help differentiate among the many different families. Among the known graphs with infinite (original) niche numbers are wheels [4], some variations of stars called novas [6], and complete bipartite graphs with at least three 55
PAGE 65
vertices in one partition [36]. New niche numbers for these graphs are largely unknown at present. If n 0 (G) is infinite, the other niche numbers may be quite small, or, as shown in a theorem to be presented in this chapter, arbitrarily large. K 1 3 for example, has first and second niche numbers equal to 3, and its third niche number is only 1, as figure 4.1 shows. The concept of niche graphs originally derived from work with competition graphs, and many of the initial results, problems, and conjectures were suggested by analogy with known results in competition graphs. The original definition of the niche number of a graph was chosen to be similar to the definition of competition number. If we consider the possibility of changing the definition of competition number to parallel these new niche number definitions, a rather surprising result emerges. Define the first competition number of a graph G, k 1(G), to be the minimum number of extra vertices, in complete components, such that the disjoint union of G and these components is a competition graph. Simi larly the second competition number, k 2(G), is the minimum number of extra vertices (in components, whether complete or not) such that the disjoint union of G and these components is a competition graph, and 56
PAGE 66
the third competition number, k 3 (G) is the minimum number of extra vertices such that G is an induced subgraph of a competition graph of order IV(G) I + k 3(G). It is clear that k(G) k 1 (G) k 2 (G) k 3(G), since any set of isolated vertices is also a set of complete components, thus a set of components, and G, as a component of a graph, is automatically an induced subgraph. Less obvious is that these four numbers must be equal. The following theorem was first proved by Suzanne Seager[41]. Theorem 4.1. For any graph G, k(G) = k 1 (G) = k 2 (G) = k3(G). Proof: Consider any food web whose competition graph has G as an induced subgraph. We construct a food web on the same number of vertices whose competition graph is the disjoint union of G and isolated vertices, showing that k(G) :s; k 3 (G). Then by the remark above we will have equality of all four competition numbers. Eliminate all arcs which do not come from a vertex of G. The remaining digraph has as its competition graph G (since all within G remain) and some isolated vertices (with no outarcs, the remaining vertices can have no competitions). 57
PAGE 67
Therefore k(G) :S k 3(G), and k(G) = k 1 (G) k3(G). = I Whether this result could prove useful for determining unknown competition numbers has not been investigated. 4.2 Basic Properties of New Niche Numbers The principal objection to the original definition of niche number was that it is infinite for some graphs. Each of the new definitions answers that objection. In some of the proofs that follow, food webs which have a given graph G as a subgraph of their niche graphs are constructed. When referring to the vertices of the food web, the vertices which correspond to vertices of G will be called graph vertices; the other vertices of the food web will be called extra vertices. Theorem 4.2. For every graph G, (1) n1(G), n 2(G), and n 3 (G) are finite. (2) n1 (G) :S 98 (G) + 1. (3) n2(G) :S 98(G). Proof: First note that if n 0 (G) = k, then G and k isolated extra vertices form a niche graph. Since each extra vertex is in its own complete component, 58
PAGE 68
n 1 (G) s; k, for G and k extra vertices components form a niche graph. That n 1 (G). Similarly, n 1 (G) 2: n 2 (G), since in =mplete is, n 0 (G) 2: n 1 (G) is the number of extra vertices in complete components which, together with G, form a niche graph, and n 2 (G) is the minimum number of extra vertices in components (complete or not) which suffice. Clearly n 2 (G) 2: n 3 (G) as well, for if G and k vertices in other components form a niche graph, G is an induced subgraph of that niche graph. In other words, if a digraph D demonstrates that n 1 (G) is k or less, the same digraph gives k as an upper bound for n 2 (G) and n 3(G). Therefore showing that n 1 (G) is finite for all graphs G will prove part ( 1) Let G be an arbitrary graph. Construct a digraph for G as follows: select an edge clique cover of the graph. To the vertex set of the graph, add a new vertex for each element of the edge clique cover, and add one additional vertex (the sink) This (the union of the graph vertices, the clique vertices, and the sink) will constitute the vertices of the digraph. Arcs in the digraph will be from each graph vertex to each clique vertex whose clique contains the graph vertex, and from each clique vertex to the sink. TIE niche graph of this digraph will have no edges between 59
PAGE 69
the vertices of G and any other vertices, because nothing preys on the graph vertices (hence there are no commonenemy edges involving any graph vertex), graph vertices prey only on clique vertices, and clique vertices prey only on the sink vertex ( so no common prey edge can connect a graph vertex to an extra vertex) If x and y are graph vertices, there will be an edge between them in the niche graph of the digraph if and only if they both prey on the same clique vertex, that is, if and only if they are in the same edge clique, and so have an edge between them in G. Clearly the clique vertices form a complete graph, since they all prey on the sink, and the sink is an isolated vertex in the niche graph. Thus there is a niche graph consisting of G, a complete graph on the clique vertices, and an isolated vertex. Hence n 1(G), and therefore also n2(G) and n3(G), are finite. The construction also gives upper bounds on the first and second niche numbers mentioned in the theorem. We used precisely (Oe(G) + 1) extra vertices to construct the digraph showing that n 1(G) is finite, and the sink vertex is unnecessary if the clique vertices need not be in complete components. An example of the construction can be seen below in figure 4.3. 60
PAGE 70
1 7 6 2 1 1 2 cl 3 4 4 7 4 7 s ts 5 6 6 5 Figure 4. 3 A Graph and the Digraph and Niche Graph Constructed in Theorem 4.2. While an upper bound is fairly easy to construct, we have obtained a lower bound only when the maximum degree of the graph is larger than twice the maximum clique size. We state a theorem for trianglefree graphs, and then generalize to other graphs. Theorem 4. 3. For any trianglefree graph G with maximum degree k (where k > 4), n 2 (G) (k2). Proof: Let D be a digraph with G as a component (or components) of its niche graph. Consider a vertex v in G of degree k, k > 4. Each edge incident to vis created by a common prey of v and another vertex of G, or a common enemy of v and another vertex of G. These (common prey and common enemies) must all be distinct, for otherwise G would have a triangle. Now consider the set of all prey of v. This forms a clique in the niche graph, so at most two vertices of G can be in 61
PAGE 71
this set. Furthermore, if the set has any extra vertex, it cannot have any graph vertex, because there are no edges between extra vertices and graph vertices. Thus if the set has more than two vertices, they are all extras. Similar considerations apply to the set of predators of v. since k > 4, at least one set has more than two vertices, so at most two of the predators and prey of v can be vertices of G. Then there must be at least k 2 extra vertices, showing that n 2 (G) (k2). I This result sometimes gives excellent bounds. Figure 4.4 shows a graph for which the lower bound of Theorem 4.3 is exactly the niche number. 1 4 3 1 ot1tt4 8 2 6 3 7 Figure 4.4 The proof of Theorem 4. 3 depends on the fact that, since G is trianglefree, each edge of G must represent an inneighborhood of exactly two arcs, or an outneighborhood of exactly two arcs. If G has 62
PAGE 72
larger cliques, ,then each edge may arise from larger neighborhoods, and (if G is free) as many as m edges incident with a vertex v may all be created by one arc from (or to) v in the digraph. Theorem 4.3 may be generalized to take these facts into account. Theorem 4. 4 If a graph G is Km+cfree with maximum degree k and k > 2m(ml), then n 2 (G) is at least ( rk/ (ml.Jlm> Proof: The proof is similar to the proof of Theorem 4.3. Consider a vertex v of maximum degree in G, and any digraph D which has G as a component (or components) of its niche graph. Since G is Km+1free, no vertex preyed on by any vertex of G has more than m inarcs, and no vertex preying on any vertex of G has more than m outarcs. Hence at most (m 1) edges incident to v in G can be from the same prey (or common enemy) In D, v can have at most m inarcs from vertices in G, and also at most m outarcs to vertices in G. This can create at most 2m (m 1) edges. If v has greater degree, there must be an arc to or from an extra vertex. But if any arc goes to an extra vertex from v, all arcs from v must go to extra vertices, so v can have at most m arcs from vertices of G, and they can account for only m(m1) edges inci63
PAGE 73
I I dent to v in G. Then the remaining (km(m1)) edges must come from arcs to extra vertices, and since each creates at most (m1) edges in G, there must be at least
PAGE 74
5. Alternative Niche Numbers for Complete Bipartite Graphs We next look at niche numbers for specific families of graphs. For graphs with infinite original niche number, a few results have been discovered. We concentrate on complete bipartite graphs. Theorems 4.2 and 4.3 give upper and lower bounds on the niche numbers of these graphs; we make these bounds more precise. For stars (complete bipartite graphs of the form K 1,n), we will show that the second niche number is equal to the upper bound of Theorem 4.2, but for complete graphs of the form Km n the niche numbers diverge from this theoretical bound substantially. Theorem 5.1. For n > 2, n1(K1 ,0 ) = n 2(K1 ,0 ) =nand n3 ( K 1 n) = n 2 Proof: Let v 0 be one of the bipartitions of K 1,n (the center) and {v1 v 2 ... vn} be the other (the rim vertices). Consider first the second niche number. Since K 1,n is trianglefree, v 0 must have a different common enemy or common prey with each of the n rim vertices. Since none of the rim vertices is adjacent to any other, no more than one (call it v 1 ) can be, 65
PAGE 75
I say, a prey of v 0 If so, then v 0 cannot prey on any other vertex whatsoever, and must be the prey of at least n 1 other vertices, of which at most one can be one of the remaining rim vertices. But that would create edges from that rim vertex to extra vertices, so all the n 1 other vertices are extras. Now consider the question: how can the edge between v 0 and v 1 be created? They must have a common predator or a common prey. Since all predators of v 0 must be extras, a common predator is impossible because there would be an edge between it and v 0 A common prey is also impossible since there would be an edge between it and v 1 Thus v 0 does not prey on any rim vertex, nor is it preyed upon by any rim vertex. Since there are n rim vertices, each requiring a different common prey or common predator with v 0 there must be at least n extra vertices in any digraph that has K 1,n as a component of its niche graph. That n extras suffice is shown by the digraph below: v 0 preys on all n extra vertices and each vi preys on the corresponding xi. This also shows that n 1(K1,n) = n, since the resulting niche graph consists of K 1,n and n extra vertices in a complete component. To show that n 3(K1,n) = n2, note that each rim vertex must have a distinct common prey or common 66
PAGE 76
enemy with v 0 At most one prey of v 0 can be a rim vertex; at most one predator also, else there would be an edge between two rim vertices in the niche graph. Thus at least n 2 extras are necessary, and the general construction, illustrated for K 1 4 in the figure below, shows that n 2 are sufficient. I lv2 4A3 0 1 2 3 4 1 0 3 4 Figure 5.1 K 1 4 and Its Digraphs for the Second and Third Niche Number Proof: We construct, on 2n + 3 vertices, an acyclic digraph D that has a niche graph consisting of K 2,n as one component and the remaining n + 1 vertices in a single complete component. one of the bipartitions of K 2,n, V = {v1 v 2 ... vn} the other, and X= {x1 x 2 ... xn+l} a set of extra vertices. The union of these three sets is the vertex set of D. The arc set consists entirely of arcs to or from the extra vertices. For each extra xi' ( i = 67
PAGE 77
In the niche graph, these arcs will create all edges Note that extras prey on (and are preyed upon by) only graph vertices, and graph vertices prey on (and are preyed upon by) only extras. Clearly there are no edges between extras and graph vertices, between u 1 and u 2 (since u 1 is only a predator, and u 2 is only a prey), or between any vertices in V (since each vi preys on a different extra, and is preyed upon by a different extra). By adding one final arc x0u 2 (which creates no new edges among graph vertices since x0 preys on no other vertex), all the extras prey on u 2 Thus they form a clique, and the niche graph consists of the disjoint union of K2,n and Kn+l" I This construction is illustrated in figure 5.2. v Figure 5.2 The Construction Described in Theorem 5.2 Applied to K 2 4 : n 1(K2 4 ) 5 68
PAGE 78
\ The construction illustrated in figure 5. 2 has several suggestive features. One of the bipartitions has each vertex with an equal number of inand outarcs; in the other each vertex has only inarcs or only outarcs. Perhaps the most interesting aspect of the construction is that no graph vertex has any arc to or from any other graph vertex. It is somewhat surprising that we cannot eliminate one or more extras by increasing the predatorprey relationships among graph vertices. We will call arcs in D with both head and tail vertices in V(G) graph arcs. In the proof that follows we show that the existence of graph arcs can only increase the number of extra vertices needed to construct a digraph with a complete bipartite graph in its niche graph. Theorem 5.3. n1(K2 ,0 ) = n2(K2 ,0 ) = n + 1. Proof: The proof is in three main parts. First, Theorem 5.2 establishes an upper bound of n + 1 for the niche numbers. Then we show that no digraph without graph arcs can have fewer than n + 1 extras. Finally we prove by a number of cases that the use of graph arcs to create edges of the bipartite graph always requires at least n + 1 extras. 69
PAGE 79
Theorem 5.2 guarantees that the niche number is no more than n + 1. Now suppose we have an acyclic digraph D with K 2,n as a component of its niche graph. Let U = {u1 u 2 } be one of the bipartitions of K 2,n, V = {v1 v 2 ... vn} the other, and X= {x1 x 2 ... xn+l} a set of extra vertices. If there are no edges in K 2,n created by graph arcs, there must be at least n extras: K 2,n has 2n edges and no triangles so each edge must come from an inor outneighborhood with exactly two arcs and each extra can have at most two neighborhoods. Suppose, then, that D has only n extras. Each extra must have two inarcs and two outarcs. This means that, in the topological ordering of D, at least one u (call it u 1 ) and one v (v1 ) must precede the first extra, x. Then each arc at u 1 and at v 1 is an outarc, since u 1 and v 1 precede all extras. But u 1 has to have n arcs since it has n edges in the niche graph. Since each extra has an inarc from u 1 each must (in order to create the n edges incident to u 2 ) have an outarc to u 2 that is to say, each arc at u 2 is an inarc. This means that v 1 and u 2 cannot be connected in the niche graph, since one has only outarcs and the other only inarcs. This contradiction shows that n extras will not work; at 70
PAGE 80
least n+1 are necessary if there are no graph arcs creating edges in the niche graph. Finally, suppose that we have an acyclic digraph D which has K 2,n as a component of its niche graph G and some of the edges of K 2,n in the niche graph are created by graph arcs in D. We show, by considering cases, that at least n+l extras are still necessary. We will assume that the edge created by graph arcs is a competition edge. (If only a commonenemy edge exists, the reverse digraph gives the same niche graph but changes that edge to a competition edge.) We call the two predator vertices u 1 and v 1 and the prey vertex is given the index 2. Case 1: u 1 and v 1 prey on u 2 and u 1 has no other prey. Since we assume there are at least three v's, u 1 must have at least n1 (? 2) predators, and hence all must be extras. See figure 5.3. Figure 5.3 Diagram for Proof of Theorem 5.3 71
PAGE 81
Each extra must prey on one of the v's as well. Now edge u 2 v 1 is impossible. There can be no commonenemy edge since u 2 has two predators already, and v 1 cannot prey on itself, and u 1 has no other prey by assumption. There can be no competition edge since a common prey of u 1 would form a cycle, u 2 a loop, any other v a triangle with an extra, and any extra an edge with x and u 2 Case 2: u 1 and v 1 prey on u 2 ; u 1 also preys on v 1 We look at three subcases. Case 2a: v 1 has another predator. This must be another v since there will be an edge with u 1 ; call Now edge v 2 u 2 is impossible by an argument similar to case 1. Case 2b: v 1 has no other predator, and no other prey. In this case u 1 needs n1 predators since it has only one competition edge. All must be extras as argued before. u 2 has two predators, but v 1 creates no edges in the niche graph since it preys only on u 2 So u 2 needs n1 prey, and all must be extras. None can be the same extras as those preying on u 1 else there would be a cycle. Therefore at least 2n2 extras are needed, and since n > 2, at least n + 1. Case 2c: v 1 has no other predator, and one other prey. The prey must be a v (say v 2 ) since an edge 72
PAGE 82
with u 2 is forced. But now edge u 1 v 2 is impossible. v 2 can't prey on u 1's prey (v1 would make a cycle, u 2 a triangle). u 2 can't have a common prey with v 2 (v1 or u 2 would make a cycle, any other v a prohibited vv edge, and any x a vx edge). case 3: u 1 and v 1 prey on u 2 ; u 1 also preys on v 2 This is a little complicated but eventually leads to a contradiction. First, how can we create edge u 2 v 1? The only possibility is a common prey, and it must be a v, say v 3 (v1 and v 2 are not possible). Now we consider edge u 1 v 3 Again there is only one possibility: v 2 as a common prey. But at this point edge u 1 v 2 (the only missing edge in the K 2 3 subgraph we are constructing) is impossible. v 2 has two predators already and neither can prey on u 1 ; u 2 has two prey already and v 2 can prey on neither. In the remaining cases u 1 and v 1 prey on v 2 instead of u 2 Case 4: prey. it can't come from competition because u 1 has no other prey than v 2 and since v 2 already has two predators (one of which is Ul), the common predator must be v 1 Now consider Would create a triangle. The only possible common 73
PAGE 83
predator is u 2 since v 1 already has two prey and any predator of u 1 will have an edge with v 1 After these arcs are forced, edge u 2 v 3 is impossible. u 2 already has two prey, neither of which can prey on v 3 (u1 would create edge v 2 v 3 and isn't allowed any other prey anyway; v 3 would create a loop). v 3 already has two predators, and neither can prey on u 2 (u2 would create a loop and v 2 would create a cycle). case 5: u 1 and v 1 prey on v 2 ; u 1 also preys on u 2 This is the only remaining possibility. Considering edge u 1 v 2 gives us two subcases, depending on whether edge u 1 v 2 is created by a common enemy or by a common prey. The only possible common prey for u 1 and v 2 is u 2 ; the only possible common enemy is v 1 Case 5a: v 2 also preys on u 2 Now edge u 2 v 1 is impossible: no common predator (u1 gives a triangle, v 2 a cycle) and no common prey (v2 a cycle, u 1 a cycle, v 1 a loop, any v a vv2 edge, any x an xv2 edge) case 5b: v 1 also preys on u 1 To get edge u 2 v 1 the only possibility is a common enemy which must be another v, say v3. But now edge u2v3 is impossible. v3 already has two prey, but u2 can prey on neither; u2 already has two predators, but neither can prey on v3. since u 1 and v 1 must prey on either v2 or u2, all possible cases have been exhausted. 74 I
PAGE 84
5.1 The Niche Numbers of Bipartite Graphs with Both Bipartitions Having More Than Two Vertices The new niche numbers of several complete biparti te graphs are already known. In the case of the smaller graphs, K 1 1 has all niche numbers 1; K 1 2 has all niche numbers 0; K 2 2 has n 0 n 1 and n 2 equal to 2 and n 3 equal to 1. We have also proved that. K 1,n (for n>2) has n 0 infinite, n 1 and n 2 equal to n, and n 3 equal to n2, and that K 2 ,n (for n>2) has n 1 and n 2 equal to n+l. We now turn our attention to complete bipartite graphs in which both bipartitions have at least three vertices. Theorem 5.3 was proved in part by demonstrating that graph arcs (that is, arcs in the digraph from one vertex of K 2 n to another) were unnecessary. A digraph with K 2,n as a component of its niche graph, with the minimum number of extra vertices, and without graph arcs, always existed. The proof considered all possible configurations of graph arcs which would create edges in the niche graph. Most resulted in contradictions, showing the configuration under discussion did not exist in any digraph having K 2,n as a component of its niche graph. These configurations are still impossible for any digraph having Km,n (2 m n) rather than K 2,n as a component of its niche graph; the 75
PAGE 85
proofs can be reproduced word for word. To show that graph arcs are not necessary to create minimum digraphs with as a component of the niche graph we need only consider the lone K2,n case in which graph arcs are possible. The next theorem does so, and shows that graph arcs do not exist in minimal digraphs whose niche graph has Km,n as a component. An arc in a digraph will be called functional if it helps create an edge in the niche graph, i.e., if its tail has any other outarcs or its head any other inarcs. Theorem 5.4. If a digraph D has Km,n (3 m n) as a component of its niche graph, then D has no functional graph arcs. Proof: Let {u1 u2 urn} be one bipartition of Km,n and {v1 v 2 ... vn} the other. If D has a functional graph arc, then either its head has an inneighborhood of two graph vertices or its tail has an outneighborhood of two graph vertices. Assume the head has an inneighborhood of two graph vertices, and call them u 1 and v 1 (We can always consider the reverse digraph if the tail has the neighborhood.) By the proof of Theorem 5.3, only one configuration is possible, namely that u 1 and v 1 prey on u 2 u 1 preys on 76
PAGE 86
v 1 and v 1 has no other predator and no other prey. But then edge u 3 v 1 is not possible, for v 1's only predator (u1 ) can not prey on u 3 and v 1's only prey (u2 ) can not be preyed upon by u 3 ; creates a triangle. either situation I This result shows that we may restrict our search for digraphs with Krn,n as a component of the niche graph to those digraphs with no graph arcs. In other words, the digraphs which illustrate the (n2 ) niche number of Krn,n will only have arcs from graph vertices to extras and vice versa. Theorem 5.5 For m even and 4 m n, (mf2)n + 1 n 2(Km,n> (m/2) (n + 1). Proof: Since is trianglefree, every edge in the graph must be created by an inor outneighborhood of precisely two arcs in the digraph. None of the edges are created by graph arcs, so each of the mn edges represents a pair of arcs from an extra (which has no other outarcs) or to an extra (which has no other inarcs). Thus each extra can be matched with at most two of the edges of Krn,n' and at least mn/2 extras are required in the digraph. However, since the digraph is required to be acyclic, the extra that creates the edge between the first element in one bi77
PAGE 87
l I I partition of and the last element of the other must either precede that first element (if the edge is a competition edge) or follow that last element (if the edge is a commonenemy edge). In either case, the extra cannot create a second edge of Km, n. If the extra precedes the first element of one bipartition, no other element of that bipartition can prey on it, since each vertex preys only on vertices following it. A similar argument holds in the other case. Therefore there are at least two extras which can create only one edge between graph vertices, and thus there must be at least mn/2 + 1 extras in the digraph, and that means n 2(Km,nl (m/2)n + 1. To establish the upper bound, consider the following digraph on m = n = (m/2) (n + 1) vertices, which has as a component of its niche graph. Let the vertices in the bipartitions of Km n be {u1 u 2 ... 0 i n and 1 j mj2. Now assign arcs on this vertex set in the following fashion: fori= 1, ... nand j = 1, ... mj2 draw arcs from uj to xij and from xij to umj+l; for i = 1, ... n1 and j = 1 ... m/2 draw arcs from vi to xij and from xij to vi+l; 78
PAGE 88
for j = 1, ... m/2 draw arcs'from x 0 j to umj+l and from x0j to v1 Note how is generated by this digraph. Each xij' for 1 i n 1 and 1 j mj2, has exactly two predators (vi and uj) and exactly two prey (vi+l and umj+l). That produces all edges except those between v1 and the highersubscripted half of the ui and those between vn and the lowersubscripted half of the ui. The arcs from x0j take care of the former and the arcs to Xnj take care of the latter. The digraph has no cycles, for each arc from a graph vertex is to an extra with an equal subscript (the first component of the subscript for arcs and the second component for ujxij arcs) and each arc from an extra is to a graph vertex with a higher subscript. No graph vertex is connected to an extra in the niche graph, for graph vertices prey only on extras while extras prey only on graph vertices: no common enemies or common prey are possible. No graph vertex is connected to another in its bipartition, for each preys on a set of extras with a different first element in its subscript; the predators are similarly disjoint. Thus we have constructed a digraph which has Km n as a component of its niche graph and uses (m/2) (n+1) extra vertices, so n 2 (Km,nl has the desired upper bound. 79
PAGE 89
I I For complete bipartite graphs with an odd number of vertices in the smaller bipartition, the situation is more complicated. The fact that m/2 is no longer an integer makes obtaining a good upper bound more difficult, and so far we have found no general bound which is any better than rounding m/2 up to the next integer and using Theorem 5. 5. However, a cursory consideration of the proof of the lower bound of Theorem 5.5 reveals that it can be applied to these graphs with only a slight modification. Theorem 5.6 Form and n odd and 3 m n, Proof: As in Theorem 5.5, two edges in the complete bipartite graph must be created by arcs to or from extras which do not create other edges. But then there must be at least (mn 2)/2 other extras, and since mn 2 is odd, the minimum number of extras is !(mn 2)/21 + 2, or !mn/21 + 1. I This lower bound is reached by at least one complete bipartite graph; the second niche number of K 3 3 can be shown to be 6 (= !9/21 + 1) by the digraph in figure 5.4. 80
PAGE 90
Many open questions remain in this area. No good upper bound has been proved for n 2 (Km,n) when m is odd, but finding one should be possible using some of the proof techniques of this chapter. The later theorems of this chapter deal with the second niche number of complete bipartite graphs, but similar results for the first niche number are missing. We now know that Nevertheless, the only upper bound we know for n 1 {Km,n) is that given by Theorem 4.2, which is mn + 1. That leaves a large gap between the upper bounds for the first and second niche number of large symmetric complete bipartite graphs, and this is a very promising place to look for a (as yet undiscovered) graph with different first and second niche numbers. Of course, we have only established upper and lower bounds for the second niche number of Km,n (and then only when m is even and 4 :s; m :s; n), not found the exact answer. From studying various exam81
PAGE 91
I I ( I r I l I ples, we tend to think it is the upper bound, but as yet no proof exists. Also in the realm of open problems is the question of the third niche number for these graphs; no work has been done on this question. 82
PAGE 92
6. Loop Niche Numbers and Cyclic Niche Numbers In previous chapters we have discussed known results about (original) niche numbers and proved some new results concerning the niche numbers of classes of unit interval graphs. The original definition of the niche number of a graph was the minimum number of additional isolated vertices whose disjoint union with the graph was a niche graph. This definition was inspired by the analogous (and wellknown) definition for the competition number of a graph. It proved to be less efficacious for two reasons: some graphs can not be turned into niche graphs in this fashion (their niche number is infinity), and very few graphs (of those whose niche number is known) have niche numbers other than 0, 1, or oo. Seager's alternative definitions avoid these difficulties, because with any of the new definitions, all graphs have finite niche numbers, and there are several classes of graphs which have large niche numbers. Seager's definitions also have the desirable property that the analogous definitions for competition numbers result in complete agreement with the 83
PAGE 93
original (already widely studied and wellestablished) competition number on all graphs. We investigated some consequences of these new definitions in previous chapters. Other modifications of the competition number definition have been studied. One possibility that immediately suggests itself is to relax the. requirement that the digraph be acyclic. If, when determining the competition number of some graph, loops or cycles are allowed in the digraph whose competition graph is the graph in question, clearly the competition number can not increase. In fact, the class of competition graphs expands substantially, as the following theorems show. Theorem 6.1 (Dutton and Brigham[8]) A graph G with n vertices is the competition graph of an arbitrary digraph (loops allowed) if and only if G has an edge covering of at most n cliques. I Theorem 6.2 (Roberts and steif[35]) A graph G with n vertices is the competition graph of an arbitrary digraph without loops if and only if G is not K 2 and G has an edge covering of at most n cliques. I 84
PAGE 94
These results show that allowing arbitrary digraphs to generate competition graphs reduces the problem of deciding whether a graph is a competition graph to finding an edge clique cover with cardinality at most the number of vertices in the graph. In this chapter we will briefly examine related questions for niche graphs: which graphs are the niche graphs of digraphs with cycles allowed, and which are the niche graphs of arbitrary digraphs with both loops and cycles? These questions do not have the encompassing answers their cognates in competition graph theory possess. It is easy to show, for example, that many classes of graphs still have infinite niche number. Current results are fragmentary, but we show that unit interval graphs are niche graphs of arbitrary digraphs with loops (no other cycles are necessary), and several interesting avenues for further research exist. We will say that a graph G is a cyclic niche graph if G is the niche graph of an arbitrary loopless digraph. We define the cyclic niche number of a graph G, nc(G), to be the least number of vertices such that the disjoint union of G with those vertices is a cyclic niche graph. Furthermore, G is a loop niche graph if it is the niche graph of an arbitrary digraph 85
PAGE 95
with loops allowed; the loop niche number of G, n1(G), is the minimum number of extra vertices such that the disjoint union of G and those isolated vertices is a loop niche graph. Note that the loop niche number of any graph can not exceed the cyclic niche number. As in the case of the original niche number, if a graph can not be made into a cyclic or loop niche graph by appending isolated vertices, its cyclic or loop niche number is oo. The class of cyclic niche graphs is not as allinclusive as the class of cyclic competition graphs; we will first look at some graphs whose cyclic niche number is infinity. The smallest such graph is the by now familiar example K 1 3 Consider the central vertex (the one adjacent to each of the others). It is incident with three edges. Since the graph is trianglefree, each edge represents a commonenemy or commonprey pair of vertices in any digraph whose niche graph is K 1 3 (with, perhaps, some isolated vertices). Thus the central vertex must either prey on at least two other vertices, or be preyed on by at least two other vertices. In either case those other vertices are connected by an edge in the niche graph, which is impossible. So K 1 3 is not a cyclic niche graph, with 86
PAGE 96
or without additional isolated vertices, and hence has infinite cyclic niche number. The argument above is essentially that of Cable, Jones, Lundgren, and Seager[6] in their original paper, used to prove that n 0(K1 3 ) is infinite. Note that the argument does not apply to loop niche graphs, because the central vertex need not prey on two other vertices; one of the vertices it preys on may be itself. In fact, both K 1 3 and K 1 4 are loop niche graphs, as the diagram below illustrates. ) ) Figure 6.1 K 1 3 and K 1 4 Are Loop Niche Graphs Not all stars are loop niche graphs; even K1,s has an infinite loop niche number. This is a result of the following theorem, and the proof is virtually identical to the proof of a similar theorem in Cable et al.[6]. 87
PAGE 97
Theorem 6.3 If G is a graph with largest clique size m vertices, and maximum degree greater than 2m(m1), then nc(G) = n 1(G) = Proof: Let v be a vertex of G with maximum degree at least 2m(m 1) + 1. Assume G has a finite loop niche number. Since the largest clique of G has m vertices, at most m vertices can attack (or be attacked by) any one vertex. If m vertices attack v, each can attack at most (m 1) other vertices of G. Then at most m(m 1) vertices can be adjacent to v by commonenemy edges. Similarly, at most m(m 1) vertices can be adjacent to v by competition edges. Thus at most 2m(m 1) vertices can be adjacent to v; since the degree of v is greater than that, G can not be a graph with finite loop niche number. Since every graph with a finite cyclic niche number has a finite loop niche number as well, G must have infinite cyclic niche number. I This theorem demonstrates that many graphs have infinite cyclic niche numbers. However, some graphs do have cyclic niche number less than their original niche number. The following theorem gives three cases in which graphs are cyclic niche graphs, but not niche graphs for any of the previously considered definitions. The first result is not surprising. The 88
PAGE 98
second result, on cycles, is noted because the cycles c4 c5 and c6 provided the first graphs with niche number 2. The FishburnGehrlein graphs to which the theorem refers are the graphs which Peter Fishburn and Bill Gehrlein constructed showing there are graphs with arbitrarily large finite niche numbers[ll]. Thus one interesting consequence of the theorem is that the difference between the original niche number and the cyclic niche number can be made as large as desired by selecting the right graph. Theorem 6.4 For graphs with three or more vertices, i) if n 0 (G) = 1, then nc(G) = o; ii) if G is a cycle, then nc(G) = o; iii) if G is one of the FishburnGehrlein graphs, then nc(G) = 0. Proof: For part i), assume that in a digraph D with its niche graph consisting of G and one isolated vertex, the extra is a prey. (Of course, we can reverse all the arcs in the digraph to make this so.) Then, if all graph vertices prey on the extra (so that G is the complete graph) replace the digraph with the complete symmetric digraph on the vertices of G, and the niche graph of this digraph is G. J Otherwise, since n 0 (G) is finite, a topological ordering of the 89
PAGE 99
vertices of D is guaranteed to exist, in which each vertex preys only on vertices succeeding it. Take the first vertex v which doesn't prey on the extra, and let all the extra's predators prey on v. Note that v had no previous predators, since every vertex preceding it in the topological ordering preyed on the extra, and therefore had no other prey. Eliminate the extra, and D now has G as its niche graph. The inneighborhood of v now creates the edges previously created by the inneighborhood of the extra, and since v had no other predators (and the predators of v no other prey), no new edges are created. To show that the cycle en graph, create a digraph on the is a cyclic niche vertices of en by having arcs from vi to vi+l and vi+2 modulo n. The proof that FishburnGehrlein graphs are cyclic niche graphs follows from the construction of the graphs, so we first describe that construction. Each graph (plus isolated vertices) in the family is the niche graph of a digraph which consists of the vertices of G plus an even number of extras. Half the extras are predators, half prey. Half the graph vertices are preyed on by an extra; the other half prey on an extra. The graph vertices that prey on an extra are preyed on only by other graph vertices, none of 90
PAGE 100
which, of course, prey on any extra. We will modify this digraph. First match each prey extra with a distinct predator extra. Then redirect the arcs that attacked each prey extra to its associated predator I I, I extra, and delete the prey extras. This leaves a digraph (with cycles) in which each extra is both predator and prey. Following a construction of Bowser and Cable[4], we now proceed by choosing one predator and one prey for each remaining extra. Have the chosen predator prey on all the extra's prey, and have all the extra's predators prey on the chosen prey. Then eliminate the extras. We claim this new digraph D has G as its niche graph. Note that all arcs which formerly were directed from a graph vertex to an extra are now directed from the graph vertex to another graph vertex which had no previous predators except one of the predator extras. There are no loops, because no vertex preyed on by an extra attacked an extra. Each inneighborhood of an extra (which created a clique in the niche graph) is now an inneighborhood of a graph vertex (whose only previous predator was an extra); each outneighborhood of an extra is now the outneighborhood of a graph vertex (which formerly had no prey except an extra) An example is illustrated in figure 6.2. I 91
PAGE 101
00 7 10 1 11 Figure 6.2 A FishburnGehrlein Graph, Its Digraph, and Its Cyclic Digraph. Suppose a graph G has an even (original) niche number n 0 Then there is at least one acyclic digraph which has as its niche graph the disjoint union of G and n 0 isolated vertices. If such a digraph has an equal number of predator and prey extras, and no prey of any extra preys on another extra, then the process described above may be used to show that G is a cyclic niche graph. In fact, we may use the following theorem of Bowser and Cable [ 4] to allow us to prove a stronger statement. Theorem 6.5 If n 0 (G) = k, and D is an acyclic digraph with niche graph G u Ik, then every extra either eats 92
PAGE 102
a graph vertex which does not eat an extra, or is eaten by a graph vertex which is not eaten by an Since this theorem tells us that each predator extra has at least one prey which does not prey on an extra, and each prey extra has at least one predator which is not the prey of any extra, we can use the construction in the proof of Theorem 6.4 to establish the following theorem. Theorem 6.6 If, for a graph G with n0(G) = 2k, there exists an acyclic digraph D with niche graph G u I 2 k and the 2k extra vertices are divided into k predators and k prey, then G is a cyclic niche graph. Proof: We simply reproduce the proof of part (iii) of Theorem 6.4, choosing the predator and prey of the extras in the intermediate digraph carefully. Assume that D is as described in the theorem. Then match each prey extra with a distinct predator extra. To create the intermediate digraph, modify D by replacing each arc from a graph vertex to a prey extra by an arc from the graph vertex to the matched predator extra. Delete the (now isolated) prey extras, and call the resulting digraph D'. D' is loopless, since we have only redirected the arcs that went from a 93
PAGE 103
graph vertex to an extra so that they now go to a different extra. The niche graph of D' is G u Ik, since any edge of G that was created by competition for a prey extra is now created by competition for the matched "predator" extra. No new edges have been created, for each vertex preying on an extra had no other prey, and each predator extra had no previous predators. Now by Bowser and Cable's result, among the predators of each extra xi there is at least one vertex vi which is not a prey of any extra, and among the prey of xi is at least one vertex ui which does not prey on any extra. For each xi, replace each inarc vxi with the arc vui, and replace each outarc xiu with the arc viu. Delete the (now isolated) extras, and call this resulting graph D''. D'' is still loopless, for each new arc vui is from a vertex which preyed on an extra in D to a vertex which did not, and each new arc viu is from a vertex which did not have an extra as predator to a vertex which did. The niche graph of D'' still contains all the edges of G, since each (inor out) neighborhood of an extra is now the (inor out) neighborhood of a graph vertex. No new edges have been added, for the graph vertices which received the transferred (inor out) neighborhoods had (inor out) neighborhoods in the original di94
PAGE 104
graph which were single extras, and those have been deleted. Hence the niche graph of D'' is G. I By this construction, all known graphs with niche number two are cyclic niche graphs. Additionally, the graph with niche number four presented in Fishburn and Gehrlein's first paper[ll] is a cyclic niche graph. (See figure 6.3 below.) However, this does not prove that all graphs with even niche number are cyclic niche graphs. If the only digraphs of minimum order which have G u Ik as their niche graph are those with an unbalanced number of predator extras and prey extras, we do not know if G is a cyclic niche graph or not. Furthermore, the graphs with odd niche number automatically have an imbalance in the extras of a generating digraph, and the question of whether the smallest known graphs with niche number three (again found by Fishburn and Gehrlein[12]) are cyclic niche graphs is open. I have shown that their cyclic niche number is at most one. In addition, the graph on 14 vertices with niche number three found by them[ll] is a cyclic niche graph, as illustrated in figure 6.3. 95
PAGE 105
I I 4 5 7 8 2 Figure 6.3 The FishburnGehrlein 11Vertex Example with Niche Number 4 Is a cyclic Niche Graph. For the final result in this chapter, we return to unit interval graphs. In chapter three, many subclasses of unit interval graphs were shown to be niche graphs, but we did not prove the conjecture that every noncomplete unit interval graph is a niche graph. For loop niche graphs, the proposition is true. Theorem 6.7 If G is a unit interval graph, n 1 (G) = o. Proof: Using the usual ordering of the vertices of G, so that each maximal clique of G consists of consecutivelynumbered vertices, we construct a 96
PAGE 106
digraph on V(G). For each maximal clique of G, draw an arc from each vertex of the clique to the highestnumbered vertex of the clique. (There is a loop from the last vertex to itself in each clique.) We claim that the niche graph of this digraph is the unit interval graph G. Each edge of G is in at least one maximal clique, so is in the niche graph as a competition edge since the vertices of the clique all have a common prey. There are no other competition edges, for the only vertices that are prey are the last in each of the maximal cliques. Suppose there is a commonenemy edge in the niche graph; that is, there is a vertex x that preys on two separate vertices y and z in the digraph, and therefore yz is an edge in G. Say, without loss of generality, that z is the highernumbered of y and z; then x y < z. Since the vertices of each maximal clique are numbered consecutively, and x and z are in the same clique, y must also be in that clique, so y preys on z. z preys on z also (it is the last vertex in some maximal clique since x preys on it). Thus the commonenemy edge yz is also a competition edge, and no commonenemy edge is a new edge. Hence the niche graph of D is G, and therefore every unit interval graph is a loop niche I 97
PAGE 107
These topics are quite new, and many questions have not been investigated. Some possible directions for further research include answering the questions: Are there graphs with infinite niche numbers but finite cyclic niche numbers? Are there graphs with finite cyclic niche numbers other than zero? (The FishburnGehrlein eightvertex graphs with niche number three may provide a positive answer.) Is there a good characterization of those graphs which have a finite loop niche number? 98
PAGE 108
7. Bibliography 1. c. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee, "Competition Multigraphs and the Multicompetition Number," Ars Combinatoria 29B(1990), 185192. 2. c. Anderson, K. F. Jones, J. R. Lundgren, and S. Seager, "A Suggestion for New Niche Numbers for Graphs," congressus Numerantium 81(1991), 2332. 3. J. A. Bondy and U. s. R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976. 4. s. Bowser and c. A. Cable, "Some Recent Results on Niche Graphs," Disc. Appl. Math. 30(1991), 101108. 5. , "Cliques and Niche Graphs," Congressus Numerantium 76(1990), 151156. 6 0 c 0 Seager, 231241. Cable, K. F. Jones, J. R. Lundgren, and S. "Niche Graphs," Disc. Appl. Math. 23(1989), 7. J. E. Cohen, "Interval Graphs and Food Finding and a Problem," Rand Corporation 17696PR, Santa Monica 1968. Webs: A Document 8. R. D. Dutton and R. zation of Competition 6(1983), 315317. C. Brigham, "A Character iGraphs," Disc. Appl. Math. 9. P. Erd6s and I. Kaplansky, ''Sequences of Plus and Minus," Scripta Mathematica 12(1946), 7375. 10. P. c. Fishburn, Interval Orders and Interval Graphs, John Wiley and Sons, New York, 1985. 11. P. c. Fishburn and w. v. Gehrlein, "Niche Numbers,'' Journal of Graph Theory 16(1992), 131139. 99
PAGE 109
12. "The Smallest Graphs with Niche Number Three," preprint. 13. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. 14. H. J. Greenberg, J. R. Lundgren, and J. S. Maybee, "Extensions of Graph Inversion to Support an Artificially Intelligent Modeling Environment," Annals of OR 21(1989), 127142. 15. R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 2nd ed., AddisonWesley, Reading, 1989. 16. Phil Hanlon, "Counting Interval Graphs," Trans. Amer. Math. soc. 272(1982), 383426. 17. F. Harary, Graph Theory, AddisonWesley, Reading, 1969. 18. F. Harary, R. z. Norman, and D. cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, John Wiley, New York, 1965. 19. K. A. s. Hefner, K. F. Jones, s. Kim, J. R. Lundgren, and F. S. Roberts, "(i,j)Competition Graphs," Disc. Appl. Math. 32(1991), 241262. 20. R. Honsberger, Mathematical Gems III, The Dolciani Mathematical Expositions 9, Mathematics Association of America, Washington, D.C., 1985. 21. G. Isaak, S.R. Kim, T. A. McKee, F.R. McMorris, and F. Roberts, "2Competition Graphs," SIAM J. Disc. Math. 5(1992), 524538. 22. M.S. Jacobson, "On the pEdge Clique Number of Complete Bipartite Graphs," SIAM J. Math. 5(1992), 539544. Cover Disc. 23. K. F. Jones, J. R. Lundgren, F. s. Roberts, and S. Seager, "Some Remarks on the Double Competition Number of a Graph," congressus Numerantium 60(1987), 1724. 24. S. Kim, Competition Graphs and Scientific Laws for Food Webs and Other Systems, Ph.D. thesis, 100
PAGE 110
I ( I \ I I I Department of Mathematics, Rutgers University, New Brunswick, 1988. 25. "The Competition Number and Its Variants, 11 preprint. 26. J. R. Lundgren, "Food Webs, Competition Graphs, CompetitionCommon Enemy Graphs, and Niche Graphs, 11 in Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, F. s. Roberts(ed.), SpringerVerlag, New York, 1989, 221243. 27. J. R. Lundgren and J. s. Maybee, "A Characterization of Graphs with competition Number m," Disc. Appl. Math. 6(1983), 319382. 28. R. J. Opsut, "On the Computation of the Competition Number of a Graph," SIAM J. Alg. Disc. Math. 3(1982), 420428. 29. C. Rasmussen, Interval Competition Graphs of Sym metric Digraphs and TwoStep Graphs of Trees, Ph.D. thesis, Department of Mathematics, University of Colorado at Denver, Denver, 1990. 30. A. Raychaudhuri and F. S. Roberts, "Generalized Competition Graphs and Their Applications," Methods Oper. Res. 49(1985), 295311. 31. F. s. Roberts, Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems, PrenticeHall, Englewood Cliffs, 1976. 32. "Food Webs, Competition Graphs, and the Boxicity of Ecological Phase Space,'' in Theory and Applications of Graphs, Y. Alavi and D. Lick, (eds.), SpringerVerlag, New York, 1978, 477490. 33. , "On the Compatibility Between a Graph and a Simple order," J. Combin. Theory 11(1971), 2838. 34. , "Applications of Edge Covering by Cliques," Disc. Appl. Math. 10(1985), 93109. 3 5. F. S. Roberts and J. E. Steif, "A Characterization of Competition Graphs of Arbitrary Digraphs," Disc. Appl. Math. 6(1983), 323326. 101
PAGE 111
36. D. Sakai, "Two Results About Niche Graphs," RUTCOR Research Report #RRR 6691, Rutgers Center for Operations Research, New Brunswick, 1991. 37. D. D. Scott, "The competitionCommon Enemy Graph of a Digraph," Disc. Appl. Math. 17 (1987), 269280. 38. s. Seager, "The Double Competition Number of Some TriangleFree Graphs," Disc. Appl. Math. 29 (1990), 265269. 39. "TriangleFree Niche Graphs," preprint. 4 0. "Niche Graph Properties of Trees," prepr int. 41. "The Competition Number of a Graph and the Niche Number of a Graph," unpublished research report, Mount Saint Vincent University, Halifax, N. s., 1990. 42. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, New York, 1973. 43. c. Wang, Competition Graphs, Threshold Graphs and Threshold Boolean Functions, Ph.D. thesis, Department of Mathematics, Rutgers University, New Brunswick,. 1991. 102
