Competition Graphs
by
Brandon Swan
A thesis submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
May 7, 2012
Keywords: Graph Theory, Competition Graphs
Copyright 2012 by Brandon Swan
Approved by
Chris Rodger, Chair, Don Logan Chair of Mathematics
Dean Ho man, Professor of Mathematics
Curt Lindner, Professor of Mathematics
Abstract
A competition graph is a simple graph G that correlates to a digraph D in the following
way.
V(G) = V(D) and
E(G) =
n
fu;vgj there exists x2V(D) for which f(u;x);(v;x)g E(D)
o
:
Competition graphs were originally created in 1968 by Biologist Joel Cohen. In this paper
we discuss four things. First, the use of linear algebra is considered with connection to
competition graphs. Second, we generalize the idea of the competition graph into the m-
step competition graph, and characterize Pn as an m-step competition graph. Third, we
begin to characterize disjoint unions of graphs as m-step competition graphs. And last, we
explore what happens if we treat m-step competition graphs as an in nite sequence, called
a competition sequence.
ii
Acknowledgments
I?d like to thank all of the professors on my committee. Especially my main advisor,
Dr. Chris Rodger.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Binary Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 m-Step Competition Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Completion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5 Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
iv
List of Figures
1.1 Competition Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Economic Competition Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 G with clique cover number 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 m-step Competition Graph Example . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 The adjecency matrix A(D) of a directed graph D . . . . . . . . . . . . . . . . 5
2.2 m-step Digraph Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Neighborhood Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1 Use of adjacency matrices with k = i = 2 . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Ci(D) = Sn for all i2Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3 Digraphs D for which C(D) = P7 . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Example where n 1(mod k). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5 Example where n 2(mod k). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.6 A C6 graph with 3 pendant vertices. . . . . . . . . . . . . . . . . . . . . . . . . 13
3.7 Union of 3 di erent disjoint C4 graphs . . . . . . . . . . . . . . . . . . . . . . . 14
3.8 Union of 4 di erent disjoint C4 graphs and 2 disjoint C5 graphs . . . . . . . . . 16
v
3.9 Digraphs for which C2(D) is the graph above . . . . . . . . . . . . . . . . . . . 16
3.10 Block diagonal adjacency matrix for D for which Cm i(D) =
m[
i=1
(G) . . . . . . . 17
4.1 Competition Sequence of D. Ci = Kn for all i 5 . . . . . . . . . . . . . . . . 18
4.2 Pictoral example for Final Graph Kn . . . . . . . . . . . . . . . . . . . . . . . . 19
4.3 Pictoral example for Final Graph Kn . . . . . . . . . . . . . . . . . . . . . . . . 19
4.4 Example of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.5 Construction of the primitive set . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.6 Digraph D who?s  nal graph is G satisfying all maximal cliques having at least
one vertex not in any other maximal clique. . . . . . . . . . . . . . . . . . . . . 23
4.7 Digraph D who?s Final Graph does not satisfy every maximal clique having at
least one vertex not in any other maximal clique . . . . . . . . . . . . . . . . . 23
5.1 C(D) = C(Dt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2 C(D) = C(Dt) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.3 C(D)6= C(Dt) and C(D)6= C(Dt) . . . . . . . . . . . . . . . . . . . . . . . . . 28
vi
Chapter 1
Introduction
This thesis concerns competition graphs. The Competition Graph G = C(D) corre-
sponding to the directed graph D is the simple graph de ned in the following way.
V(G) = V(D) and
E(G) =
n
fu;vgj there exists x2V(D) for which f(u;x);(v;x)g E(D)
o
:
C(D)D
Figure 1.1: Competition Graph
The concept of competition graphs was  rst introduced by Joel Cohen[5]. Joel Cohen
was a biologist, and his use for competition graphs was to model food webs. The digraph D
would model a food web, and the arcs in this digraph modeled predator/prey relationships.
The edges in the competition graph modeled two animals that shared prey. Due to this origin,
when discussing competition graphs, we often refer to vertices as predators and prey. Vertex
x preys on vertex y if (x;y) 2E(D). Moreover, there are a few assumptions made about
digraphs D because of this application. First, digraphs must be loopless because animals
do not prey upon themselves. Secondly, all digraphs D must be acyclic because cycles do
not occur naturally in the wilderness. It is worth noting, that both of these phenomena
1
have actually occurred in natural food webs, but they are not very common. Moreover,
another possible use for competition graphs is economic graphs. In this case, the digraph
D models asset liability relationships in economic systems. Because of this, we must change
the de nition of the digraph slightly in this model.
E(G) =
n
fu;vgj there exists x2V(D) for which f(x;v);(x;v)g2E(D)
o
D C(Dt)
Figure 1.2: Economic Competition Graph
It is clear to see that this is equivalent to C(Dt) where Dt is the digraph with all arcs
reversed in D. However, early study of competition graphs kept these generalizations in
place. For some of the early work in competition graphs see[12, 10, 5]. The major question
in the early study of competition graphs was which simple graphs G could be realized as
competition graphs? That is to say, given a simple graph G, does there exist a digraph D
for which C(D) = G. It turns out that adding isolated vertices will eventually make it so.
One naturally asks, if G could not be realized as a competition graph, how many isolated
vertices must you add to make G realizable as a competition graph? This number of isolated
vertices required is known as the Competition Number. The competition number of a simple
graph G actually has been fully characterized, but we must introduce two de nitions before
we can state that result.
C lique: A C lique is a complete induced subgraph H of a simple graph G.
C lique Cover: A C lique Cover is a set of cliques in G with the property that every edge
in G lies in at least one clique.
2
C lique Cover Number: The C lique Cover Number,  (G), of a graph G is the minimum
number of cliques required for which G can be covered with  (G) cliques.
G Clique1 Clique2
v1 v1v2
v3 v4
v5
v2
v3 v4 v4
v2
v5
Figure 1.3: G with clique cover number 2
Theorem 1 The competition number of a graph is minf0 ,  (G) jV(G)j+ 2g.
This theorem will be more clear when the application of linear algebra to competition graphs
is discussed.
Theorem 1 essentially ended the discussion on competition graphs themselves, but also led
to the discussion of generalizations of competition graphs. There are many generalizations
of competition graphs, but we are only concerned with two in this thesis.
The  rst generalization is to allow loops and cycles in the digraph D. However, this leads
to a fairly obvious generalization of the previous theorem
Theorem 2 The competition number of a graph is minf0 ,  (G) jV(G)jg if loops and
cycles are allowed in D.
The second generalization is much more exciting. This generalization was  rst introduced
in [4]. If instead of looking at 1-step neighbors for competition, look at the more general
m-step competition graph G = Cm(D) of a digraph D. This changes the de nition in the
following way.
E(G) =
n
fu;vgj there exists x2V(D) for which there exist walks
of length exactly m from both u and v to x
o
3
D
C2(D)
C3(D)
Figure 1.4: m-step Competition Graph Example
This will be the main topic of this thesis. Chapter 2 will introduce the linear algebra
approach to this problem. Chapter 3 will discuss results characterizing paths and cycles
as m-step competition graphs. Chapter 4 will introduce competition graphs as an in nite
sequence. Chapter 5 will discuss further work to be done.
4
Chapter 2
Binary Linear Algebra
There are two approaches to the study of competition graphs: standard graph theory,
and a linear algebra approach. In this chapter we introduce the linear algebra approach.
When using linear algebra, it is appropriate to work over the boolean quasi- eld B. B is a
quasi- eld with the only elements being 0 and 1 in which addition and multiplication are
de ned as usual except that 1 + 1 = 1. So for this entire chapter, assume all math is in B.
Adjacency Matrix: For any directed graph D, the adjacency matrix A = A(D) is the
jV(D)j jV(D)j boolean matrix in which (vi;vj)2E(D) if and only if Ai;j = 1.
D ?
???
???
???
?
011001
001
?
???
???
???
?
A=A(D)
Figure 2.1: The adjecency matrix A(D) of a directed graph D
m-step digraph: An m-step digraph Dm of a directed graph D is a digraph for which
(vi;vj)2E(Dm) if and only if there exists a directed walk of length m from vi to vj in D.
D D2 D3
Figure 2.2: m-step Digraph Example
Obviously the adjacency matrix allows any digraph to be represented by a matrix, and
therefore changes any graph theory problem into a linear algebra problem. However, this is
5
only useful if some good properties hold. The following results are well known and can be
found in most graph theory texts.
Observation 1 Am is the adjacency matrix of Dm
Observation 2 Two digraphs D1 and D2 with adjacency matrices A1 and A2 respectively
are isomorphic if and only if A1 and A2 are isomorphic.
There are also many more nice properties that hold. We will not delve deeply into the
subject, but primitive and prime matrices have shown to be very useful in the study of
competition graphs.
Primitive Matrix: A matrix A is said to be primitive if there exists an integer m for
which Am = J where J is the all 1s matrix.
Prime Matrix: A matrix A is said to be prime if A = B C implies that either B or C
is a permutation matrix.
For more work on prime and primitive matrices, see [7, 13, 6]. There is a very nice
algorithm that will take A, the adjacency matrix of a digraph D, and transform it into C(A)
the adjacency matrix of C(D). First we must notice that if vi;vj;::: all prey upon a vertex
x, then these vertices will all be in competition. Therefore vi;vj;::: will form a clique in
C(D). We will need the de nition of neighborhoods to state this formally.
N+(x) =fvj(x;v)2E(D)g
N (x) =fvj(v;x)2E(D)g
N?(v) N+(v)v
Figure 2.3: Neighborhood Example
6
It follows directly that all vertices in N (x) will form a clique in C(D) for all x2V(D).
This totally exhausts all edges in C(D). This leads to the following algorithmic construction
for C(A), the adjacency matrix for C(D).
1. Start with the 0 matrix
2. Find all vertices in N (v1) =fvi1;vi2;:::g
3. Replace the submatrix M[fi1;i2;:::g;fv1;v2;:::g] with the J matrix.
4. Repeat step 2 for all vi2V(D)
5. Take the resulting matrix and subtract I.
7
Chapter 3
m-Step Competition Graph
This chapter will discuss results achieved regarding paths and cycles charterized as m-
step competition graphs. We will also discuss unions of isomorphic graphs characterized
as m-step competition graphs. We start with some general widely known results regarding
m-step competition graphs.
Proposition 1 Cm(D) = C(Dm)
The following result appeared in [4]. This result is most easily seen by using the information
introduced in the previous linear algebra chapter, as is the following result.
Corollary 1 If G is an m-step competition graph, then G is also a k-step competition graph
if k divides m.
This follows directly from the observation that Cm(D) = Ck(Di) where m = k i, which is
portrayed nicely using adjacency matrices. Let A be the adjacency matrix of the digraph
D for which Cm(D) = G. Then Ai is the adjacency matrix of a digraph Di for which
Ck(Di) = G.
A A A A=A4
A2 A2 =A4
? ? ?
?
Figure 3.1: Use of adjacency matrices with k = i = 2
Theorem 3 Let G be a triangle-free graph on n vertices. If G is an m-step competition
graph for m>n, then G is Sn(the star graph with n vertices.)
8
Theorem 3 was proved in [8]. Without going into details, it was proved that such graphs
must have a "star forcing structure" through a beautiful induction technique. See Figure
3.2 for an example of a digraph D for which Cm(D) = Sn for all values of m.
D C(D)=Sn
Figure 3.2: Ci(D) = Sn for all i2Z
Lemma 1 Pn is an n 1 and an n 2 competition graph.
Pn is the (n 1)-step and (n 2)-step competition graph of the following directed graphs
respectively de ned by
n 1
8>
<
>:
V(D) = fvij1 i ng
E(D) = f(vi;vi+1);(vn 1;v1)j1 i ng
n 2
8>
<
>:
V(D) = fvij1 i ng
E(D) = f(vi;vi+1);(vn 1;v1);(vn 2;vn)j1 i ng
See Figure 3.3 for an example of P7
Theorem 4 Pn is a k-step competition graph if n 1(mod k) or n 2(mod k).
The proof is actually very simple. It uses the previous observation along with Corollary 1.
However, I wish to go a little more into detail, as well as give some direct construction of
these graphs.
9
D1suchthatC6=P7
D2suchthatC5=P7
Figure 3.3: Digraphs D for which C(D) = P7
The  rst construction utilizes linear algebra. If n 1(mod k), obtain the adjacency
matrix A from the  rst digraph presented in Observation 1. Since n  1(mod k), there
exists an integer i for which k i = n 1. Cn 1(D) = Ck(Di) by Corollary 1. Ai will be the
adjacency matrix of Di for which Ck(Di) = Pn. If n 2(mod k), use the second digraph
from Observation 1, and proceed likewise. See Figure 3.4 for an example for P7.
D1suchthatC6=P7 ????
???
???
???
???
???
??
01000000010000
00010000000100
00000101000001
1000000
?
???
???
???
???
???
???
??
A
D2suchthatC3=P7 A2
?
???
???
???
???
???
???
??
00100000001000
00001000000010
10000011100000
0100000
?
???
???
???
???
???
???
??
Figure 3.4: Example where n 1(mod k).
The second construction is a direct Graph Theory construction. Let k i = n 1 or
k i = n 2. The following is a construction for a digraph for which Ci(D) = Pn.
10
D1suchthatC4=P6 ??
???
???
???
???
???
?
010000001000
000100000011
100001100000
?
???
???
???
???
???
??
A
D2suchthatC2=P6
?
???
???
???
???
???
??
001000000100
000011100001
110000010000
?
???
???
???
???
???
??
A2
Figure 3.5: Example where n 2(mod k).
8>
>>>
>>><
>>>
>>>>
:
V(D) = vij1 i n
E(D) =
8
>>>
><
>>>
>:
(vi;vi+k) 1 i n
(vn i;vn i+k+1) 1 i k
(vn 1 k;vn) if n 2(mod m)
This begs the question: could Theorem 4 be strengthened to an if and only if statement?
If not, what are some other values that work? That is a good question.
Theorem 5 Pn is a k-step competition graph if and only if n 1(mod k) or n 2(mod k).
The only if part of this statement was proved in [1].
The proof relies heavily on two de nitions.
Anomaly: In Section 2, we learned that the columns of the adjacency matrix will create
cliques in C(D). Since Pn has clique cover number n 1, there is a bijective function from
the cliques of Pn to n 1 of the columns of A. The other column is referred to as the
anomoly.
Leaf: Since Cm(D) = Pn, There are only two vertices with degree 1. These vertices, l1
and l2, are known as the leaves of a graph. The proof is very long, but the basic construction
11
is to force a certain structure on any digraph D for which Cm(D) = Pn by using these basic
lemmas.
1. Every vertex except maybe  has exactly 2 m-step predators.
2. Every vertex has a 1-step prey, and every vertex except maybe  has a 1-step predator.
3. If a pair of vertices share 2 m-step prey, one of these prey is  .
4. No vertex has 3 m-step predators.
5. If a vertex has 3 m-step prey, one of those prey is  .
6. If x has only one m-step prey, then x is a leaf.
7. If Ni(u) Ni(v) for any i m then u is a leaf.
8. If every m-step predator of x is also an m-step predator of y, then either x or y is  .
9. If two vertices share a k-step prey, they will share an m-step prey as well.
These statements are proved as follows.
1. These 2 m-step predators correspond to the cliques of Pn.
2. If x had no 1-step prey, x would not be in competition with any other vertex. If x has
no 1-step predator, then it wouldn?t have 2 m-step predators.
3. All vertices correspond to di erent cliques in the graph. Since these 2 m-step prey
create the same clique, one of them is not needed in the bijective function from the
cliques to the vertices. Pick either column and call it  .
4. This follows because Cm(D) is triangle free.
5. If none were  , Cm(D) would have a claw.
6. A more generalized concept will be proved in (7).
12
7. u is adjacent to v in Cm(D). If u was adjacent to another vertex w, then v would be
adjacent to w creating a triangle in Cm(D).
8. Use a similar observation to that in (3).
9. If two vertices share a k-step prey, that prey has a 1-step prey. By induction, the two
vertices will share an m-step prey as well.
3.1 Unions
The next section will cover taking the union of k di erent isomorphic graphs. We start
with the Cn graph.
Theorem 6 The spiked cycle is an m-step competition graph if and only if m = 1.
This includes Cn itself. See Figure 3.6 an example of a spiked cycle with 3 pendant vertices.
Figure 3.6: A C6 graph with 3 pendant vertices.
This was proved in [4]. The proof is in uenced heavily by linear algebra. Using some
results from [6], it can be found that any such digraph D for which C(D) is a spiked cycle
must have a prime adjacency matrix.
This statement can be generalized to the union of m di erent cycles. For the following
theorem, take
m[
i=1
(Cn) to mean the union of m vertex-disjoint Cn graphs.
Theorem 7
m[
i=1
(Cn) is a k-step competition graph if and only if k divides m.
13
3uniondisplayi=1C4
Figure 3.7: Union of 3 di erent disjoint C4 graphs
Since Cm(D) will need to be
k[
i=1
Cn, we know a few things about D. Since the clique
cover number of
k[
i=1
Cn is k n, we know there is a bijective function from every vertex in D
to the cliques in Cm(D). This leads to the following observations.
1. For every vertex v, d+(v) 1.
2. For every vertex v, d+(v) 2.
3. For every vertex v, d (v) 1.
4. For every vertex v, d (v) 2.
5. If N+(u) N+(v) then u = v.
For (1), since every vertex is in competition in Cm(D), every vertex must have an
outgoing edge, else it would not be in competition. For (3), if a vertex had no in-degree,
then it would have no m-step predators, contradicting the bijection from the edges to the
vertices. For (2), if a vertex v had out degree 3 or higher, then it would have 3 or more
out degree neighbors in D. This would create a claw in Cm(D). For (4), if a vertex v had
in-degree 3 or higher, there would be a triangle in Cm(D). For (5), u will be in competition
with v in Cm(D). If u was in competition with another vertex w, v would be in competition
with w too causing a triangle in Cm(D). So u can only be in competition with v, which is a
contradiction of the cycle structure.
It is possible to partition the vertices into two sets. V2 =fvjd+(v) = 2g and V1 =fvj
d+(v) = 1g. It is also possible to decompose V1 even further into
14
V1;i =fvjd+(v) = 1 And the shortest walk from v to some vertex u2V2 has length ig:
For emotionally satisfying reasons call V1;0 = V2. Clearly v2V1;i can only be adjacent to
some vertex u2V1;i 1. But how many of these V1;i are non-empty? And how big are they?
This leads to the following observations.
a. V1;i = ; for all i m.
b. v2V2 may only be adjacent to some vertex u2V1;m 1.
c. jV1;ij=jV1;jj for all 0 i;j m 1.
For (a), if i m, then v would only have 1 m-step neighbor, contradicting the cycle
structure. For (b), suppose v2V2 was adjacent to some v2V1;i for i < m 1. Then, by
(5), v would have 3 m-step neighbors, contradicting (2). For (c), without loss of generality,
we can assume jV1;ij6=jV1;i 1j. There are two cases.
Case 1: jV1;ij>jV1;i 1j. In this case, two vertices must be adjacent to the same vertex
by the pigeon hole principle, but this contradicts (5).
Case 2: jV1;ij<jV1;i 1j. In this case, there must be one vertex in V1;i 1 with in-degree
0, contradicting (3).
Due to the cyclic nature of D, v2V1;i can only be in competition to some other u2V1;i
in Cm(D). Moreover, these graphs will all be isomorphic. Therefore m must clearly divide
the number of cycles there are, which is k.
This proof can be expanded a little bit in the following way. Let
k[
i=1
mk[
i=1
(Cni) be the
disjoint union of m1 Cn1 graphs, m2 Cn2 graphs and so on.
Corollary 2
k[
i=1
mk[
i=1
(Cni) is a j-step competition graph if and only if j divides
g = GCD(m1;:::;mk).
15
This theorem follows directly from the proof above. The digraph constraints are the same
from above. See Figure 3.8 for an example of this.
2uniondisplayi=1C5
GCD(4,2)=2
4uniondisplayi=1C4
Figure 3.8: Union of 4 di erent disjoint C4 graphs and 2 disjoint C5 graphs
Figure 3.9: Digraphs for which C2(D) is the graph above
The next step is to generalize this theorem to spiked n cycles. Instead, let?s generalize
to any graph G as best we can.
Theorem 8 Let G be any j-step competition graph.
m[
i=1
(G) is a k-step competition graph if
k divides m * j.
The proof involves the construction of a diagonal matrixAthat is the adjacency matrix
of a digraph D for which Cm j(D) =
m[
i=1
(G). This construction along with Corollary 1 proves
the theorem. In this digraph, let A be the adjacency matrix of DG for which Cj(DG) = G.
Also let n =jV(G)j.
16
A=
?
???
???
???
???
???
???
???
???
?
0nA0n...... 0n0n0nIn 0n... 0n
... ... ... ... ... ...... ... ... ... ... ...
... ... ... ... ... ...I
n0n......... 0n
?
???
???
???
???
???
???
???
???
?
Am?i=
?
???
???
???
???
???
???
???
???
?
Am0n ......... 0n0n Am0n...... 0n
... ... ... ... ... ...... ... ... ... ... ...
... ... ... ... ... ...0
n ... ...... 0nAm
?
???
???
???
???
???
???
???
???
?
n?m
n?m
n?m
n?m
Figure 3.10: Block diagonal adjacency matrix for D for which Cm i(D) =
m[
i=1
(G)
17
Chapter 4
Completion
So far competition graphs have been restricted to one value m. Let us now observe
an in nite sequence of competition graphs. This sequence C(D);C2(D);::: is called the the
C ompetition Sequence of a graph D. Sometimes, for a certain value k, G = Ck = Ck+1 = :::.
This G is called the F inal Graph of the Competition Sequence. A generalized idea of this,
known as a competition index, was introduced and studied in [3, 2, 11].
Competition Index: When you look at the competition sequence of a digraph D, the
length between the  rst repeated graphs in the sequence is known as the index of D.
The  nal graph is a special where competition index = 1.
D C(D) C2(D)
C3(D) C4(D) C5(D)
Figure 4.1: Competition Sequence of D. Ci = Kn for all i 5
Observation 3 If Kn or Kn ever appears in a Competition Sequence, it will be the  rst
instance of the Final Graph.
If Ck(D) = Kn, every vertex is in competition with some vertex, therefore no vertex has
out-degree 0. If vertices u, and v are in competition, then there exists a vertex x for which
f(u;x);(v;x)g E(Dk). x has a prey, call it y. Therefore f(u;y);(v;y)g E(Dk+1).
18
mSteps
m+1Steps
Figure 4.2: Pictoral example for Final Graph Kn
If Ck(D) = Kn, we will prove by contradiction. If u and v are in competition in Dl for
l > k. Without loss of generality we can say l = k + 1. There exists vertices u,v, and x
for which there is an l-step path from both u to x and v to x. The second vertices on each
path will be in competition in Dk. If these vertices are not unique, then u and v will be in
competition in Dk. Either way, this contradicts Ck(D) = Kn.
isteps
msteps
m+isteps
Figure 4.3: Pictoral example for Final Graph Kn
It?s pretty clear that a cycle-free digraph D will have Final Graph Kn. However, there
are non acyclic digraphs D with Final Graph Kn. Also, there are digraphs that have  nal
graphs other than Kn or Kn. One naturally asks a few questions.
1. Can we classify digraphs D with Final Graph Kn?
2. Can we classify digraphs D with  nal graph Kn?
19
3. Can we classify simple graphs G, for which G is the Final Graph of some digraph D?
4. Can we  nd some upper and lower bounds for when the Final Graph will be reached?
Question four suggests another de nition. The C ompletion Number of a digraph D is
the smallest integer k for which Ck(D) = G, where G is the Final Graph of D.
To answer Question 1, we must de ne a Primitive Graph, and a Primitive Set.
Primitive Digraph: A digraph D is primitive if there exists an integer k for which at
Dk = Kn. A digraph D is primitive if an only if its adjacency matrix is primitive.
Primitive Set: A primitive set is an induced subgraph C D for which C is a primitive
digraph.
Lemma 2 If C(D) = Kn, there exists a vertex, ve, for which there exists an n 1 path from
every vertex v2v(D) to ve.
We know that since C(D) = Kn, given any two vertices u and v, there must be a third
vertex x(maybe not distinct) for whichf(u;x);(v;x)g E(D). We will create an algorithm
that will  nd the vertex ve.
1. Arbitrarily label all vertices in the graph vi distinctly, call V(G) = V0.
2. Form a set V1 as follows: for every pair of vertices vi and vi+1 arbitrarily chose one
vertex v1i for which vi and vi+1 both prey upon v1i . Place v1i in V1.
3. Repeat to create Vi+1 from Vi until you reach Vn 1.
A few observations must be made. While, v1i may be equal to some v1j for some i6= j, this
is  ne because we?re  nding walks, not paths or trails. Also, at every step, jVij=jVi 1j 1.
(When determining the size of these multisets, repetitions of elements are counted multiple
times). Therefore, for jV(D)j = jV0j = n, we know jVn 1j = 1. This vertex, vn 11 = ve,
satis es the lemma.
20
...
...
v1 v2 v3 vn?1 vn
vprime1 vprime2 vprimen?1
v(n?1)1 v(n?1)2
v(n)
Figure 4.4: Example of the Algorithm
Theorem 9 C(D) = Kn if and only if D contains a primitive set P. Moreover, for every
vertex v2V(D) there exists a vertex p2V(P) for which (v;p)2E(D).
Take the vertex from the previous lemma and call it v. We must build a primitive set,
we will start with v and N+(v). For all u2N+(v), there exists a n 1 walk from u to v. v,
N+(v) and all vertices in these walks will make the the primitive set.
v(n)
v(n)
...N+(v(n?1))
v
PrimitiveSet
Figure 4.5: Construction of the primitive set
21
We must  nd an integer i for which there exists a walk from any vertex u to any other
vertex w in our primitive set. Moreover, this walk may only contain vertices in the primitive
set. Since C(D) = Kn, every vertex must be adjacent to v in C(D). So therefore we know,
every vertex u2V(G) must be adjacent to some vertex w2N+(v). Therefore, any vertex
in our primitive set may go to N+(v) and stay there as long as it wants. We know that
you can get from any vertex u2N+(v) back to v with a walk of length n 1. Moreover,
this walk only uses vertices in our primitive set. However, we need to be able to reach any
vertex, not just v. Chose a length of 2n 1 for these walks. All vertices in our primitive set
will be on some trail from u2N+(v) to v. Moreover, this vertex can?t be the (n 1)th or
larger vertex in this trail, because that vertex is v. Let u be the ith vetex on some trail for
i<n 1. To get to u in 2n 1 steps, walk around N+(v) for n i steps, then follow the trail
to v in n 1 steps, then get back into N+(v) by the vertex that starts the trail containing u.
Follow this trail for i steps to reach u. All together this trail was (n i)+(n 1)+i = 2n 1
steps.
So C(D) = Kn implies that D has a primitive set and that every vertex will be adjacent
to some vertex in the primitive set. So therefore if Cm(D) = Kn, D will have a primitive
set, because a set will either always be primitive or never be primitive. Also, every vertex
will reach the primitive set in m steps.
Moreover, from this proof, it is easy to see that Cm(D) = Kn at most 2n 1 steps
before the primitive set is J. So any bound for a primitive set becoming J is also a bound
for a digraph D completing to its  nal graph of Kn. Furthermore, we can subtract at most
2n 1 from all natural bounds of primitive bounds.
The next observation is in regards to question three.
Observation 4 A simple graph G is the  nal graph of some digraph D if every maximal
clique of G has at least one vertex exclusive to that maximal clique.
22
The following is a construction for D that satis es the observation. Let Pi be the vertices
that are unique to maximal clique i. Form those vertices into a primitive set. Let vertices
in more than one maximal clique be adjacent to all Pi for which v2Ki.
G=
?1?
2
?i
...
P1
P2
Pi
...
CliquesofG DisjointPrimitiveSets
Verticesinmorethanoneclique
Figure 4.6: Digraph D who?s  nal graph is G satisfying all maximal cliques having at least
one vertex not in any other maximal clique.
However, the only if part of this statement is false.
False Conjecture 1 A simple graph G is the  nal graph of some digraph D only if every
maximal clique of G has at least one vertex exclusive to that maximal clique.
See Figure 4.7 a counterexample.
D C(D) IsomorphicC(D)
Figure 4.7: Digraph D who?s Final Graph does not satisfy every maximal clique having at
least one vertex not in any other maximal clique
23
This graph is also a counterexample to another conjecture about Question 2.
False Conjecture 2 If a digraph D has no primitive set, then the  nal graph of D is Kn:
The previous graph also disproves this statement, because the digraph from the previous
graph contains no primitive set.
There are many results on bounds for primitive graphs, and every one of those bounds is
also a natural bound for the completion number. For more information see [7, 13]. However
one would expect that the completion number would be strictly less than the primitive num-
ber. One interesting question is: given the set of graphs D that have the same competition
graph, what are the range of completion numbers of these graphs? This brings on a few
de nitions
Biome: Given a simple graph G. The biome of G, BG, is the set of all digraphs D for
which C(D) = G.
C ompetition Range: Given a biome,  nd the completion numbers for all digraphs D
in said biome. The lower and upper bounds of these completion numbers are known as the
completion range.
Theorem 10 For Cn, the upper bound in the completion range is bn=2c. And for odd Cn
the lower bound is blog2(n)c.
From earlier theorems, we know a few things about any digraph D for which C(D) = Cn.
1. d+(v) = d (v) = 2 for all v2V(G)
2. N+(v) N+(u) implies that u = v.
Observation 5 If d+(v) >bjV(G)j2 c, then C(D) = Kn
Since all v are adjacent to more than half of the vertices in G, they must share at least
one vertex by the pigeon hole principle.
24
Observation 6 m+ 1 jN+(v)j2Dm 2m
By (1), every vertex starts o with 2 neighbors. Each of these neighbors has 2 neighbors,
so 2m is an obvious upper bound. However, by (2), these 2 neighbors must yield at least 3
2-step neighbors. Generalize this idea to get m+ 1 as a natural lower bound.
So these bounds naturally give the bounds in the theorem, but can we actually reach
these bounds? The following is a construction for a graph that will reach the upper bound
for all Cn.
8
><
>:
V(D) = fvij1 i ng
E(D) =
n
(vi;vi)[(vi;vi+1)
o
The following is a construction of a digraph that will reach the lower bound for odd Cn.
8>
<
>:
V(D) = fvij1 i ng
E(D) =
n
(vi;v2i)[(vi;v2i+1)
o
Obviously this will reach the bound, however, is C(D) = Cn? If n is even, then C(D) will
be a perfect matching. However, when n is odd, vi will be adjacent to vi+bn/2c and vi+dn/2e
This is equivalent to takingbn2cas a generator in the groupZn, which will generate every i
because bn2c and n are relatively prime..
25
Chapter 5
Questions
This concludes the extent of our information on the subject of competition graphs.
However there is much more work to be done. The following is a list of some interesting
questions.
1. If the clique cover number of a graph G isjV(G)j, does this imply that G can only be
realized as a 1-step competition graph?
This is true for Cn and the spiked cycle. Any proof must use a bijective function
from the vertices to the cliques of G. Forcing a prime matrix construction has been a
useful technique in previous results, and may prove to be fruitful in the future. For an
example of how this is done see [4]. For more information on prime matrices see [6].
2. Can we  nd a complete characterization of digraphs D for which the  nal graph of D
is Kn?
The original thought was that G would have Final Graph Kn if and only if D had no
primitive set. The original thought was disproved by Figure 4.7.
3. Can we make a complete characterization of graphs G for which G is the  nal graph
of some digraph D?
The original thought was disproved by 4.7.
4. Can we  nd completion range?s for more graphs?
This seems to be a very hard problem to generalize. The only result so far is Cn
5. Is Proposition 8 an only if statement as well?
26
6. Can we  nd a complete characterization of trees as m-step competition graphs? This
seems to be a very hard problem to generalize. The proof for paths alone took more
than 10 pages to prove, and it was very speci c to the exact structure of Pn.
7. Given a Biome B(G), What graphs lie within fC(Dt)jD2Bg.
Sometimes C(Dt) = C(D). Other times C(Dt = C(D). And rarely, C(Dt) seems to
have nothing to do with C(D) altogether. The following are examples of each of these
cases.
D C(D) Dt C(Dt)
Figure 5.1: C(D) = C(Dt)
D C(D) Dt C(Dt)
Figure 5.2: C(D) = C(Dt)
27
D C(D)
Dt C(Dt)
Figure 5.3: C(D)6= C(Dt) and C(D)6= C(Dt)
28
Bibliography
[1] E. Belmont, \A Complete Characterization of Paths that are m-step Competition
Graphs," Discrete Applied Mathematics, 159 (2011), 1381{1390.
[2] H.H. Cho, H.K Kim, \Competition Indices of Strongly Connected Digraphs," Bull.
Korean Math. Soc, 48 (2011), 637{646.
[3] H. H. Cho and H. K. Kim, \Competition indices of digraphs," Proceedings of workshop
in combinatorics, 99 (2004), 96{107.
[4] H.H. Cho, S.-R. Kim, and Y. Nam, \The m-step competition graph of a digraph,"
Discrete Applied Mathematics, 105 (2000), 115{127.
[5] J.E. Cohen, \Food Webs and Niche Space," Princeton University Press, (1978).
[6] D. De Caen, \Primes in the Semigroup of Boolean Matrices," Linear Algebra and its
Applications, 37 (1981), 119.
[7] E. Robert Hartwig and Michael Neumann, \Bounds on the exponent of primitivity
which depend on the spectrum and the minimal polynomial," Linear Algebra Appl.,
184 (1993), 103{122.
[8] G. Helleloid, \Connected triangle-free m-step competition graphs," Discrete Applied
Mathematics, 145 (2005), 376{383.
[9] Wei Ho, \The m-step, same-step and any-step competition graphs," Discrete Applied
Mathematics, 152 (2005), Pages 159-175.
[10] Kim A. S. Hefner, Kathryn F. Jones, Suh-Ryung Kim, J. Richard Lundgren, Fred S.
Roberts, \(i, j) competition graphs," Discrete Applied Mathematics, 32 (1991), 241-262.
[11] H. K. Kim, \Competition indices of tournaments," Bull. Korean Math. Soc, 45 (2008),
385{396.
[12] Suh-Ryung Kim, Terry A. McKee, Fred R. McMorris, Fred S. Roberts, \p-Competition
Numbers," Discrete Applied Mathematics. 46 (1993), 87-92.
[13] S.W. Neufeld, \A diameter bound on the exponent of a primitive directed graph," Linear
Algebra and its Applications, 245 (1996), 27-47.
29