
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00005732/00001
Material Information
 Title:
 Competition graphs and their generalizations
 Creator:
 McKenna, Patricia A
 Publication Date:
 1994
 Language:
 English
 Physical Description:
 vii, 47 leaves : illustrations ; 29 cm
Subjects
 Subjects / Keywords:
 Graph theory ( lcsh )
Algorithms ( lcsh ) Algorithms ( fast ) Graph theory ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 4547).
 General Note:
 Submitted in partial fulfillment of the requirements for the degree, Master of Science, Applied Mathematics.
 Statement of Responsibility:
 by Patricia A. McKenna.
Record Information
 Source Institution:
 University of Florida
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 31508826 ( OCLC )
ocm31508826
 Classification:
 LD1190.L622 1994m .M35 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
COMPETITION GRAPHS
AND THEIR GENERALIZATIONS
by
Patricia A. McKenna
B.A., Potsdam College of the State University of New York, 1988
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Applied Mathematics
1994
This thesis for the Doctor of Philosophy
degree by
Patricia A. McKenna
has been approved for the
Department of
Mathematics
by
Stanley E. Payne
McKenna, Patricia A. (M.S., Applied Mathematics)
Competition Graphs and Their Generalizations
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
The concept of the competition graph has been extensively studied and gen
eralized since its introduction in the late sixties. We consider the generalizations
known as the pcompetition graph and the ^tolerance competition graph. We
identify the chordal graphs on 3 or more vertices as 3competition graphs. We
identify some graphs which are the pcompetition graphs of loopless Hamiltonian
or loopless strongly connected digraphs. Next, using a construction of Myciel
ski as well as other methods, we generate large classes of graphs which fall into
one category but not another. For example, we construct large classes of graphs
which are mintolerance competition graphs but not competition graphs. We also
present an algorithm for generating graphs which are competition graphs but not
2competition graphs.
This abstract accurately represents the content of the candidates thesis. I rec
ommend its publication.
Signed
in
Contents
1 Introduction.................................................. 1
2 p Competition Graphs......................................... . 5
2.1 Preliminaries .............................................. 5
2.2 3Competition Graphs of Arbitrary Digraphs.................. 7
2.3 p Competition Graphs of Loopless Hamiltonian and Strongly Con
nected Digraphs............................................... 11
3 Tolerance Competition Graphs.................................. 14
3.1 Preliminaries ............................................. 14
3.2 MinTolerance Competition Graphs........................... 16
3.2.1 The Basics........................................... 16
3.2.2 MinTolerance Competition Graphs and a Construction of
Mydelski ............................................ 18
3.3 MaxTolerance Competition Graphs........................... 28
3.4 SumTolerance Competition Graphs........................... 29
3.5 Two^Tolerance Competition Graphs......................... 31
3.5.1 {0,?}^Tolerance Competition Graphs................. 33
3.5.2 1Competition Graphs Which Are Not 2Competition Graphs 36
3.5.3 Creating 1competition graphs which are not 2competition
graphs.............................................. 39
3.5.4 More on 1competition graphs which are not 2competition
graphs.................................................. 41
4 Conclusion ................................................ 43
v
List of Figures
1 G is the competition graph of D. Note that the inset of any vertex
in D forms a clique in G. ................................ 1
2 G is the 8competition graph of D. Note that the inset of any vertex
in D does not necessarily form a clique in G.................. 5
3 Si, S2, and S3 form a 2ECC for G................................ 6
4 G of Figure 8 is the 2competition graph of D.................. 6
5 G is a maxtolerance competition graph.......................... 15
6 D is the digraph for which G is the maxtolerance competition graph. 16
7 G is a mintolerance competition graph.......................... 17
8 Is this graph a mintolerance competition graph?................ 18
9 fi{Cs), also known as Grotzschs graph.........,.............. 19
10 n{CA)........................................................... 20
11 fi(C3)........................................................ 21
12 p(KA)........................................................... 22
13 G is a sumtolerance competition graph.......................... 29
14 The complete bipartite graph, Jif3i3.......................... . 30
15 The complete bipartite graph K2,6............................... 32
16 The graphs G and (GM)\Jl2...................................... 34
17 G is a maxtolerance competition graph.......................... 35
vi
18 G is not a 1competition graph and not a 2competition graph. . 37
19 Graphs which are 1competition graphs and not 2competition graphs. 39
20 A graph which is a 2competition graph of an arbitrary digraph
with loops, but not of a digraph without loops.................. 43
vu
1 Introduction
Competition graphs were first introduced by Joel Cohen in 1968 [5] in relation
to food webs. Since then, the topic has been extensively studied and generalized,
proving to be an area of research in which graph theorists have been limited only
by their imaginations.
For basic graph theory definitions and terminology, the reader is referred to
Roberts [16]. Basic knowledge of competition graphs is helpful before proceed
ing to generalizations such as pcompetition graphs (Chapter 2) and ^tolerance
competition graphs (Chapter 3). We will start with the definition.
The competition graph of a digraph D = (V,A) is the graph G = (V,E) where
[x,y] Â£ E if and only if 3 z Â£ V such that both (, z) and (y, z) Â£ A.
Example 1 Graph G of Figure 1 is the competition graph of digraph D.
a b c a b c
D:
fed fed
Figure 1: G is the competition graph of D. Note that the inset of any vertex in D
forms a clique in G.
A collection C of sets of vertices from a graph G is called an edgeclique cover
(ECC) of G if each set in C is either a (not necessarily maximal) clique or the
1
empty set, and every edge in G is in at least one of the cliques of C. The number
of cliques in a smallest edgeclique cover is the edgeclique cover number of G,
denoted 0e(G). In studying competition graphs, the importance of the edgeclique
cover number can not be overstated, as we will see next.
The following list summarises those facts about competition graphs which are
most relevant (and sometimes analogous) to topics in later chapters. Some can
be modified to apply to pcompetition graphs and/or ^tolerance competition
graphs. All are referred to in later chapters.
Fact 1 [1] A graph G is a competition graph of an arbitrary digraph
if and only if 0e(G) < n.
Fact 2 [17] A graph G with n vertices is the competition graph of
an arbitrary digraph without loops if and only if G is not K2 and
de(G) < n.
Fact 3 [6] A graph G of order n is the competition graph of a
Hamiltonian digraph if and only if G has a labeling oi, 02,..., on of
its vertices and an edgeclique cover Ci,C2,.. .,Cn satisfying a, Â£
C,, 1 1,..., A,* ^ , z 1,..., 71 1, and
Fact 4 [6] If G is a cycle, then G is the competition graph of a
Hamiltonian digraph.
2
Fact 5 [6] If G is a tree on n > 3 vertices, then G is the competition
graph of a Hamiltonian digraph.
Fact 6 [6] If G is a tree plus an edge, with V(G) > 3, then G is
the competition graph of a Hamiltonian digraph.
Fact 7 [6] If G is a connected trianglefree graph on n > 3 vertices
with 0e(G) < n, then G is the competition graph of a Hamiltonian
digraph.
Fact 8 [6] The complete graph Kn for n > 3 is the competition
graph of a Hamiltonian digraph.
Fact 9 [6] If G is a chordal graph on n > 3 vertices, then G is the
competition graph of a Hamiltonian digraph.
Fact 10 [6] If V(G) = n then G is the competition graph of a
strongly connected digraph if and only if 0e(G) + i(G) < n (where
z(G) is the number of isolated vertices in G).
In the chapters that follow we will use variations of the facts above to explore
generalizations of the competition graph. We will present results analogous to
Facts 35 and 810 for pcompetition graphs. Finally we will discuss the ways in
which the facts above suggest further research.
In closing, it is worthwhile to make brief mention of some variations of the com
3
petition graph which are neither explored nor generalized here. These are the
competitioncommon enemy graph and the niche graph, which are the topics of
Scott [18] and Cable, Jones, Lundgren, and Seager [4] respectively. Generaliza
tions of these concepts are mentioned in Chapter 4 as possible areas for future
research.
4
2 p Competition Graphs
2.1 Preliminaries
The pcompetition graph was first introduced in 1989 by Kim, McKee, McMorris,
and Roberts [9]. The pcompetition graph of a digraph D = (V,A) has vertex set
V and an edge between x and y if and only if there are distinct vertices oi,..., ap
and arcs (s, o,) and (y, a,) in D for each i
graph has an edge between two vertices if and only if those two vertices compete
for at least p vertices in the digraph. Graph G of Figure 2 is the 3competition
graph of D.
Figure 2: G is the 3competition graph of D. Note that the inset of any vertex in
D does not necessarily form a clique in G.
We now define the notion of a pedge clique cover (or pECC) of a graph G. Let
F = {Si,..., Sr} be a family of subsets of V(G), with repetition allowed. F is a
pECC of G if for every set ii,... ,ip of p distinct subscripts, T = S,, f) D SiP
is either empty or induces a clique of G, and the collection of sets of the form T
5
covers all edges of G.
Finally, we define the notion of pedge clique cover number (denoted 0fj), which
is the smallest r for which for which there is a pECC of cardinality r.
Example 2 For G shown in Figure 3, we have the following 2ECC:
Si by c}, 1S2 Cj (1}, and S3 (fl, 6, c, <
a b
Figure 3: Si, S2, and S3 form a 2ECC for G.
We use this 2ECC to create D (see Figure 4), by letting each set of the 2ECC
be the inset of a vertex in the digraph.
a b
D:
d c
Figure 4: G of Figure 3 is the 2competition graph of D.
In this case we have In(d) = Si, In(6) = 52> and In(a) = S3
The following theorem is due to Kim, McKee, McMorris and Roberts [9], and al
lows us to identify a graph as a pcompetition graph without actually constructing
the digraph D.
6
Theorem 1 A graph G with n vertices is a ^competition graph of an arbitrary
digraph if and only if 8%(G) < n.
In this chapter we will focus first on the case where p = 3, identifying some
classes of graphs which are 3competition graphs of arbitrary digraphs. Next
we will place certain restrictions on D, such as loopless Hamiltonian and loopless
strongly connected, and discuss various classes of graphs which are pcompetition
graphs of such digraphs.
2.2 3Competition Graphs of Arbitrary Digraphs
In response to the question, Are there interesting families of graphs which are
3competition graphs of arbitrary digraphs? posed by Kim et a!. [9], we have
identified chordal graphs as such. There are just three exceptions: the paths on
3,4, and 5 vertices (P3, A, and Ps respectively). Simple counting arguments show
that these graphs are not 3competition graphs. For example, consider P4 with
vertices labeled consecutively vi,V2v3,u4. A minimum covering of edges [uj,v2\
and [v2,v3] requires the following four sets: {1^, n2}, {v*, u2, n3}, {ua, v2, u3}, {v2, y3}
We cannot cover the edge [u3,4] by simply adding v4 to the three sets containing
z/3, since we would create the unwanted edge [i>2)V4]. So we are required to add a
fifth set, and our minimal 3ECC of P4 is {ui,'u2}, {ui,u2,u3}, {t>i,r72, v3,r>4},
7
{^3,^4}. We conclude that 03{P4) = 5 > 4, i.e. P4 is not a
3competition graph. Analogous proofs for P3 and P5 are left to the reader.
The following lemmas are required to prove that the remaining chordal graphs
are 3competition graphs.
Lemma 1 Every path on 6 or more vertices is a 3competition graph.
Proof: The following sets form a 3ECC for Pn, n > 6, when the vertices of Pn
are labeled consecutively V\,v2,... ,vn:
51 = {vi,v2,vni,vn}
52 = {vi,v2,v3}
53 = {vuv2,v3,v4}
Si =
Sfil = 3 j ^n2 j ^n1 j ^n}>
Sn = 2>^n1j^n} ^
Lemma 2 Every tree T on 5 or more vertices that is not a path has a pendant
vertex, x, such that T{s} is not a path.
Proof: Let T be a tree on n > 5 vertices that is not a path. We need only
consider the case that T is the path vj, v2, ..., with one final vertex,un,
which is adjacent to exactly one of the v.s, 2 < z < n 2.
8
If us neighbor is vi or v_2 then n_i or uj respectively is the pendant vertex
whose removal does not create a path. Finally, if ns neighbor is vj, 3 < j < n3,
then either Vi or un_i is removable without creating a path.
Lemma 3 Every chordal graph G which is not a tree has at least k + 2 vertices,
where k is the number of nontrivial maximal cliques of G.
Proof: We proceed using induction on n = F(G).
Base case: n = 3 implies G is K3,I3, or K2 U 7i, so clearly the lemma holds.
Assume that for every chordal graph on fewer than n vertices that is not a tree,
the lemma holds. Let G be such a graph on n vertices. We must show n> k + 2.
Since G is chordal, we know G has a simplicial vertex, i.e. a vertex whose
neighborhood is a clique. Call that vertex x. Let G; = G {x}. G' is a chordal
graph on n 1 vertices. Let k' be the number of maximal cliques in G'.
Case i: G' is a tree.
Then k' is simply the number of edges in G', which is (n 1) 1 = n 2. Since
G' is a tree, and G is not, we know that x is in a maximal clique of size three
in G, and its two neighbors form a clique in G', thus G has the same number of
maximal cliques as G'. That is, k = n 2, or n = k + 2. So certainly n > k + 2.
Case ii: G' is not a tree.
Then the induction hypothesis holds for G', and we know n 1 > k' + 2, which
implies n > W + 3. We know one of the following is true: k! = k or k' = k 1.
9
We conclude that n > k + 2.
Thus every chordal graph which is not a tree has at least k + 2 vertices.
Theorem 2 Every chordal graph G on n > 3 vertices that is not P3,P4,or P5 is
a 3competition graph.
Proof: Case i: G = P, n > 6. Then G is a 3competition graph by Lemma 1.
Case ii: G is a tree that is not a path.
We use induction on n to prove that G is a 3competition graph. Our base case
is n = 4, since there are no trees on 3 vertices other than P3. When n = 4, G is
which was shown to be a 3competition graph in Figure 2.
Assume all trees on less than n vertices that are not paths are 3competition
graphs. Let G be such a tree on n vertices. By Lemma 2, there exists a vertex
x in G such that G' = G{2} is not a path. G' is a 3competition graph by
induction hypothesis. Let y be the one neighbor of x in G. Surely y is listed in
at least 3 of the sets of a 3ECC of G' of size at most n 1. We create a 3ECC
of G of size at most n by adding x to 2 of those sets containing y, and adding a
final set {x,y}. Therefore G is a 3competition graph.
Case Hi: G is not a tree.
Let Ci, 1 < i < fc be the k nontrivial maximal cliques of G. Consider the following
sets: Si = V(G), S2 = S3 = Ci, S4 = C2, j Sjt+2 = Ck These k + 2
sets form a 3ECC for G, and by Lemma 3, we know n > k + 2.
10
The three cases above convince us that every chordal graph on 3 or more vertices
that is not P3, P4, or P5 is a 3competition graph.
Since interval graphs are chordal, we have the following corollary of Theorem 2.
Corollary 1 Every interval graph on three or more vertices that is not ft, ft?
or Ps is a 3competition graph.
2.3 p Competition Graphs of Loopless Hamiltonian and
Strongly Connected Digraphs
The results presented in this section are due to Langley et al. [10] and are anal
ogous to some of the previously mentioned facts about competition graphs. We
begin by characterizing some large classes of graphs which are the pcompetition
graphs of loopless Hamiltonian digraphs, and we conclude with a sufficient con
dition for a graph to be the pcompetition graph of some strongly connected
loopless digraph for p > 2.
Theorem 3 Let p > 2. Every cycle on n > p + 3 vertices is the pcompetition
graph of a loopless Hamiltonian digraph.
This result is rather easily proved by constructing the digraph for which the cycle
is the pcompetition graph. The following result is not as readily proved.
Theorem 4 Let p > 2. If T=(V,E) is a tree on n > 2p vertices, then T is the
pcompetition graph of a loopless Hamiltonian digraph.
11
Often mathematical induction is a handy tool in proving results on trees. However
in the previous theorem, as p grows, so does n > 2p, giving us unmanageable
base cases for induction for large p. So the proof in [10] involves several lemmas
and has a constructive flavor.
If we restrict ourselves to the case when p = 2, then we arrive at the following
result via some lemmas (one of which is proved by induction).
Theorem 5 H G is a chordal graph on n > 5 vertices, then G is the 2competition
graph of a loopless Hamiltonian digraph.
In attempts to prove a similar result for greater p, we again have a problem using
induction since base cases become increasingly difficult to handle as p grows.
The next result is an easy corollary of the above theorem.
Corollary 2 If G is an interval graph on n > 5 vertices, then G is the 2
competition graph of a loopless Hamiltonian digraph.
We conclude this section with a sufficient condition for a graph to be the p
competition graph of a strongly connected loopless digraph.
Theorem 6 Let G be a graph which is the pcompetition graph of some loopless
digraph, D, for p > 2. Then G is the pcompetition graph of some strongly
connected loopless digraph, D'.
12
The proof involves topologically ordering the strong components of D, and then
creating a digraph, D', which has fewer strongly connected components, such that
G is also the pcompetition graph of D'. The curious reader is referred to [10] for
detailed proofs of all results which have been presented in this section.
13
3
Tolerance Competition Graphs
3.1 Preliminaries
In this section, we will assign a tolerance from the nonnegative integers N,
to each vertex v, of a graph G = (V,E). Let : NxN > N be a symmetric
function. We will deal with = min, = max, and 4> sum in this chapter.
G is a (/^tolerance competition graph if there is a digraph D = (V,A) and an
assignment of tolerances Â£, to the vertices V{ such that for i ^ j, [u,, Vj] Â£ Â£(G)
if and only if ]0(vi) p) 0(vj) > tj) (where 0(x) is the outset of vertex x).
As with competition graphs, we are interested in covering the edges of G with
cliques. For this purpose, we define a toleranceedge clique cover (0TECC)
of G to be a collection 5i, S2, .., 5* of subsets of V such that [ur,us] G E(G) if
and only if at least (tr,t) of the sets S', contain both vr and vB. The size of a
smallest ^>TECC of G taken over all possible tolerance assignments is the
tolerance edge clique cover number and is denoted ^(G).
The following theorem of Brigham, McMorris, and Vitray [3] is easily understood
through examination of the example which follows it.
Theorem 7 Let ^ be a symmetric function defined from NxN into N. Then G
= (V,E) is a ^tolerance competition graph if and only if 0{G) < V.
Example 3 We will show that G of Figure 5 is a ^tolerance competition graph
14
for = max. (i.e. G is a maxtolerance competition graph). To see this, construct
a digraph D = (V, A) for which G is the maxtolerance competition graph.
a b
Figure 5: G is a maxtolerance competition graph.
ta = tb = 0, tc = td = 2, te = 1
Sets of a maxtolerance ECC: Se = {a, d}, Sc = {e, d}, Sb = {d,a, c}, Sa =
{d, b, e, c}, Sd = {6, c}
It is easy to check that [s, y] Â£ E(G) if and only if x and y occur together in at
least max {tx,ty} of the S{.
To construct digraph D (see Figure 6), we simply let Sj be the inset of vertex j
in D. This is the point at which we understand the relevance of Theorem 7; we
must use the same vertex set for D as we had for G, so 0^(G) must be less than
or equal to  V.
We have vertices a and b competing zero times. However, since max{Â£a, Â£&} = 0,
we do have edge [o, 6] in G. Vertices e and c compete only for vertex a, and since
max {te,tc} = 2, there is no edge between vertices e and c.
Note that D is loopless and Hamiltonian in this case (a Hamiltonian cycle in D
15
a
b
D:
Figure 6: D is the digraph for which G is the maxtolerance competition graph.
is abdeca). This will not always be the case, as will be discussed later.
The above example shows the strength of Theorem 7. We need not construct D
every time we wish to show that a graph is a ^tolerance competition graph. We
may instead show that 0^(G) < F.
3.2 MinTolerance Competition Graphs
3.2.1 The Basics
In this section, we let = min and start with an example.
Example 4 We will see that G of Figure 7 is a mintolerance competition graph
by constructing a minTECC of G consisting of V or fewer sets.
We assign tolerances as follows:
Then the following sets form a minTECC for G:
S\ {/} = {d, c, c}, i?3 {6, a, c}, S4 = {6, e}
4 < 6 = V, so G of Figure 7 is a mintolerance competition graph.
16
a b c
1
G:
c
fed
Figure 7: G is a mintolerance competition graph.
Brigham et al. [3] have shown that several classes of graphs are mintolerance
competition graphs and have provided some sufficient conditions for a graph to
be a mintolerance competition graph.
Theorem 8 [3] The following graphs are mintolerance competition graphs:
a. Every bipartite graph
b. Kni,n2,...tTifc (complete multipartite graphs)
c. Every graph G with a(G) > a^jg'j+i) w^ere a (G) is the size of
a maximal set of independent vertices in G, A (G) is the maximal
vertex degree in G, and 6 (G) is the minimal vertex degree in G.
The authors of [3] leave us with the following open question regarding min
tolerance competition graphs: Are there any graphs which are not mintolerance
competition graphs? It is unknown at this time whether the tenvertex graph
shown in Figure 8 is a mintolerance competition graph or not. No mintolerance
ECC of size 10 or less has been found thus far. However, proving that none exists
is a difficult problem.
17
Figure 8: Is this graph a mintolerance competition graph?
3.2.2 MinTolerance Competition Graphs and a Construction of My
cielski
We now use a construction of Mycielski [15] to generate large classes of graphs
which are mintolerance competition graphs. Most of the graphs we construct
do not satisfy the sufficient conditions of Theorem 12, nor are they competition
graphs. Thus, we are creating large new classes of mintolerance competition
graphs.
Given a graph G, we construct the graph p(G) as follows. If V(G) = {vi,v2,... ,i)ra},
let V(p(G)) = {ai,a2,...,am,bx,b2,..., bm, c} with [a,, aj] G Â£(p(G)) if and
only if [uj,i>j] G E(G),[ai,bj] G E(fi(G)) if and only if G E(G), [5,, c] G
E(fi{G)), 1 < i < m, and no other edges.
Example 5 Shown in Figure 9 is p(G), where G = C5, the cycle on five vertices.
18
Figure 9: p{G*,), also known as Grotzschs graph.
Courtesy of Larsen, Propp and Ullman [11], we have the following two interesting
properties of fi(G) :
a. v(fi(G)) = o>(G),where 01(G) is the size of the largest clique in G.
b. %(//(G)) = x(G) + 1, where x(G) is the chromatic number of G.
We now show that fi(G) is a mintolerance competition graph for several classes
of graphs G.
Theorem 9 (i(Cn) is a mintolerance competition graph.
Proof: Consider fi(C4):
If we assign the following tolerances, and use the sets 5, shown below as a min
TECC we can see that C4) is a mintolerance competition graph.
Tolerances: 1 = tc = ia., 1 < i < 4, 4 = tj,;, 1 < i < 4.
19
a>2
Oi
Figure 10: fi{C4).
Sets of minTECC:
Sc {c, 61,62,63,64} Sai = {oi, 62,64}
^2 = {<12563,61} 5Q3 = {03,64,62}
5a4 = {<14561,63} 5ft! = {
Sfc = {<12, O3} Sb3 = {<13,04}
Sb = {04, Oi}
\V{n{CA))\ = 2(4) + 1 = 9 = the size of the minTECC above.
Now consider fi(C3):
Tolerances: 1 = tc = 1 < i < 3
3 = tfc, 1 < < 3
Sets of minTECC (similar to sets used for C4):
= {c, 61,62,63} Sai = {01,62,63} Saj = {02,61,63}
Saa = {<13562,61} Sbi = {01,02} 5fcj = {o2,03}
20
ai
Sb3 {3j l}
Again we have used V  sets.
Tolerances used for /i(C73) can also be used for fi(Cn),n > 5.
1 ic ia; j 1 ^ ^ 7i
3 = tbi, 1 < i < n
Sets of minTECC:
Sc = {c, &15 &n}
Sai = {aj,6j_i,6,+i} (addition mod n), 1 < i < n
Sbi = {ai.Oi+i} (addition mod n), 1 < i < n
This is a minTECC of fi(Cn) which contains 2n +1 = V(/i(C'n)) sets, so fi(Cn)
is a mintolerance competition graph Vn>3.
21
Note that for n > 6, condition c of Theorem 8 is not met by since
a(fi(C)) = w + LfJ for n > 6 and 2(fr(Â£,i)+i) = for n > 6, but for
n>6, rc+Lil <*%*
Theorem 10 fi(K) is a mintolerance competition graph.
Proof: fi(K2) = C5, so ^{K^) is a mintolerance competition graph, since every
cycle is a competition graph. = p>(Cz) is a mintolerance competition
graph by the previous theorem.
We start by considering fi(K4) (see Figure 12).
Figure 12: fi(K4).
Let tc = ta. = 1, 1 < j < 4
Let tbj = 4, 1 < j < 4
Sets of a minTECC: {ai,2,3,4}, {1562,63,64}, {2,63,64,61},
{3,64,61,62}, {4,61,62,63}, {0,61,62,63,64}.
22
A similar construction works for fi(Kn), n > 5:
Let tc = taj = 1, 1 < j < n
and tbj = n, 1 < j < n
Sets of a minTECC:
{&I3 d2, On}j {1 3 ^2 3 ^3j j &n}3
{2j ^4s j j ^l}* 3 {ns ^13 ^2) 3 ^nljs
{c, ^l)&23",3 ^n}
The above minTECC consists of to + 2 sets, and certainly with n > 5 we have
n + 2 < 2n + 1 = V(G).
It is easy to check that x and y are adjacent in fi(Kn) if and only if at least
min{Â£x,iu} of the sets above contain both x and y.
Again, fi(Kn) does not satisfy condition c of Theorem 8. To see this, we consider
n > 5.
O'CMKn)) = n 2(tfjiri)+ij
Tor n > 5, n <
(2n+l)(2(nl)) (2n+l)(nl)
2(n+l) (n+1)
Theorem 11 If B is a bipartite graph, then fi(B) is a mintolerance competition
graph.
23
Proof: Let B be a bipartite graph with bipartition {!,..., ar] and {&i,..., 6*}.
Without loss of generality assume r < t. Now consider fi(B), which contains all
vertices and edges from B, as well as new vertices a[,..., a'T, b[,..., b't, and c.
^i(B) has 2r + 2t + 1 vertices in all.
We must find a minTECC of ^(B) of size at most 2r f 2< + 1.
Let tai = ta> = 1, 1 < i < r, tc = r + 1, t= 2r + 1, 1 < i < t, and
tbj = 2r + 2, 1 < i < t.
We let N[x\ be the closed neighborhood of vertex x, and assign our sets for a
minTECC as follows.
Sai = lV[a;], 1 < i < r
Sa[ = JV[oJ], 1 < i < r
^r+i = HU{6il 1<<*}
S2r+2 = {c} U{^i I 1 < i < t}
52r+r+1 = {c}U{6:l
It is easy to check that x and y are adjacent in /z(B) if and only if at least
min{Â£f,fv} of the sets Sp above contain both x and y.
The size of the minTECC is 3r + 1 < F (since r < t). Thus /x(B) is a
mintolerance competition graph.
When B is bipartite, with r and t defined as in the proof, we see that a(/x(B)) =
24
2t, 'V = 2r + 2t +1, A(/z(B)) > r + i, andÂ£(/i(B)) < r +1. With these facts and
some tedious algebra, we see that /i(B) does not satisfy condition c of Theorem
8.
Now we consider /i(G), where G is a connected graph. The following theorem
convinces us that /i(G) is rarely a competition graph itself.
Theorem 12 Let G be a connected graph on n vertices. /i(G) is a competition
graph if and only if G is Kn or G has exactly one nonsimplicial vertex xa, and
xa is contained in exactly two maximal cliques of G of sizes 3 or greater.
Proof: (4=) We construct fi(Kn) and /t(H), where H has exactly one nonsim
plicial vertex xa and xa is contained in exactly two maximal cliques of H of sizes
greater than or equal to 3. Next we give an ECC for each which consists of 2n +1
or fewer cliques.
Let X= {xi,..., x} be the original vertices of G, let Y= {yi,... y} be their
shadows, and let z be the additional vertex which is adjacent to every vertex
of Y.
For n(Kn), our ECC consists of the n edges incident to vertex z, and Nx(yi) U
{y,} V i < n. So we have an ECC of fi(Kn) consisting of 2ra < 2n + 1 cliques.
For /i(H), our ECC consists of the n edges incident to vertex z, and V i such that
xi is simplicial in H, we list {y,} U Nx{yi) in our ECC. For the one nonsimplicial
25
vertex xa in H, let C\ and Ci be the 2 maximal cliques in H which contain xa.
Then we complete our ECC of /i(H) with {ya}UiVCl(ya) and {ya}G Nc3(ya). This
ECC consists of 2ra + 1 = y(^i(H)) cliques.
(=4>) We must show: /i(G) is a competition graph => G is Kn or G has exactly
one nonsimplicial vertex xa, and xa is contained in exactly two maximal cliques
of G of size j, k> 3.
Suppose fi(G) is a competition graph. Then 0e(/i(G)) < 2n + 1. Consider a
minimum ECC of //(G). The n edges incident at vertex z make up n of the
cliques in such an ECC. Since Y (the set of shadow vertices) is an independent
set, no two vertices from Y will appear together in any clique of the ECC. Since
G is connected, we must have at least one clique for each y, in order to cover
edges between X and Y. So we have a total of 2n required sets in our ECC thus
far. If there are two nonsimplicial vertices in G, say xa and Xb, then we need at
least two cliques to cover edges between ya and X and at least two cliques to cover
edges between yb and X. This would force the minimum ECC to be of size 2n + 2,
indicating that fi(G) is not a competition graph. So there is at most one vertex ?/,
such that Xi is nonsimplicial in G. Furthermore, x, must be in just two maximal
cliques of G (otherwise the minimum ECC contains more than 2n + 1 cliques).
If one (or both) of these maximal cliques is K2, then //(G) is not a competiton
graph. We conclude that G is Kn or G has exactly one nonsimplicial vertex, x,
26
and xa is contained in exactly two maximal cliques of G of sizes greater than or
equal to three.
Theorem 13 If G is a competition graph, then fi(G) is a mintolerance compe
tition graph;
Proof: Let G be a competition graph on n vertices, ai,..., o. To create /j(G),
we add vertices &i,..., bn, and c, with appropriate edges as described earlier.
Since G is a competition graph, we know we can cover the edges of G with n or
fewer cliques.
We now specify a minTECC for fi(G).
Assignment of tolerances:
ta. =tc= 1, 1 < i < n and tb. = n + 2, 1 < i < n
We can start our minTECC of /x(G) with the same cliques used in a minimal
covering of G (there will be less than or equal to n of these, since 0e(G) < n).
We will also use the set {c, ..., bn} (to cover all edges incident to c).
The edges that remain to be covered are between V(G) and B = {&i,..., &}, so
let our final sets be {a,} (J JVb(oi), 1 < i < n, where B= {fex,..., 6}. Note that
tb. = to + 2, so no edges will appear between any of the 6,s.
The maximum number of sets in this minTECC is 2n + 1 =  V(/i(G)).
Thus /*(G) is a mintolerance competition graph.
27
Note that since cycles and complete graphs are competition graphs, Theorems
13 and 14 are direct corollaries of Theorem 13.
3.3 MaxTolerance Competition Graphs
In [3], the authors briefly discuss the situation for = max. The following
theorem is due to them.
Theorem 14 For all n > 1, K2,n is a maxtolerance competition graph. More
over, this can be demonstrated using only tolerances 0,1, and 2.
The idea of the proof was demonstrated in Example 3 (the graph shown there
was ^2,3) The proof simply lists the tolerances we must use, and the sets of a
maxTECC that will work for all K2i.
It is interesting to note that unlike the case for = min, there art graphs which
have been identified as not being maxtolerance competition graphs. The one
given as an example in [3] is K^. The authors tell us that this fact has been
demonstrated in a long multicase analysis based on the maximum tolerance used.
They also show us a single subcase which is rather lengthy. Reading this subcase
emphasizes the difficulties that one encounters in trying to prove that a graph is
not a ^tolerance competition graph, whatever may be. The principal difficulty
is that one must consider all possible assignments of tolerances before concluding
that a graph is not a ^tolerance competition graph.
28
3.4 SumTolerance Competition Graphs
For sumtolerance competition graphs, we define as follows:
(ti, tj) = tj + tj i.e. We have an edge between two vertices v, and Vj in the
graph if and only if they compete for at least f; + tj vertices in the digraph.
Example 6 The graph of Figure 13 is a sumtolerance competition graph, as
demonstrated by the list of tolerances and the sumTECC that follow.
d
Figure 13: G is a sumtolerance competition graph.
We assign tolerances as follows:
ta = tb = tc=l
trf tg tj 0
And the sets of our sumTECC are {a, b, c}, {a, 6}, {a, c}, {a, d}, {c, e}, and
{6,e}.
We note that the vertices d, e, and / form a clique in G but are not listed together
in any of the sets of the sumTECC. However, since they have been assigned
tolerance zero, the edges between them are automatic, without being listed in
29
the sumTECC. Also notice that vertices b and c have been listed together once
in the sumTECC. This is allowable since the sum of their tolerances is 2. They
would have to be listed together at least twice in order to have the edge [6, c]
appear in the graph.
The authors of [3] bring up an interesting point which distinguishes sumtolerance
competition graphs from max and mintolerance competition graphs. They note
that there are graphs which are sumtolerance competition graphs if we allow
noninteger tolerances which are not sumtolerance competition graphs using the
usual definition (where all tolerances axe restricted to the nonnegative integers).
The example they give is, again, #3,3.
Figure 14: The complete bipartite graph, K3i3.
The tolerance assignment the authors use is:
t'a = tf, = g, tc tx = ty = and tz = 1
Then the following sets form a sumTECC for ^3,3:
Si = {a,c,x,z}, S2 = {b,c,y,z}, S3 = {a,y}, SA = {a,z}, 5S = {6,}, and
S6 = {M}
30
The proof which the authors give to show that K3)3 is not a sumtolerance com
petition graph if all tolerances are from the nonnegative integers is lengthy, even
in its incomplete form, again emphasizing the difficulty in proving that a graph
is not a ^tolerance competition graph.
The authors [3] pose the following question, Are there graphs which are not
sumtolerance competition graphs if noninteger tolerances are allowed?
3.5 Two0Tolerance Competition Graphs
In this section we concern ourselves only with those ^tolerance competition
graphs which have tolerances assigned strictly from the set {p,q}, where p and
q are nonnegative integers. Such a graph is called a twotolerance competition
graph or a {p, q}tolerance competition graph.
First, we note that certainly a pcompetition graph is a {p, g}maxtolerance
competition graph and a {p, q}mintolerance competition graph. And, likewise,
a <7competition graph is a {p, q}maxtolerance competition graph and a {p, q}
mintolerance competition graph.
We follow this point with an example of a graph which is not a pcompetition
graph and not a qcompetition graph but which is a {p, g}^tolerance competi
tion graph.
31
Example 7 K2$ (see Figure 15) is an example of a graph which is not a 1
competition graph and not a 2competition graph, but which is a {l,2}max
tolerance competition graph.
We know that since 0e(K2fi) = 12 > 8 = Vr(FL2i6) K2$ is not a 1competition
graph.
We also know (from [8]) that K2,6 is not a 2competition graph.
The tolerances and sets of a maxTECC given below, however, show that K2$
is a {1,2}maxtolerance competition graph'.
c
d
e
f
g
h
Figure 15: The complete bipartite graph K2$.
Tolerances: ta = tf, = = tf = 1, and tg = th = 2
Sets of a maxTECC: S\ = {a,c,h}, S2 = {a,d,h}, S3 = {a, e,g}, S4 =
S5 = {b,c,g}, S6 = {b,d,g}, S7 = {b, e, h}, and 58 = {b, f, h}
It is easy to check that [x,y] 6 E(G) if and only if x and y are together in at
least max{tc, tv} of the sets listed above.
32
The authors of [2] point out that when p and g are any two positive integers, the
problem of determining whether or not a graph is a {p, tolerance competition
graph is still rather difficult. The problem is simpler if we restrict one of the
tolerances to zero.
3.5.1 {0,g}^Tolerance Competition Graphs
The following theorem of [2] is very helpful in categorizing {0,g}mintolerance
competition graphs.
Theorem 15 Graph G of order n is a {O,g}mintolerance competition graph if
and only if 0f(GM) < n where M is the set of vertices of degree n 1.
An alternate wording would be:
Graph G of order n is a {O,g}mintolerance competition graph if and
only if (GM) U I\u\ is a gcompetition graph, where Im is the graph
consisting of M isolated vertices.
Example 8 G shown in Figure 16 is a {O,g}mintolerance competition graph
for 1 < q < 4, since G{mi} U Ji is a gcompetition graph for 1 < g < 4.
In all cases, we assign tolerance zero to the vertex of degree n 1, mi, and assign
tolerance q to all others, w, sc, y, and z.
33
m i w
(GM)UIi:
ii w
G:
x y z
o
x y z
Figure 16: The graphs G and (GM)\JIi.
For q = 1, the 1ECC of (GM)lJJi consists of the sets {x,y} and {y,z}.
For q = 2, the sets are {x,y,z}, {,t/}, and {y,z}.
For q = 3, the following four sets form a 3ECC for (GM)UTi:
and{y,z}.
And finally for q 4, the following five sets form a 4ECC:
{x,y,z}, {x,y,z}, {x,y}, and {y,z}.
However, it is easy to see that G is not a {0,5}mintolerance competition graph,
since the smallest possible 5ECC for P3 is of size 6, which is greater than G=5.
If GM has no isolated vertices, then the authors of [2] simplify the previous
theorem as follows.
Theorem 16 Let G be a graph of order n, let M be the set of its vertices of
degree n 1, and suppose GM has no isolated vertices. Then G is a {0,q}min
tolerance competition graph if and only if G is a qcompetition graph.
The idea of the proof of necessity is to start with a qECC of GM (which by
the previous theorem will be of size n or smaller), and add the vertices of M to
34
every one of those sets, thus creating a qECC of G which is of size n or smaller,
implying that G is a gcompetition graph.
The following theorem of [2] is quite useful in determining whether or not a given
graph is a {O,l}maxtolerance competition graph.
Theorem 17 Graph G of order n is a {O,l}maxtolerance competition graph if
and only if 0*(G) < n + 1
The proof for necessity (=>) involves taking a {0,l}*maxTECC of size at most
n and turning it into a 1ECC of size at most n +1 by simply adding a set which
consists of those vertices which were originally assigned tolerance 0.
The idea of the proof for sufficiency (4=) is to take a 1ECC of G of size at most
n + 1 and drop one of the sets arbitrarily. To all vertices in that set, assign
tolerance 0, and assign 1 to all others. This idea is used in the example that
follows.
Example 9 For G of Figure 17, it is clear that B\ = 7 = n + 1.
a b c
H'
G:
 H
d e f
Figure 17: G is a maxtolerance competition graph.
35
The seven sets required in a 1ECC of G are:
{a,b}, {6,c}, {c,/}, {/, e}, {e,d}, {d,a}, and {b,e}.
H we drop one set arbitrarily, say {6, e}, and assign tolerance 0 to vertices b and
e and 1 to all others, then it is easy to see that \x,y] gE(G) if and only if x and
y are in at least max{Â£x,ttf} sets of the new maxTECC.
3.5.2 1Competition Graphs Which Are Not 2Competition Graphs
In considering the question, Are there any graphs which are {O,l}mintolerance
competition graphs which are not {0,l}sumtolerance competition graphs? [2],
we have come across some interesting problems. One is, Which 1competition
graphs are not 2competition graphs? This is because every 1competition graph
is a {O,l}mintolerance competition graph and every 2competition graph is
automatically a {O,l}sumcompetition graph (we would put tolerance 1 on ev
ery vertex). So, if we find graphs which are 1competition graphs but not 2
competition graphs, we might find a {O,l}mintolerance competition graph which
is not a {O,l}sumtolerance competition graph. We have identified only a few
graphs which are 1competition graphs but not 2competition graphs. One of
them is C4, the cycle on 4 vertices (proven in [8]), and the others are closely
related to the graph G of Figure 18. Unfortunately, all of them are also {0,1}
sumtolerance competition graphs, so we have not yet answered the question
originally posed.
36
a
b
G:
d c
Figure 18: G is not a 1competition graph and not a 2competition graph.
G of Figure 18 is not a 1competition graph, since 0g(G) = 6 > 5 = V(G).
However, it can easily be made into a 1competition graph, as we will soon see.
The most important thing to note about G at this point concerns the size of a
smallest 2ECC of G.
Theorem 18 For G of Figure 18, 0g(G) = 7.
Proof: We know that a 2ECC of just the 4cycle a, 6, c, e requires 5 sets (from
[8]). We can cover G with 7 sets, so 5 < 0g(G) < 7.
There is only one way to cover the 4cycle a, 6, c, e with 5 sets. It is: {a, b, c, e}
{a, 6} {6, c} {c, e} {e, a} It is easy to see that we cannot cover edges [a, d\ and
[d, c] by only adding vertices to these existing 5 sets. Thus 6 < 91(G) < 7.
To see that 91(G) ^ 6, we must consider several cases.
Case i: We cover the 4cycle a, 6, c, e with 5 sets.
Let those 5 sets be the same as before:
S\ = {o, 6, c, e}, 1S2 {u, 6}, S3 = {i, c}, $4 = {c, e}, S$ = {e, 0}
We know we will have to add a sixth set, by previous arguement. In order to have
37
this sixth set be of use, it must list [a, d] or [d, c]. It cannot list both of the edges
[o,d] and [d,c], since this would create the unwanted edge [a, c]. So, without loss
of generality let Sq = {a, d}. Now, given these six sets, we must list [a, d] again,
and [d,c] twice, without creating any unwanted edges. It is quite easy to see with
our limited choices that this is not possible.
So, the conclusion for case i is: when we cover the 4cycle a, b, c, e with 5 sets, it
is impossible to cover G with 6 sets.
Case ii: We cover the 4cycle a, b, c, e with 6 sets (which do not include the 5
sets from case i).
There is only one way (up to equivalence) to cover a 4cycle with six sets (which
do not include the sets from case t). Thus without loss of generality, let our six
sets be Si = {a, b, c}, 52 = {a, &, e}, S3 = {a, e}, S4 = {6, c}, S5 = {e,c},
and Sq = {e, c}. Again, we are quite limited when we try to cover edges [o, d]
and [d, c]. After careful analysis, we realize that it is impossible to do without
creating a seventh set.
We can cover G with the following seven sets: Si = {a, 6, c, d, e}, S2 = {a, 6}, S3 =
{6,c}, S4 = {c,e}, Sq = {e,a}, Sq = {a,d}, and S7 = {d,c}. Thus0g(G) = 7.
So we have seen that G = K2,3 is not a 1competition graph, since ^(G) = 6 and
it is not a 2competition graph, since dg(G) = 7. However, we are interested in
38
graphs which are 1competition graphs but not 2competition graphs. The work
just shown will be very helpful in showing that the following graphs do meet that
description.
Figure 19: Graphs which are 1competition graphs and not 2competition graphs.
For each of the six graphs G of Figure 19, 0*(G) = 6 and 8%(G) => 7. Thus
each of those graphs is a 1competition graph but not a 2competition graph.
Note that a seventh graph (a disconnected one) could be added to Figure 19; we
simply leave the bottom vertex isolated and keep the other six edges.
We can generalize the above method quite nicely to a result which is great in
theory, but rather difficult to implement.
3.5.3 Creating 1competition graphs which are not 2competition graphs.
Let us begin by considering the graphs previously discussed. All six had #2,3 as
a generated subgraph. In each of the six cases, we started with #2,3 and added
one vertex, x being careful to add edges from x which would keep 8\ of our
new graph equal to 6. But since each of the six graphs has #2,3 as a generated
subgraph and 6l(K2,3) > 7, we know that 8% for each of the six new graphs is
39
also greater than or equal to 7, which is one more than the number of vertices.
It is easy to see, then, that the following method will always result in a graph
which is a 1competition graph but not a 2competition graph.
Start with a graph G on n vertices with 0*(G) = n + 1 and 0g(G)
> n + 2. Add a vertex x which is adjacent to all vertices of G (or just
some of the cliques of G), creating the new graph, G'. Then 0g(G') is
still n+1, so G' is a 1competition graph. However, G' still has G as a
generated subgraph, so 0g(G') >n + 2, and G' is not a 2competition
graph.
We can, in fact, generalize this notion further by starting with G on n vertices
with 0g(G) = to + k and ^(G) >n + fe + l, & >1. Then we can add k vertices
to G, one at a time, making each vertex adjacent to all of those in the graph
preceding it. The new graph G' will have 0*(G') = n + A:, but since G is a
generated subgraph of G', flg(G') > n + k + 1. Thus G' will be a 1competition
graph but not a 2competition graph.
As mentioned previously, the method discussed here is a nice theoretical tool;
however, from a practical standpoint it is quite difficult to use. The problem
comes in the first step finding G such that ^(G) = n + k and 0g(G) > ti + fc +1,
k > 1. The difficulty in finding such a G was illustrated by the graph ^2,3, where
n = 5 and k = 1. For larger n and ft, the proof for 0g(G) > n f k + 1 becomes
40
quite unwieldy.
3.5.4 More on 1competition graphs which are not 2competition
graphs.
In conclusion, we present some ideas which are useful in narrowing the search
for more 1competition graphs which are not 2competition graphs. First, note
that any such graph will not be chordal or unicyclic (except C4). This is because
chordal graphs and unicyclic graphs are 2competition graphs (see [9]).
The following lemma, a proof of which is given in [6], allows us to narrow the
search even further.
Lemma 4 Every connected trianglefree graph G with n = V(G) or fewer edges
is either a tree or a tree with an additional edge.
We use this lemma to prove the following result.
Theorem 19 If G is a connected trianglefree graph with n or fewer edges, then
G is a 2competition graph or G is C4.
Proof: Let G be of order n with n or fewer edges and assume G is not C4. By
the lemma, G is a tree, or G is a tree with one extra edge. If G is a tree, then G
is chordal and is therefore a 2competition graph. If G is a tree with one extra
edge, then G is unicyclic, and is therefore a 2competition graph.
41
The search for more 1competition graphs which are not 2competition graphs has
been reduced (in the connected case) to nonchordal, nonunicyclic 1competition
graphs with at least one triangle. The six graphs presented earlier do meet this
description, but the search for more continues.
42
4 Conclusion
There are many directions in which the topics discussed here can be taken for
future research. We conclude by listing some of those possibilities.
Open Problem 1: Which graphs are pcompetition or ^tolerance competition
graphs of symmetric digraphs (with or without loops)? [See [14] for an analogous
result for interval competition graphs.]
Open Problem 2: Can we find a family of graphs Q such that the following
statement is true?
If V(G) = n, then G is a 2competition graph of a digraph that has
no loops if and only if G Â£ Q and < n.
Some graphs which are known to be in this set Q are K2, K2 U K\, P3, K3 (all
courtesy of [9]) and the graph shown in Figure 20. What other graphs belong in.
G1
Figure 20: A graph which is a 2competition graph of an arbitrary digraph with
hops, but not of a digraph without loops.
Open Problem 3: How might we minimize or maximize the number of arcs in
D without changing G, where G is the pcompetition graph or the ^tolerance
competition graph of D? [See [7] for a related result for competition graphs.]
43
Open Problem 4: What if we expand on some of the ideas briefly mentioned
at the end of Chapter 1 and consider such graphs as pniche graphs, ^tolerance
niche graphs, pcompetitioncommon enemy graphs, and ^tolerance competition
common enemy graphs? Can we find any results analogous to those that are
known for niche graphs and competitioncommon enemy graphs [see [18] and
[4]]?
Open Problem 5: Which acyclic digraphs have pcompetition graphs which
are interval graphs? [See [13] for analogous results on competiton graphs.]
Open Problem 6: What if we make analogous definitions using clique covers
of vertices rather than edges? What can be determined in such cases?
One might wonder whether Joel Cohen ever would have imagined in 1968 the
possibilities hidden in his food web model. The open problems listed above
certainly barely scratch the surface in terms of where research in this area could
possibly go.
44
References
[1] R. C. Brigham and R. D. Dutton. A characterization of competition graphs.
Discrete Applied Mathematics, 6:315317, 1983.
[2] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Two^tolerance compe
tition graphs. Submitted for publication, 1993.
[3] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Tolerance competition
graphs. To appear in Linear Algebra and Its Applications, 1994.
[4] C. Cable, K. F. Jones, J. R. Lundgren, and S. Seager. Niche graphs. Discrete
Applied Mathematics, 23:231241, 1988.
[5] J. E. Cohen. Interval graphs and food webs: A finding and a problem.
Document 17696PR, RAND Corporation, 1968.
[6] K. F. Fraughnaugh, J. R. Lundgren, J. S. Maybee, S. K. Merz, and N. J.
Pullman. Competition graphs of strongly connected and Hamiltonian di
graphs. SIAM Journal on Discrete Math, 1993. To appear.
[7] K. A. S. Hefner and D. W. Hintze. Maximizing arcs in a network for a given
conflict graph, to appear, 1994.
[8] G. Isaak, S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts.
2competition graphs. SIAM Journal on Discrete Math, 5:524538, 1992.
45
[9] S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts, pcompetition
graphs. To appear in Linear Algebra and Its Applications, 1994.
[10] L. Langley, J. R. Lundgren, P. A. McKenna, S. K. Merz, and C. W. Ras
mussen. Some characterizations of pcompetition graphs of strongly con
nected and Hamiltonian digraphs, manuscript, 1994.
[11] M. Larsen, J. Propp, and D. Ullman. The fractional chromatic number of
Mycielskis graphs, to appear in Journal of Graph Theory, 1994.
[12] J. R. Lundgren. Food webs, competition graphs, competitioncommon en
emy graphs, and niche graphs. In F.S. Roberts, editor, Applications of Com
binatorics and Graph Theory to the Biological and Social Sciences. Springer
Verlag, 1989. In IMH Volumes in Mathematics and Its Applications, vol.
17.
[13] J. R. Lundgren and J. S. Maybee. Food webs with interval competition
graphs. In Graphs and Applications: Proceedings of the First Colorado Sym
posium on Graph Theory. Wiley, New York, 1984.
[14] J.R. Lundgren, J.S. Maybee, and C.W. Rasmussen. Interval competition
graphs of symmetric digraphs. Discrete Mathematics, 119:113122, 1993.
[15] J. Mycielski. Sur le coloriage des graphes. Colloquium Mathematicum,
3:161162, 1955.
46
[16] F. S. Roberts. Discrete Mathematical Models, with Applications to Social,
Biological, and Environmental Problems. Prentice Hall, Englewood Cliffs,
New Jersey, 1976.
[17] F. S. Roberts and J. E. Steif. A characterization of competition graphs of
arbitrary digraphs. Discrete Applied Mathematics, 6:323326, 1983.
[18] D. D. Scott. The competitioncommon enemy graph of a digraph. Discrete
Applied Mathematics, 17:269280, 1987.
47
In summary, a subgraph of interval graph G induced on vertices a, b, c, d, e,
and / is a 4fan about nonsimplicial edge [a, b] hinged at a if {a, b, c} is a maximal
clique of G, [e, c], [e, a], [/, d], [/, a] 6 E(G), possibly [b, /] Â£ E(G), and no other
edges are present. The figure below shows two such 4fans.
To construct our collection S of sets, we use the chart that follows. For every
nonsimplicial edge of G, we determine its type, and add set(s) to the collection
S. For example, if [a, b] is a Type 2 nonsimplicial edge, we add two sets to S, as
described in the chart. Note that we also add sets based on maximal cliques of
size at least 4 in G which contain only simplicial edges (see section 6 of chart).
48
Sets of S
Type of Nonsimplicial Edge Set Definition Set Type
(1) [a, 6] contained only in cliques of size at least 4 Se = N[[a,b\\ (1)
(2) [a, 6] contained only in cliques of size 3, and there are no induced 4fans about [a, 6] Sei = N{[a,b\) (2a)
S II IpT cr* (2b)
(3) [a, 6] contained only in cliques of size 3, and there is at least one 4fan about Ml Sei=N([a,b\) (3a)
$0 :3 11 IT r 73b) :
Sek (i c, d}, one such set for each 4fan about [a, 6] hinged at a (3c)
Sej = {b,p, g}, one such set for each 4fan about (a, 6] hinged at b 73d)
(4) [a, 6] is contained in both cliques of size at least 4 and of size 3, and there are no 4fans about [a, 6] (induced or otherwise) Sei = the union of all cliques of size at least 4 containing [a, 6] (4a)
Se, = N([a,b\) (4b) ,
(5) [a, 6] is contained in both cliques of size at least 4 and of size 3, and there is at least one 4fan about [a, 6] (perhaps not induced) Sei the union of all cliques of size at least 4 containing [a, 6] (5a)
Sc, = AT(M) 75b)
Sek = {> c> d}U{all cliques of size at least 4 contain ing [a, &]}{&},one such set for each 4fan about [a, 6] hinged at a (5c)
Sej {b,P, g}U(all cliques of size at least 4 contain ing [a, 6]}{a},one such set for each 4fan about [a, 6] hinged at b (5d)
Se = Cm, where Cm is a cliqueof size at least 4 with no nonsimplicial edges (6)
49
Theorem 13 If G is a chordal graph, then S forms a (2)neighborhood cover of
G.
Proof: This follows from the fact that S is an extension of the family T of
Section 3.2, which was proved to form a (2)neighborhood cover of G. It is easy
to see from the definitions given in the chart that those sets in S which are not
in T do form cliques in N2(G).
Corollary 3 Let S' = {Se e S\Se is maximal}, and suppose G is chordal. Then
S' is a (2)neighborhood cover of G.
4.3 Main Result
In this section, we prove five lemmas, each relating to a different type of non
simplicial edge of interval graph G, and a sixth lemma which relates to those
maximal cliques of size at least 4 in G which have no nonsimplicial edges. The
lemmas convince us that each set of S' defined in Section 4.2 corresponds to a
maximal clique of N2(G). We then use the lemmas to show that the family S'
forms a (2)neighborhood cover of G which consists of maximal cliques of N2(G).
We conclude with a necessary and sufficient condition for an interval graph G to
have an interval (2)neighborhood graph.
50
In each of the following lemmas, we will assume the following facts, unless
stated otherwise: The graph G is an interval graph. We let the (distinct) consec
utively ranked maximal cliques of G be Ci,..., Cr, and edge [a, b] is contained
in precisely Ci,..., Ci+ki Notice that the closed neighborhood of edge [a, b],
jv[M] =
Lemma 7 If edge [a, b] is a Type 1 nonsimplicial edge of G, then the set Se in
S' associated with it is a maximal clique in N2(G).
Proof: Suppose Se S' and Se is associated with nonsimplicial Type 1 edge
[a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of
length 2 from vertex x to every vertex in Se] we will show x Â£ Se. Assume not. If
x Â£ Se, then x 0 N[[a, Â£]] = Suppose without loss of generality that
x e Cm implies m < i. Consider clique Ci+ki, the last clique in the consecutive
ranking to contain both a and 6. Clique Ci+ki contains a vertex d such that
Ci+k~i is the first clique in the ranking in which d appears. We know d exists by
the maximality of the cliques in the ranking.
Case 1: Vertex x is adjacent to neither a nor b. Since there are two paths of length
2 from x to d, there exist two vertices / and g in V(G) such that [/, d], [/, x\, [g, d],
and [g,x] Â£ E(G). Note that f ^ a, b and g ^ a, b. Then, by the consecutive
ranking, / and g appear together in cliques C;_i,..., Ci+k~i, and possibly more.
51
Hence [/, g] e E(G), and in fact [f,g\ is a nonsimplicial edge of G. Edge [/, g]
is not a Type 1 nonsimplicial edge, since N[[f,
see this from the consecutive ranking of the maximal cliques of G), so [/, g] is
Type 4 or Type 5. In either case, the only cliques of size at least 4 containing
[/, g] are precisely Ci+ki (by maximality of Se in S'). Thus {x, /, g} is
a maximal clique Cp of G, and p < i. Vertex x is not adjacent to any vertex
in Uother than / and g. This is because if it were adjacent to some
vertex v G U^+fc1C,, v ^ f,g, then {v,f,g,x} would be a clique of G of size
> 4 containing / and g but not in {C*,..., Ci+k1}.
Every clique in {Ci,..., Ci+k1} contains a, b, f, and g. Since k > 2, there
exist vertices p and q in U3jZli+k~1Cj such that p and q are each adjacent to all of
Q
a, b, f, and g but [p, q] ^ E(G). Thus in G we have g b
Recall that there are two paths of length 2 from x to every vertex in N[[a, 6]].
This includes / and g\ thus there exist /', g' G V(G) such that [x,f], [/',/],
[x,g% and \g',g\ e E(G).
Note that [/', g], [g1, /], [x, q] <Â£ E(G), since the addition of any of these edges
creates a clique of size at least 4 containing x, /, and g. This also convinces us
52
that f ^ g'. Then the subgraph of G induced on vertices x, /, g, /', g', and q
convinces us that G is not an interval graph, a contradiction.
Case 2: Vertex x is adjacent to one of a and b. Without loss of generality, suppose
[a;, a] e E(G). Then there exists g 6 V(G) such that [x,g], [g,d] G E(G). Recall
that Ci+ki is the first clique in the ranking in which d appears. Then g and
a appear together in at least Cii,..., Ci+ki. Hence [<7, a] is a nonsimplicial
edge, either of Type 4 or 5 (not Type 1, because N[[a, 6]] is properly contained in
N[[a, <7]]). Thus {a, g, x} is a maximal clique of G. There are two paths of length
2 from x to every vertex in iV[[a, 6]], including a and g, thus there exist vertices
r, s E V(G) such that [x, r], [r, a], [x, s], and [s, g] E E(G)x Note that r ^ s, since
this would create clique {a, <7,x,r = s}, contradicting the maximality of clique
{a,g,x}. For the same reason, [a, s],[r, g] Â£ E(G). This leads to the following
subgraph in G:
We conclude that G is not an interval graph, a contradiction.
/'
9' g q
53
d
The two cases convince us that x Â£ N[[a, ft]] = Se, and hence Se is a maximal
clique of N2(G). u
Lemma 8 If edge [a, 6] is a Type 2 nonsimplicial edge of G, then the sets in S'
associated with it are maximal cliques in N2(G).
Proof: Suppose Se Â£ S' and Se is associated with nonsimplicial Type 2 edge
[a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths
of length 2 from vertex x to every vertex in Se; we will show x Â£ Se. Assume not.
Case 1: The set Se is a Type (2a) set. Then x Se = N([a, b]).
Subcase a: Assume x Â£ N[[a, 6]]. Recall that x Â£ N([a, &]); thus without loss
of generality, assume x = a. Certainly there is one path of length 2 (through
b) from x = a to each vertex in N([a, 6]). Suppose vertex c belongs to Q and
no later cliques in the ranking, and let vertex d belong to Ci+ki and no prior
cliques in the ranking. Note, then, that C* = {a, b, c}, and Ci+k1 = {a,b,d}.
Since no two vertices in N([a, 6]) are adjacent, there exists u Â£ V{G) such that
54
U Â£ Cm implies m < i and [x,u\, [u,c] Â£ E(G), and there exists v Â£ V(G) such
b
d
C Jl
\
J s\. J/ \ / \ \
that v Â£ Cj implies j > i + k 1 and [x, v\, [v, c] Â£ E(G). u x = a v
Vertices v,u Â£ N([a, Â£>]), so [v,b\,[u,b\ 0 E(G). Also, by the consecutive
ranking of the maximal cliques of G and the fact that \Cq\ = 3 if a, b Â£ Cg, we
know [u, c], [u, d], [u, v] ^ E{G). So we have the following induced subgraph in G:
b
d
KI2\
u x = a v This is an induced 4fan about [a,b], a contradiction.
Subcase b: x ^ N[[a, 6]]. Let vertex d be in Ci t k 1 and no prior cliques
in the ranking. Since there are two paths of length 2 from x to d, d and x have
two common neighbors. Any neighbor of d can be adjacent to at most one of
a and b (otherwise a and b are contained in a clique of size greater than 3), so
at least one of these two common neighbors is neither a nor 6; let v be such a
common neighbor. Since [d,v] Â£ E(G) and [x,u] Â£ E(G), we have v in each
maximal clique Q_i,..., Ci+k~i and perhaps more. But this contradicts the fact
that \Cj\ = 3, i < j < i + k 1, when we consider maximality of the cliques in
the ranking. Hence x Â£ N([a, 6]) = Se or x Â£ AT[[a, b]].
55
We conclude that if Se is a Type (2a) set, then x E Se.
Case 2: The set Se is a Type (2b) set. Then x Â£ Se = {a, b}.
Subcase a: x E N[[a, b]]. Since there are two paths of length 2 from x to
a, there exists y G V((?) such that [x,y],[y,a] G E(G), [y,b] Â£ E(G). There
are also two paths of length 2 from x to b, so there exists z E V (G) such that
[x, z], z, 6] G E(G), [z, a] ^ E(G). Then we have the subgraph shown below, and
G is not an interval graph, a contradiction.
Subcase b: x 0 N[[a, 6]]. Without loss of generality, suppose x G Cm implies
m < i. Vertex x is adjacent to at most one common neighbor of a and b, c,
where c G C*. Suppose without loss of generality [x,b] E(G). Then, since
there are two paths of length 2 from x to a, there exists y G V(G) such that
[x,y\,[y,a] G E(G). Also, because [a, b] is nonsimplicial, there exists d ^ c G
AT[[a,6]], d G Ci+ki, and [c,d] Â£ E(G).
We must add a chord to 4cycle xyac. Chord [a,re], with or without chord
y
z b d
56
[:y, c] creates a 4fan about nonsimplicial edge [a, c], causing {a, b, x) to be a set
in S', contradicting the maximality of the set {a, b} Se in S'. Thus chord
[;y, c] G E(G), and chord [a, x] Â£ E{G). Thus far, we know of one path of length
2 from x to b, the path through c, and since [y, b] E(G), we know there exists
z G V(G) such that [x, z], [z, b] G E(G). By reasoning similar to above, we have
chord [c, z] for 4cycle xcbz, since [6, x] creates a 4fan about nonsimplicial edge
[b, c], putting {x, a, b} in S'. Then the subgraph induced on vertices a,b,c,d,y,
and z indicates that G is not an interval graph, a contradiction.
y
If x is not adjacent to any common neighbors of a and b, then a has a neighbor
y such that [y,b] 0 E(G) and [x,y], [y, a] G E{G), and b has a neighbor z such
that [z, a] ^ E(G) and [x, z], [z, 6] G E{G). Then G has a chordless 4cycle of size
4 or greater (either yabz or yabzx), a contradiction.
We conclude that x G Se {a, b}, and hence Se is a maximal clique in N2(G).
57
Lemma 9 If edge [a, 6] is a Type 3 nonsimplicial edge of G, then the sets in S'
associated with it are maximal cliques in N2(G).
Proof: Suppose Se G S' and Se is associated with nonsimplicial Type 3 edge
[a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths
of length 2 from vertex x to each vertex in Se\ we will show x G Se. Assume not.
Case 1: The set Se is a Type (3a) set. Then x Â£ Se
N([a, 6]). Without loss of
generality, assume there is a 4fan about edge [a, b] hinged at b. f b g
Subcase a: x G 7V[[a, 6]].
Suppose x = b. Then there are two paths of length 2 from x = b to c and two
paths of length 2 from x b to d (via a and / and via a and g, respectively). If c
and d are the only neighbors of [a, b], then {c, d, 6} is a Type (3d) set, contradicting
the maximality of Se = iV([a, b]) = {c, d} G S'. Thus a and b have another
common neighbor h. Since [h,g] would create the chordless 4cycle hgda and
[h, f] would create the chordless 4cycle hfca, we know [h, g], [h, f] Â£ E(G). Thus
there exists y G V(G) such that [b,y\, [y,h] G E(G). Edge [a, y] E(G), since if
it were, we would have {a, b, h, y} contained in some clique of G, contradicting
the fact that [a, 6] is a Type 3 nonsimplicial edge. Then we have NC? as an
58
induced subgraph of G (on vertices a,c,d,h,f,g, and y), contradicting the fact
that G is an interval graph.
/
C>
Now suppose x = a. Since there are two paths of length 2 from x to d and
two paths of length 2 from x to c, we know there exists y G V (G) such that
[c, y], [y,a] G E(G). The addition of edge [b,y\ forces [a, 6] into a clique of size
greater than 3, so [b, y] Â£ E(G). Then we have the following subgraph induced
on vertices o, b, c, d, /, and y, convincing us that G is not interval.
y
Subcase b: x $ iV[[a, 6]]. Suppose without loss of generality that x G Cm
implies m
of length 2 from x to d, d and x have two common neighbors, one of which, call
it y, is neither a nor b. Thus [a:, y], [y, d] G E(G). By the consecutive ranking of
the cliques of G, y = c. However, this contradicts the fact that [a, b] is contained
only in cliques of size 3, as {a, b, c, d} becomes a clique of G.
59
We conclude from Case 1 that Se is not a Type (3a) set.
Case 2: The set Se is a Type (3b) set. Since the reasoning used in Case 2 of the
proof of Lemma 2 did not rely upon the fact that there were no 4fans about
[a, 6], we may use the same arguments here. We conclude that Se cannot possibly
be a Type (3b) set.
Case 3: The set Se is a Type (3c) set. Suppose Se corresponds to the 4fan about
d
[a, b] hinged at a shown below. Then x $ Se = {a, c,d}. f a g
Subcase a: x G N[[a, 6]]. Then [x,c],[x,d\ E(G). Thus there exists y G
V(G) such that y 0 N[[a, 6]], [x,y],[y,a] G E(G), and thus [y,b] Â£ E(G). Then
we have NCj as an induced subgraph of G (on vertices b,c,d,x, f,g, and y),
contradicting the fact that G is an interval graph.
/.
c( >
, V 
g a o x y
Subcase b: x iV[[a,6]]. Suppose that x G Cm implies m < i, and let Cp
be the last clique in the ranking in which vertex x appears. Suppose also that
Cj = {a,b,c} and Ck = {a,b,d}, with j < k. Since x and d have two common
neighbors, those neighbors both appear in cliques Cp,...,Ck, and perhaps others.
60
This includes Cj, so those two common neighbors must be a and b, contradicting
x#N[[a,b]].
We conclude that Se is not a Type (3c) set.
Case 4: The set Se is a Type (3d) set. Precisely those arguments used in Case 3
of this proof (with as and b's interchanged) convince us that Se is not a Type
(3d) set.
The four cases presented convince us that x G Se, and therefore Se is a
maximal clique in N2(G).
Lemma 10 If edge [a, b] is a Type 4 nonsimplicial edge of G, then the sets in S'
associated with it are maximal cliques in N2(G).
Proof: Suppose Se G S' and Se is associated with nonsimplicial Type 4 edge
[a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths
of length 2 from x to every vertex in Se; we will show x 6 Se. Assume not.
Case 1: The set Se is a Type (4a) set. Then x is not in Se, the union of all cliques
of size at least 4 containing [a, b].
Subcase a: x G N[[a, 6]]. Note x ^ a, b, since o, b G Se. Then {x,a, b} is a
maximal clique of G, and hence x has no neighbors in N([a, 6]). We see that there
are two paths of length 2 from x to every vertex in Se {a, b} (one path through
61
a and one path through b). Thus x must have two paths of length 2 to each of a
and b. We have one path of length 2 from vertex x to b through vertex a, and we
need another. Hence there exists v g iV[[a, b]\ such that [x,v\, [v,b\ G E(G), and
Subcase b: x Â£ iV[[a, 6]]. Without loss of generality assume x G Cm im
plies m < i. Let Cq be the first clique in <7*,..., Ci+ki of size > 4. Suppose
{o, b, /, g} C Cq. We show q = i. If q ^ i, then Ci is a clique of size 3, let
Ci = {a, b, h}. Since x JV[[a, 6]] and there are two paths of length 2 from x to g,
there exists v G V(G) such that [x,v], [v,g\ G E(G). By the consecutive ranking
of the cliques of G, we have v h. But then {o, b, h, g} is contained in a maximal
clique of G, contradicting the maximality of {a, b, h} as a clique, so q = i. This
same argument convinces us that the cliques of size at least 4 containing [a, b]
occur consecutively and at the beginning of the list Ci,..., Q+fci. Suppose the
number of maximal cliques of size at least 4 containing both a and b is n. Then
they are Ci,..., Cj+71_i Also, suppose the number of maximal cliques of size =
3 containing both a and b is t. Those cliques are Ci+n,..., Ci+n+ti = Ci+ki
Since [a, b\ is a Type 4 nonsimplicial edge, we have n, t ^ 0.
a
x
we have a 4fan about [a, b] hinged at b, a contradiction. q b v
62
If n > 2, then the arguments used for a Type (1) set (see proof of Lemma 1)
convince us that G is not interval, a contradiction. We conclude that Se is not a
Type (4a) set.
We must consider the instance where n = 1. Suppose {a,b,g,h} C Ci, and
cliques Ci+i,..., Ci+ki are of size 3. Note that n = 1 implies Se = C{. Since
x Â£ iV[[a, b]], without loss of generality suppose [x, 6] Â£ E(G).
If a; is adjacent to 3 or more members of Ci {&}, then we contradict the
maximality of Ci = Se as a set in S', as {x} U C* is contained in some set
of S' associated with a different nonsimplicial edge of G.
If x is adjacent to exactly two members p and q of Ci {6}, then there
exist p' and q' G V(G) such that [x,p'], \p',p], [x, q'], \q', q) G E{G). Note
that \p', q], [q',p] ^ E(G), since this would create a set in S' associated with
nonsimplicial edge \p,q\ that contains both x and Ci, a contradiction. This
also explains why p' ^ q'. Then the subgraph induced on x,p,q,p',q', and
b, shown here contradicts the fact that G is an interval graph.
Suppose x is adjacent to exactly one member of Ci. If a; is adjacent to a, we
know of one path of length 2 from x to b (through a), and we know there
exists b' G V(G) such that [x,b'],[b',b\ G E(G). Since [x, b] Â£ E(G), we
know [b',a] G E(G), otherwise we have a chordless 4cycle xabb'. Because
63
/'
the maximal clique containing {a, b', x} occurs before C; in the consecutive
ranking of G's maximal cliques, we know {a, b, b'} C Q, but this contradicts
the fact that x is adjacent to only one member of Cj (recall [x, 6'] G i?(G)).
We conclude that [a;, a] Â£ E(G).
It remains to consider the case that xs one neighbor in C,, g, is neither a
nor b. Note that a and b have no common neighbors that are neighbors of x
other than g, by consecutive ranking and the fact that Ci is the first clique in
the ranking to contain both a and b. Then there exists V G V (G) such that
[x,b'],[b',b] G E(G). We know [b',g] G E(G), otherwise we have chordless
4cycle xb'bg. Also, there exists a! G V(G) such that [re, a'], [o', a] G E{G),
and we know [a!,g] G E(G), otherwise we have chordless 4cycle xa'ag.
From the above, we know [o', 6], [b',a] E(G). Let Q+i = {a, b, c}. Then
the graph induced on vertices a', a, c, b, band g indicates that G is not an
interval graph, a contradiction.
64
If x is adjacent to no members of C*, then there exist a',b' G V(G) such
that [rr, a'], [aa], [rr, b'], [b', b] G E{G). Notice that a and b have no common
neighbor that is adjacent to x, since Q is the first clique in the ranking to
contain both a and b. Hence [a'b],[b',a] Â£ E(G). When we consider the
graph induced on vertices x, a', a, b, and b1, we see that we have chordless
4cycle a!abb' if [a1, b'] G E(G) and chordless 5cycle xa'abb' otherwise. Both
possibilities contradict the fact that G is an interval graph.
Subcases a and b convince us that x G Se or Se is not a Type (4a) set.
Case 2: The set Se is a Type (4b) set. Then x Â£ Se = N([a, 6]).
Subcase a: x G N[[a, 6]]. Without loss of generality suppose x = a. It is clear
that there are at least two paths of length 2 from x = a to any vertex in a clique
of size at least 4 containing a and b. Let {d,a,b} be a maximal clique of G.
There is a path of length 2 from x to d, through b, but there has to be another
such path. Hence there exists v G V(G) such that [a;, v\, [w, d\ G E(G). This
65
creates a 4fan about edge [a,b], a contradiction. We conclude that x Â£ AT[[a, &]]
or x e Se = N([a, 6]).
Subcase b: x Â£ iV[[a, 6]]. Again, suppose x e Cm implies m < i. Suppose
[a, 6] is contained in exactly n maximal cliques of size at least 4. By the same
argument as in Case 1, Subcase b of this proof, we know these n maximal cliques
occur consecutively and at the beginning of the list Ci,..., Ci+k^i. Thus Ci+n is
the first maximal clique in the ranking that contains both a and b and is of size 3.
Let Ci+n = {a, b, c}. Since x and c have two common neighbors, and since C2+7i
is the first clique in the ranking in which c appears (by maximality of cliques in
the ranking), those two common neighbors must be in Ci+n, and therefore must
be a and b. This contradicts the fact that x $ Se = N([a, b]).
We conclude from the two subcases that x Â£ Se or Se is not a Type (4b) set.
Cases 1 and 2 convince us that x 6 Se, and thus Se is a maximal clique in
N2(G). u
Lemma 11 If edge [a, 6] is a Type 5 nonsimplicial edge of G, then the sets in S'
associated with it are maximal cliques in N2(G).
Proof: Suppose Se Â£ S' and Se is associated with nonsimplicial Type 5 edge
[a, 6]. To show that Se is a maximal clique in N2(G), assume there are two paths
of length 2 from vertex x to every vertex in Se; we will show x Se. Assume not.
66
Case 1: The set Se is a Type (5a) set. Then Se is the union of all cliques of size
at least 4 containing edge [a, b], and x Â£ Se.
Subcase a: x G N[[a, 6]]. Then {a, b, re} is a maximal clique of G, and x has
no neighbors in N([a, 6]). We can easily identify two paths of length 2 from x
to every vertex in Se {a,b}, one through a and one through b. We consider
the fact that there are two paths of length 2 from x to b. We find one such path
through a, and conclude that there exists v G V(G) such that [x, v\, [v, b] G E(G).
Similarly, there are two paths of length 2 from x to a, and since [v, a\ ^ E(G),
there exists y G V(G) such that [a:, y], [y, a] G E{G), and [y, b] E(G). Let q be
some neighbor of [a, b] other than x. Then [q,x\ E(G), and the subgraph of G
induced on vertices a, b, x, y, v, and q indicates that G is not an interval graph, a
contradiction.
Subcase b: x jV[[a, 6]]. Again suppose x G Cm implies m < i. As in Lemma
4, Case 1, Subcase b and Lemma 4, Case 2, Subcase b, the cliques of size at least
y
q b v
67
4 containing [a, 6] occur consecutively and at the top of the list Ci}..., Ci+k1
Again, if [a, b] is contained in at least two cliques of size at least 4, then the
argument in the proof of Lemma 1 convinces us that G is not interval.
It remains to consider the case that [a, 6] is contained in exactly one maximal
clique of size at least 4 in G. Then Se = CiD {a, b,p, q}. The same argument as
was used in the proof for set Type (4a) (Lemma 4, Case 1, Subcase b, n = 1) is
appropriate here, and convinces us that G is not interval.
The subcases convince us that Se is not a Type (5a) set.
Case 2: The set Se is a Type (5b) set. Then x Â£ Se = N([a, 6]).
Subcase a: x E iVjfa, b]\, without loss of generality x a. We claim [a, b] is
in at most two maximal cliques of size 3. Suppose not. Suppose Cu = {a,b,c},
Cv = {a,b,d}, and Cw = {a,b,f} are maximal cliques of G. Notice that i <
u,v,w < i + k 1. Suppose without loss of generality that i
i + k 1. Since there are two paths of length 2 from x = a to c, there exists
y E V(G) such that y Â£ iV[[a, 6]] and [a, y\, [y, c] E E(G). As a result we see that
[y, b] Â£ E(G). By maximally of cliques in the ranking, and because y AT[[a, 6]],
one of the following must be true:
cECi or cECi+ki (1).
Note that [y, d] and [y, /] are not edges of G, since these two edges create
68
chordless 4cycles ycbd and ycbf respectively. Thus we can use precisely the
same argument as above to conclude that one of the following must be true:
d E Ci or d 6 Ci+ki (2),
and one of the following must be true:
f E Ci or / E Ci+ki (3).
Clearly it is not possible for (1), (2), and (3) to all hold, so [a, b] is in at most
two maximal cliques of size 3 in G.
Suppose [o, 6] is in exactly one maximal clique of size 3 in G, say {a, b, c}.
Again, vertex y exists such that [y,b] Â£ E(G), and [y,a],[y,c] E E(G).
Then we have a 4fan about [a, b] hinged at a, and N([a, &]) is properly
contained in a set Sq E S', where Sq is a Type (5c) set associated with edge
[a, 6], contradicting the maximally of Se in S'.
Suppose [a, 6] is in exactly two maximal cliques of size 3, {a,b,c}, and
{a, b, d}. Statements (1) and (2) must hold, so without loss of generality, let
Ci = {o, b, c}, and Ci+*_i = {a, b, d}. The arguments just used convince us
that y and z exist such that [a, y\, [y, c], [a, z\, [z, d] E E(G) and [y, 6], [z, b]
E(G). We know [y, z] Â£ E{G), since y E Cm implies m < i, and z E Cn
69
implies n > i + k 1. Then we have an (induced) 4fan about [a, b] on
vertices a, b, c, d, y, and y x = a z
Then the Type (5c) set associated with this 4fan and edge [a, b] properly
contains N([a, 6]), a contradiction to the maximality of Se in S'.
We conclude that x Â£ N[[a,b]].
Subcase b: x g iV[[a, 6]]. Since the argument in the proof of Lemma 4, Case
2, Subcase b does not involve a 4fan about [a, b], we may use the same argument
to arrive at a contradiction in this case.
We conclude from the two subcases that x E Se or Se is not a Type (5b) set.
Case 3: The set Se is a Type (5c) set. Set Se is associated with a 4fan about
[a, b] hinged at a. Suppose the 4fan is on vertices a, b, c, d, f,and g, as depicted
in the figure. fag
Then x Â£ Se = {a, c, d} U {all cliques of size at least 4 containing [a, 6]} {6}.
At least one of [6, /], [6, g] 0 E(G), say [b,g\ Â£ E(G).
70
We claim [d,/] ^ E(G). This is because [d, /] e E{G) implies [ft,/] e E(G)
(otherwise we have chordless 4cycle bdfc). However, if [d, /], [b, f]
Se is properly contained in UCp, where a,b e Cp and \CP\ > 4, contradicting the
maximality of Se in S'. Hence [d, f ] ^ E(G). Then [c, g] Â£ E(G), since existence
of [c, g] would create the chordless 4cycle bdgc. fag
Subcase a: x N[[a, 6]].
Suppose x = b. Certainly there are two paths of length 2 from x = b to a
and two from x = ft to any vertex in UCp, where a, ft 6 Cp and \CP\ > 4. We
know of one path of length 2 from x = ft to d and one from x to c. There
is another path of length 2 from x = ft to d, so there exists y G V(G) such
that [ft, y], [y, d] G E(G). fag
Since G is interval, [o, y] 6 E(G), otherwise we have the following subgraph
in G.
71
y
X =
c
a
9
y
Thus we have the following subgraph in G. /
a
9
If [6, /] or [y, c] G E(G), then Se is properly contained in UCp, where a, b G
Cp and \CP\ > 4, so [b, /], [y, c] g E(G). (Depicted above.)
There is another path of length 2 from x = b to c, so there exists z EV (G)
such that [6, z], [z, c] G E{G). Consider the subgraph of G induced on
vertices a, b, c, d, /, and z.
We know [a,z] G E(G), or else G is not interval. However, [a, z] G E(G)
b
fad
72
implies Se is properly contained in UCv, where a,b G Cp and \CV\ > 4. We
conclude that x ^ b.
Suppose x = v, where {a, b, u} is a maximal clique of G, v c,d. Then
[v,d],[v,c] E(G). It is clear that there are two paths of length 2 from
x = v to every vertex in Se except a. We know of only one path of length
2 from x = v to a at this point, and that path is through b. Notice that
[v,f],[v,g] & E(G), since existence of these edges would create chordless
x v
4cycles vfad and vbdg respectively.
fag Then there exists
y eV(G)~ {b, c, d, /, #} such that [v, y], [y, a] e E(G).
We see that [y, 6] ^ E(G), since this would create clique {a, b, v, y}, contra
dicting the maximality of clique {a, b, u}. Then [b, /] E(G), since lack of
this edge would create induced subgraph NCj on vertices b, c, d, f, g, v, and
V
73
But then the set in S associated with the 4fan about [a, 6] hinged at a
induced on vertices a, b, d, g, v, and y is {v, d, a} U {UCp, where a,b e Cp
and \CP\ > 4}, which properly contains Se, a contradiction.
We conclude that x JV[[a, b]\.
Subcase b: x iV[[a, b]]. By the definition of a 4fan, {a, 6, d} is a maximal
clique of G\ let Cj = {a, b, d}. fag
Suppose without loss of generality that x 6 Cm implies m < i. By the same
reasoning as in the proof of Lemma 4, Case 1, Subcase b, the maximal cliques of
G of size > 4 that contain [a, b] occur consecutively and at the beginning of the
list Ci,..., Ci+k1 Thus Cj is the first clique in the ranking in which vertex d
appears, and i
since d G Se. By the consecutive ranking, those neighbors are a and b. However
x Â£ 7V[[a, 6]], so x cant possibly be adjacent to both a and b. Hence we have a
contradiction and conclude that Se is not a Type (5c) set.
Case 4: The set Se is a Type (5d) set. Precisely those arguments used in Case 3
of this proof (with as and 6s interchanged) convince us that Se is not a Type
(5d) set.
74
We conclude from Cases 1, 2, 3, and 4 that x Â£ Se and Se is a maximal clique
in N2(G).
Lemma 12 If a set in S' corresponds to a maximal clique of size at least 4 in G
that has no nonsimplicial edges, then the set is a maximal clique in N2(G).
Proof: Suppose Cj = Se Â£ S' and Cj is a maximal clique of G of size at least
4 with no nonsimplicial edges. To show that Se is a maximal clique in N2(G),
assume there are two paths of length 2 from vertex x to every vertex in Se; we
will show x Â£ Se. Assume not. Also suppose {t, u, v, w} C Se. Since Se has no
nonsimplicial edges, any vertex not in Se (in particular x) is adjacent to at most
one vertex in Se.
Subcase a: Vertex x is adjacent to one vertex v in Se. There is another path of
length 2 from x to u, so there exists a vertex y Â£ Se such that [z, y], [y, u] Â£ E(G).
But chords [u,x] and/or [y,v] cause edge [u, v] to be nonsimplicial, so we have
chordless 4cycle uyxv in G, contradicting the fact that G is an interval graph.
Subcase b: Vertex x is adjacent to no vertex in Se. There are two paths of
length 2 from x to u, so there exist vertices y2 Â£ V (G) such that y\,y2 & Se and
[x,yi],[yi,u],[x,y2],[y2,u] Â£ E(G). Note that [yi,v\, [y2,v\ <Â£ E{G), since [u,n]
is not nonsimplicial. Hence there exist zi,z2 Â£ V(G) such that Zi, z2 Â£ Se and
[x,zi], [zi,v], [x,z2], [z2,v] Â£ E(G). Note, as before that [zi,u],[z2,u] Â£ E(G),
75
since [it, v] is not nonsimplicial. Consider the subgraph of G induced on vertices
uy2xz\v. We know [y2, Zi] ^ E(G), since this would create chordless 4cycle
uy2ziv. But the 5cycle uy2xziv is not chordless, since G is an interval graph. In
fact, G interval implies that [x,u], [x, v\ e E(G). Then {x,u,v} is a clique of G,
contradicting the fact that [u, v] is not nonsimplicial.
Hence x G Se and Se is a maximal clique in N2(G).
Theorem 14 The collection of sets S' for a given interval graph G is a (2)
neighborhood cover of G consisting of maximal cliques of N2(G).
Proof: This theorem follows directly from Lemmas 7 through 12.
Corollary 4 An interval graph G has an interval (2)neighborhood graph if and
only if S' has a consecutive ranking.
We can use Corollary 4 to identify a class of interval graphs whose (2)neighborhood
graphs are interval.
Corollary 5 If G is an interval graph and the nonsimplicial edges of G are
contained only in maximal cliques of size at least 4, then N2(G) is an interval
graph.
76
Proof: Suppose G is an interval graph in which all nonsimplicial edges occur
in maximal cliques of size at least 4. Let Ci,...,Cr be a consecutive ranking of
the maximal cliques of G.
If G contains no nonsimplicial edges, then the only elements of S' are those
maximal cliques of size at least 4. Certainly S' has a consecutive ranking, and
thus (by Corollary 4) N2(G) is an interval graph.
Assume G has at least one nonsimplicial edge. Define C([a, 6]) to be the union
of those cliques of G which contain nonsimplicial edge [a, b]\ then C([a,b]) =
iV[[a, 6]] and this set is the union of some consecutive cliques in the ranking
C\,... ,Cr. The set S consists of cliques of size at least 4 with no nonsimplicial
edges, and the sets C([a, 6]) (one such set for every nonsimplicial edge [a,b]). In
S', we have only the maximal sets of S; S' is essentially a collapsed version
of the consecutive ranking Ci,..., CT, so S' certainly has a consecutive ranking,
and N2(G) is an interval graph.
77
5. The (2)Neighborhood Graphs of Interval Graphs Are Weakly Chordal.
5.1 Introduction
The necessary and sufficient condition given in Chapter 4 for an interval graph
to have an interval (2)neighborhood graph is a bit unwieldy. We concentrate in
this chapter on the properties of interval graphs whose (2)neighborhood graphs
are not interval. We will need the definition that follows.
Definition: A graph G is weakly chordal if G contains no chordless cycles of length
5 or greater.
Notice that weakly chordal graphs are perfect graphs.
5.2 If G is interval, then N2(G) is weakly chordal.
Theorem 15 If G is an interval graph, then N2(G) is a weakly chordal graph.
Proof: Suppose G is an interval graph and N2(G) contains the chordless cycle
V\V2 ... VkiVk, where k > 5.
Suppose every pair of consecutive vertices on the cycle viv2 ... v^iVk is adja
cent in G. Since G is interval, some of the chords of the cycle are also in E(G).
78
However, no matter which chords of the cycle are in E(G), some pair of noncon
secutive vertices of the cycle ends up diagonally opposed on some 4cycle of G.
This creates a chord in the chordless kcycle in N2(G), a contradiction. Hence,
there exists some consecutive pair of vertices on the ftcycle, say V\ and v2, that
is not adjacent in G.
Suppose without loss of generality that Ci,C2,.. .CT is a consecutive ranking
of the maximal cliques of G in which the maximal cliques containing appear
strictly before those containing v2 (recall [vi,v2] E(G)).
Since V\ and v2 are adjacent in N2(G), iV(wi) fl iV(?;2) > 2 in G. Suppose
Xi and x2 are both adjacent to V\ and v2 in G. Edge [xi,x2] E E(G), since G is
interval.
Since [ui,Ufc] E(N2(G)), \N(vk) H N(v{) > 2 in G. Notice that Vk is not
adjacent to both X\ and x2 in G, since if it were, edge [ufc, n2] would be in N2(G).
Thus the maximal cliques containing vertex Vk appear either before or after those
containing both vertices xi and x2 in the consecutive ranking. If the maximal
cliques of G containing vertex Vk appear after those containing both X\ and x2
in the consecutive ranking, then the common neighbors of vertices V\ and Vk (of
which v2 is not one, since [wi, v2] ^ E(G)) are also adjacent to v2. This forces
[vk>v2} Â£ E(N2(G)), a contradiction. Hence the maximal cliques of G containing
79
Vk all appear before those containing both X\ and X2 in the consecutive ranking.
Similar reasoning convinces us that the maximal cliques of G containing V3
all appear after those containing both x\ and x2 in the ranking.
Extending the argument, we find that the maximal cliques containing Vki
through Ufi+2, respectively, appear before those containing both x\ and x2 in
the ranking.
Case 1: k is odd. In this case, we find that the maximal cliques containing
t>3 ... Wpii appear after those containing both xi and x2. However, the maximal
cliques of G containing vertex Ufk^+1 must appear both before and after those
containing Xi and x2 in the ranking, a contradiction. We conclude that N2(G)
contains no induced odd cycle of length 5 or greater.
Case 2: k is even. Here we find that the maximal cliques of G containing v3 ... Vk
2
appear after those containing both xi and x2 in the ranking. Since the maximal
cliques of G containing Vk, 9 appear before those containing Xi and x2 in the rank
ing and those containing U+1 appear after, we know that two common neighbors
of Vk+2 and Vk+l are adjacent to Xi, x2, and all of the common neighbors of X\
and x2 in G. However, this creates unwanted chords (for example [ui,U+1]) in
N2(G), a contradiction. We conclude that N2(G) contains no induced even cycle
of length 6 or greater.
80
Hence, if G is an interval graph, N2(G) is weakly chordal.
5.3 What if N2(G) contains a chordless 4cycle?
Conjecture 1 If G is an interval graph and N2(G) contains a chordless 4cycle,
then G contains one of the following as an induced subgraph.
Figure 5.1: If N2(G) has a chordless 4cycle as a generated subgraph, then G has
one of the graphs above as a generated subgraph.
Beginning of Proof: Suppose abed is a chordless 4cycle in N2(G). Then a
and b are diagonally opposed on some 4cycle of G.
Case I. A 4cycle in G on which a and b are diagonally opposed is contained in a
complete subgraph. Suppose the subgraph of G induced on vertices a, b, x, and
81
y in G is complete.
Since [c, d] is an edge of N2(G), c and d have (at least) two common neighbors
in G. The possibilities (without loss of generality) are:
(1) c and d are both adjacent in G to a and b,
(2) c and d are both adjacent in G to a and x,
(3) c and d are both adjacent in G to x and y,
(4) c and d do not have two common neighbors in the set {o, b, x, y}.
Suppose (1) holds.
Then [c, d], [c,x\, [c,y], [d,x], [d,y\ Â£ E(G). This is because any one of these
edges would create chord [a, c] or chord [b, d] in N2(G). Since c and a are both
adjacent to b in G c and a have no other neighbors in common in G. Similarly,
b and d have only one common neighbor in G, vertex a. Thus there exist two
other vertices, say v and w, so that [a,v], [d,v], [c,w], [b,w] 6 E(G). Hence we
have the following graph as an induced subgraph of G.
Suppose (2) holds.
Then we have the graph shown in the figure below as a subgraph of G, and
as a result in N2(G) we have edge [6, d], a contradiction.
C
a
v
82
b a c
y x d
Suppose (3) holds.
Then we have the graph shown in the figure below as a subgraph of G, and
as a result [a, c], [6, d] e E(N2(G)), a contradiction.
axe
b y d
Suppose (4) holds. Without loss of generality, there are 3 subcases to consider.
(4)[1] c and d are both adjacent to a in G,
(4) [2] c and d are both adjacent to x in G,
(4) [3] c and d have no common neighbors in the set {a,b,x,y}.
We first consider the case (4) [1].
Let another common neighbor of c and d be labelled v (see the figure above).
Note v g {a,b,x,y}, since we are in Case (4)[1]. Since G is chordal, either [a,v]
83
or [c, d] is an edge of G, but not both, since the presence of both in G would
produce [a, c] in N2(G).
Suppose [a, v\ e E(G) and [c, d] g E(G). Because b and d have a as a common
neighbor in G, there must be no other vertices to which both b and d are adjacent.
The same is true for a and c, which are both adjacent to v in G. These two facts
force the following nonedges in G: [d,y],[d,x],[b,v],[c,b],[c,x], and [c, y]. The
forced nonedges of G are indicated in the figure below with dotted lines.
The only remaining possible edges between the vertices mentioned thus far
are [y,v], [x,v], and [b,d]. If [b,d\ e E(G), then [x,v], [y,v\ Â£ E(G), since these
edges would create chordless 4cycles bdvx and bdvy respectively in G. This would
contradict the fact that G is an interval graph. Thus if [b,d] 6 E(G), we have
the following induced subgraph in G.
Because b and c have a as a common neighbor, and no other vertices in the set
{a, b, c,d,v, x, y} are adjacent to both b and c, there exists a vertex q, not in the set
84
{a, b, c, d, v, x, y} such that [6, q], [c, q\ G E(G). There is only one way to consecu
tively rank the four maximal cliques of G containing {a, b, x, y}, {a, b, d}, {a, d, ?;},
and {a, v, c}. In fact, the listing given is the only way to consecutively rank them.
Since the ranking is consecutive and [6, q], [c, q] G E(G), q is adjacent to o, d, and v
(see the figure below). This forces edges [a, c] and [6, d] in N2(G), a contradiction.
We conclude that [b, d] $ E(G).
Thus we have in G the subgraph shown in the figure below, possibly with
edge [d, rr] or [v,y\ (perhaps both).
;y a
X b
If [i>, rc] is an edge of G and [v,y\ is not (see the figure below), then there
exists a vertex q that is adjacent to both b and c in G (otherwise they only have
a as a common neighbor).
85
By consecutive ranking of the maximal cliques of G, q is in a maximal clique of
G containing a, x, and v, forcing [a, c] into the edge set of N2{G), a contradiction
(see the figure below).
d
y *
The same reasoning as above convinces us that it is not possible for [v, y] to
be in the edge set of G if v, x] is not.
Can both [u, y\ and \v, x] be edges in G1 The answer is no. If they both were,
then we would have the graph shown in the figure below as an induced subgraph
of G.
d
y *
Again, the consecutive ranking of the maximal cliques of G is forced to have a
maximal clique containing {a, x, y, v} between a maximal clique containing b and
one containing c. Vertices b and c must have a common neighbor q that is not
in the set {a, b, c, d, v, x, y}. Then the consecutive ranking just mentioned forces
86
q to be adjacent to a, x, y, and v. Then a and c are both adjacent q and v, a
contradiction.
The only possibility that remains to be considered in this subcase of (4) [1] in
which [a,v] Â£ E(G) and [c,d\ 0 E(G) is the one in which neither [v,y] nor [v,x]
is in E(G). Thus we have the subgraph shown below induced in G.
Let q be adjacent to both a and d, with q 0 {a, b, c, d, v, x, y}. Edges [b, q] and
[q, c] in G would force edges [b, d] and [a, c] in N2(G), so neither [b, q] nor [q, c] is
an edge in G. Thus there exists another vertex p not in {a, b, c, d, v, x, y, q} that
is adjacent to both b and c. We must consider the 4cycle acpb in G. Since G is
interval, this 4cycle must have at least one chord. However, both chords [a,p]
and [b, c] force a and c to be diagonally opposed on 4cycles of G, thus forcing
edge [a, c] into N2(G), a contradiction.
We conclude that in case (4) [1], it is not the case that [a, u] Â£ E(G) and
[c,d\tE(G).
Recall that it is not possible to have both edges [a, v] and [c, d] in E(G). Thus
it remains to consider the case where [c,d] Â£ E(G) and [a, v] E(G). Because
a and c are both adjacent to d, the following nonedges are forced: [c, b], [c, x],
87
and [c, z/]. Since b and d are both adjacent to a, [b,v\, [d,y], and [d,x] are forced
nonedges in G (see the figure below).
The edges that we can possibly add are: [v, y], [v, x], and [b, d].
Suppose [b, d] G E(G). Then \v,y\,[v,x\ Â£ E(G), since they create chordless
4cycles in G. Thus [b, d] G E(G) implies the graph below is an induced subgraph
of G.
y a c
x b d v
Now suppose [b, d] 0 E{G). We must explore the possibilities for [v,y] and
[v,x]. If we consider the graph below, and the consecutive ranking of the cliques
of G, we see that neither [v,y] nor [u,:r] is in E(G), since neither c nor d is
adjacent to x or y in G.
c
88
Vertices a and d are both adjacent to vertex c. Let q be another neighbor of a
and d, q Â£ {a, b, c, d, v, x, y}. The following nonedges are forced: [<7, u], [<7, c], [q, 6].
the only possible edges to consider at this point are [q, x] and [9, y] (see the figure
below).
c
Suppose [<7,2;] E(G) and [q, y] g E(G)? Then we are locked into one choice
for the consecutive ranking of the maximal cliques of G that contain {a, b, x, y},
{a, x, q}, {a,q,d}, {a,d,c}, and {d,c,v} respectively, as the figure below indi
cates.
c
Thus far, We are aware of one common neighbor of b and c, vertex a. No
other vertex in the set {a, b, c, d, v, x, y, q} is adjacent to both b and c. Let p be
a vertex adjacent to both b abd c. Then by the consecutive ranking, p is in a
89
maximal clique with a, x, and q and in another one with a, q, and d. Then a and
c are both adjacent to p and to d, a contradiction. We conclude that it is not the
case that [q,x] G E(G) and [q,y] 0 E(G).
Suppose we have [q,y] G E(G) and [q,x\ 0 E(G). the same argument as
directly above leads to a contradiction.
It remains to consider the case that both [q,x] and [q,y] G E(G). A look
at the figure below convinces us that the only possible ranking of the maximal
cliques of G containing {a, b, x, y}, {a,x,y,q}, {a,q,d}, {a, d, c}, and {d,c,v}
respectively is in precisely the given order.
c
Vertices b and c have some common neighbor p g {a, b, c,d,v, x, y, q}. Thus,
by consecutive ranking, p is adjacent to a,q,d,x, and y. However, p adjacent
to both b and d implies [6, d] G E(N2(G)), a contradiction. We conclude that
neither [q, y] nor [q, x) is an edge of G.
90
c
V
q
Thus the graph shown above is an induced subgraph of G. There must exist
a vertex, m Â£ {a, b, c, d, v, x, y, q}, that is adjacent to both b and c. However,
this creates 4cycle acmb, and both chords [a, m] and [6, c] force [a, c] into the
edge set of N2(G), a contradiction. We conclude that it is not possible to have
lb,d)$E(G).
This concludes subcase (4) [1]. Hence, if the two common neighbors of c and
d are a and v, where v Â£ {a, b, x, y}, then G has the graph depicted below as an
induced subgraph.
y a c
x b d v
This concludes the proof for most of Case I; it remains to consider subcases
(4) [2] and (4) [3], as outlined on page 83 Once these subcases and Case II (no
4cycle in G on which a and b are diagonally opposed is contained in a complete
subgraph) are verified, the conjecture will be proved true.
91
6. Conclusion
There are many directions in which the research discussed here can be taken for
future study. We conclude by listing some of those possibilities.
As mentioned at the end of Chapter 2, it remains an open problem to fully
classify those (trianglefree) graphs which are (2)neighborhood graphs, and the
question for [2]neighborhood graphs is yet to be considered.
The necessary and sufficient condition for an interval graph to have an interval
(2)neighborhood graph given in Chapter 4 can certainly be further explored. It
would be nice to find more classes of interval graphs which satisfy the necessary
and sufficient condition. To this end, the work begun in Chapter 5 will most
likely be helpful. Completion of the proof of Conjecture 1 is an obvious starting
point.
Future work should also include attempts to generalize other results on neigh
borhood graphs to (p)neighborhood graphs. Some questions to consider are
when is a graph isomorphic to its (p)neighborhood graph? and when is the
complement of G isomorphic to NP(G)? There are many other results for the
case p = 1 whose generalizations to larger p would make an interesting study.
92
References
[1] B. D. Acharya and M. N. Vartak. Open neighborhood graphs. Research Re
port 7, Indian Institute of Technology Dept, of Mathematics, 1973. Bombay
400 076, India.
[2] C. A. Anderson, L. Langley, J. R. Lundgren, and S. K. McKenna, P. A. and
Merz. New classes of pcompetition graphs and ^tolerance competition
graphs. Congressus Numerantium, 100:97107, 1994.
[3] J. W. Boland, R. C. Brigham, and R. D. Dutton. The difference between
a neighborhood graph and a wheel. Congressus Numerantium, 58:151156,
1987.
[4] J. W. Boland, R. C. Brigham, and R. D. Dutton. Embedding arbitrary
graphs in neighborhood graphs. Journal of Combinatorics, Information,
and System Sciences, 12:101112, 1987.
[5] R. C. Brigham and R. D. Dutton. A characterization of competition graphs.
Discrete Applied Mathematics, 6:315317, 1983.
93

Full Text 
PAGE 1
/ COMPETITION GRAPHS AND THEIR GENERALIZATIONS by Patricia A. McKenna B.A., Potsdam College of the University of New York, 1988 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1994
PAGE 2
This thesis for the Doctor of Philosophy degree by Patricia A. McKenna has been approved for the Department of Mathematics by Date
PAGE 3
McKenna,Patricia A. (M.S., Applied Mathematics) Competition Graphs and Their Generalizations Thesis directed by Professor J. Richard Lundgren ABSTRACT The concept of the competition graph has been extensively studied and gen eralized since its introduction in the late sixties. We consider the generalizations known as the pcompetition graph and the competition graph. We identify the chordal graphs on 3 or more vertices as 3competition graphs. We identify some graphs which are the pcompetition graphs of loopless Hamiltonian or loopless strongly connected digraphs. Next, using a construction of Myciel ski as well as other methods, we generate large classes of graphs which fall into one category but not another. For example, we construct large classes of graphs which are mintolerance competition graphs but not competition graphs. We also present an algorithm for generating graphs which are competition graphs but not 2competition graphs. This abstract accurately represents the content of the candidate's thesis. I rec ommend its publication. ill
PAGE 4
Contents 1 Introduction .. . . . . . . . 1 2 p Competition Graphs . . . . . . 5 2.1 Preliminaries . . . . 5 2.2 3Competition Graphs of Arbitrary Digraphs 7 2.3 p Competition Graphs ofLoopless Hamiltonian and Strongly Connected Digraphs . . . . . . 11 3 Tolerance Competition Graphs G e 4 e e e a e 14 3.1 Preliminaries . . . 3.2 MinTolerance Competition Graphs 3.2.1 The Basics . . 3.2.2 MinTolerance Competition Graphs and a Construction of Mycielski . 3.3 MaxTolerance Competition Graphs 3.4 SumTolerance Competition Graphs . 3.5 TwotPTolerance Competition Graphs . 3.5.1 Competition Graphs . . 14 16 16 18 28 29 31 33 3.5.2 !Competition Graphs Which Are Not 2Competition Graphs 36 IV
PAGE 5
3.5.3 Creating !competition graphs which are not 2competition graphs. . . . . . . . 39 3.5.4 More on !competition graphs which are not 2competition graphs. . . . . . . 41 4 Conclusion . . . . . . . . 43 v
PAGE 6
List of Figures 1 G is the competition graph of D. Note that the inset of any vertez in D forms a clique in G. . . . . . . 1 2 G is the 9competition graph of D. Note that the inset of any vertez 3 4 5 in D does not necessarily form a clique in G. St, 82, and SJ form a 2ECC for G. .... G of Figure 3 is the 2competition graph of D. G is a maztolerance competition graph. . 5 6 6 15 6 D is the digraph for which G is the maztolerance competition graph. 16 7 G is a mintolerance competition graph. . 8 Is this graph a mintolerance competition graph? .. 9 p.(C5), also known as Grotzsch's graph. 10 p.(C4). 11 p.(CJ). 12 p.(K4). 13 G is a sumtolerance competition graph. 14 The complete bipartite graph, K3 3 15 The complete bipartite graph K2 6 16 The graphs G and {GM}Ul2. ... 17 G is a maztolerance competition graph. V1 . 17 18 19 20 21 22 29 30 32 34 35
PAGE 7
18 G is not a 1competition graph and not a 2competition graph. 37 19 Graphs which are 1competition graphs and not 2competition graphs. 39 20 A graph which is a 2competition graph of an arbitrary digraph with loops, but not of a digraph without loops. . . 43 vii
PAGE 8
1 Competition graphs were first introduced by Joel Cohen in 1968 [5] in relation to food webs. Since then, the topic has been extensively studied and generalized, proving to be an area of research in which graph theorists have been limited only by their imaginations. For basic graph theory definitions and terminology, the reader is referred to Roberts [16). Basic knowledge of competition graphs is helpful before proceeding to generalizations such aspcompetition graphs (Chapter 2) and tolerance competition graphs (Chapter 3). We will start with the definition. The competition graph of a digraph D = (V,A) is the graph G = (V,E) where [:z:,y] E E if and only if 3 z E V such that both (:z:,z) and (y,z) EA. Example 1 Graph G of Figure 1 is the competition graph of digraph D. a b c a b c G: D: f e d f e d Figure 1: G is the competition graph of D. Note that the inset of any verte:z: in D forms a clique in G. A collection C of sets of vertices from a graph G is called an edgeclique cover (ECC) of G if each set in C is either a (not necessarily maximal) clique or the 1
PAGE 9
empty set, and every edge in G is in at least one of the cliques of C. The number of cliques in a smallest edgeclique cover is the edgeclique cover number of G, denoted Oe(G). In studying competition graphs, the importance ofthe edgeclique cover number can not be overstated, as we will see next. The following list summarizes those facts about competition graphs which are most relevant {and sometimes analogous) to topics in later chapters. Some can be modified to apply to pcompetition graphs and/or tolerance competition graphs. All are referred to in later chapters. Fact 1 [1] A graph G is a competition graph of an arbitrary digraph if and only if Oe{G) n. Fact 2 [17] A graph G with n vertices is the competition graph of an arbitrary digraph without loops if and only if G is not K2 and Be( n. Fact 3 [6] A graph G of order n is the competition graph of a Hamiltonian digraph if and only if G has a labeling a1 a2 an of its vertices and an edgeclique cover 02 Cn satisfying ai (j_ Ci,i = 1, ... ,n, ai E Ci+l! i = 1, ... ,n1, and an E C1. Fact 4 [6] H G is a cycle, then G is the competition graph of a Hamiltonian digraph. 2
PAGE 10
Fact 5 [6] H G is a tree on n ;::: 3 vertices, then G is the competition graph of a Hamiltonian digraph. Fact 6 [6] H G is a tree plus an edge, with IV(G)I ;::: 3, then G is the competition graph of a Hamiltonian digraph. Fact 7 [6] H G is a connected trianglefree graph on n > 3 vertices with Be(G) ::; n, then G is the competition graph of a Hamiltonian digraph. Fact 8 [6] The complete graph Kn for n ;::: 3 is the competition graph of a Hamiltonian digraph. Fact 9 [6] H G is a chordal graph on n ;::: 3 vertices, then G is the competition graph of a Hamiltonian digraph. Fact 10 [6] H IV(G)I = n then G is the competition graph of a strongly connected digraph if and only if Be(G) + i(G) ::; n (where i(G) is the number of isolated vertices in G). In the chapters that follow we will use variations of the facts above to explore generalizations of the competition graph. We will present results analogous to Facts 35 and 810 for pcompetition graphs. Finally we will discuss the ways in which the facts above suggest further research In closing, it is worthwhile to make brief mention of some variations of the com3
PAGE 11
petition graph which are neither explored nor generalized here. These are the competitioncommon enemy graph and the niche graph, which are the topics of Scott [18] and Cable, Jones, Lundgren, and Seager [4] respectively. Generaliza tions of these concepts are mentioned in Chapter 4 as possible areas for future research. 4
PAGE 12
2 p Competition Graphs 2.1 Preliminaries The pcompetition graph was first introduced in 1989 by Kim, McKee, McMorris, and Roberts (9]. The pcompetition graph of a digraph D = {V,A) has vertex set V and an edge between z and y if and only if there are distinct vertices a1 aP and arcs {z, ai) and {y, ai) in D for each i p. In other words, the pcompetition graph has an edge between two vertices if and only if those two vertices "compete for" at least p vertices in the digraph. Graph G of Figure 2 is the 3competition graph of D. b b G: D: c d d Figure 2: G is the 9competition graph of D. Note that the inset of any vertex in D does not necessarily form a clique in G. We now define the notion of a pedge clique cover (or pECC) of a graph G. Let F = {St, ... Sr} be a family of subsets of V(G), with repetition allowed. F is a pECC of G if for every set it, ... ip of p distinct subscripts, T = Si1 n ... n Sip is either empty or induces a clique of G, and the collection of sets of the form T 5
PAGE 13
covers all of G. Finally, we define the notion of pedge clique cover number (denoted which is the smallest r for which for which there is a pECC of cardinality r. Example 2 For G shown in Figure 3, we have the following 2ECC: 81 = {a,b,c}, 82 = {a,c,d}, and 83 = {a,b,c,d}. a b G: rsr d c Figure 3: 81, 821 and 83 form a 2ECC for G. We use this 2ECC to createD (see Figure 4), by letting each set of the 2ECC be the inset of a vertex in the digraph. a b D: d c Figure 4: G of Figure 3 is the 2competition graph of D. In this case we have In( d) = 817 In(b) = 82, and In( a)= 83 The following theorem is due to Kim, McKee, McMorris and Roberts [9], and allows us to identify a graph as a pcompetition graph without actually constructing the digraph D. 6
PAGE 14
Theorem __ 1 A graph G with n vertices is a pcompetition graph of an arbitrary digraph if and only if G) :5 n. In this chapter we will focus first on the case where p = 3, identifying some classes of graphs which are 3competition graphs of arbitrary digraphs. Next we will place certain restrictions on D, such as loopless Hamiltonian and loopless strongly connected, and discuss various classes of graphs which are pcompetition graphs of such digraphs 2.2 3Competition Graphs of Arbitrary Digraphs In response to the question, "Are there interesting families of graphs which are 3competition graphs of arbitrary digraphs?" posed by Kim et al. [9), we have identified chordal graphs as such. There are just three exceptions: the paths on 3,4, and 5 vertices (P3 P4 and P5 respectively). Simple counting arguments show that these graphs are not 3competition graphs. For example, consider P4 with vertices labeled consecutively vh v 2 v3 v 4 A minimum covering of edges [v17 v 2 ] and [v2, va) requires the following four sets: {v 1 v 2}, {v 1,v2 va}, {v 1 112 v 3}, { v 2 113 }. We cannot cover the edge [v3 114 ) by simply adding v4 to the three sets containing 113 since we would create the unwanted edge [112 v4). So we are required to add a fifth set, and our minimal3ECC of P4 is {111,112}, {v17v 2,113}, {v17112,v3,114}, 7
PAGE 15
{v2,va, ,v4}, {va,v4} We conclude that 83(P4 ) = 5 > 4, i".e. P4 is not a 3competition graph. Analogous proofs for P3 and P5 are left to the reader. The following lemmas are required to prove that the remaining chordal graphs are 3competition graphs. Lemma 1 Every path on 6 or more vertices is a 3competition graph. Proof: The following sets form a 3ECC for Pn, n;:::: 6, when the vertices of Pn are labeled consecutively v2, ... Vn: 0 Lemma 2 Every tree T on 5 or more vertices that is not a path has a pendant vertex, z, such that T{z} is not a path. Proof: Let be a tree on n ;:::: 5 vertices that is not a path. We need only consider the case that T is the path v1 v 2 ... Vnl with one final vertex,vn, which is adjacent to exactly one of the vi's, 2 :$; i :$; n 2. 8
PAGE 16
H Vn 's neighbor is v2 or Vn2 then Vnl or v1 respectively is the pendant vertex whose removal does not create a path. Finally, if Vn 's neighbor is Vj, 3 ::; j ::; n3, then either v1 or Vn1 is removable without creating a path. 0 Lemma 3 Every chordal graph G which is not a tree has at least k + 2 vertices, where k is the number of nontrivial maximal cliques of G. Proof: We proceed using induction on n = IV(G)I. Base case: n = 3 implies.G is K3 13 ot K2 U !t, so clearly the lemma holds. Assume that for every chordal graph on fewer than n vertices that is not a tree, the lemma holds. Let G be such a graph on n vertices. We must show n 2:: k + 2. Since G is chordal, we know G has a simplicial vertex, i.e. a vertex whose neighborhood is a clique. Call that vertex z. Let G' = G{z}. G' is a chordal graph on n 1 vertices Let k' be the number of maximal cliques in G'. Case i: G' is a tree. Then k' is simply the number of edges in G', which is (n 1) 1 = n2. Since G' is a tree, and G is not, we know that z is in a maximal clique of size three in G, and its two neighbors form a clique in G', thus G has the same number of maximal cliques as G'. That is, k = n 2, or n = k + 2. So certainly n > k + 2. Case ii: G' is not a tree. Then the induction hypothesis holds for G', and we known1 2:: k' + 2, which implies n > k' + 3. We know one of the following is true: k' = k or k' = k1. 9
PAGE 17
We conclude that n 2: k + 2. Thus every chordal graph which is not a tree has at least k + 2 vertices. 0 Theorem 2 Every chordal graph G on n 2: 3 vertices that is not P3 P4 or P5 is a 3competition graph. Proof: Case i: G = Pn, n 2: 6. Then G is a 3competition graph by Lemma 1. Case ii: G is a tree that is not a path. We use induction on n to" prove that G is :a 3competition graph. Our base case is n = 4, since there are no trees on 3 vertices other than P3 When n = 4, G is K1,a, which was shown to be a 3competition graph in Figure 2. Assume all trees on less than n vertices that are not paths are 3competition graphs. Let G be such a tree on n vertices. By Lemma 2, there exists a vertex :c in G such that G' = G{ :c} is not a path. G' is a 3competition graph by induction hypothesis. Let y be the one neighbor of z in G. Surely y is listed in at least 3 of the sets of a 3ECC of G' of size at most n 1. We create a 3ECC of G of size at most n by adding z to 2 of those sets containing y, and adding a final set { z, y }. Therefore G is a 3competition graph. Case iii: G is not a tree. Let C;, 1 < i < k be the k nontrivial maximal cliques of G. Consider the following sets form a 3ECC for G, and by Lemma 3, we known 2: k + 2. 10
PAGE 18
The three above convince us that every chordal graph on 3 or more vertices that is not P3 P4 or P5 is a 3competition graph. D Since interval graphs are chordal, we have the following corollary of Theorem 2. Corollary 1 Every interval graph on three or more vertices that is not P3 P4 or P5 is a 3competition graph. 2.3 p Competition Graphs of Loopless Hamiltonian and Strongly Connected Digraphs The results presented in this section are due to Langley et al. [10] and are analogous to some of the previously mentioned facts about competition graphs. We begin by characterizing some large classes of graphs which are the pcompetition graphs of loopless Hamiltonian digraphs, and we conclude with a sufficient condition for a graph to be the pcompetition graph of some strongly connected loopless digraph for p;:::: 2. Theorem 3 Let p ;:::: 2. Every cycle on n ;:::: p + 3 vertices is the pcompetition graph of a loopless Hamiltonian digraph. This result is rather easily proved by constructing the digraph for which the cycle is the pcompetition graph. The following result is not as readily proved. Theorem 4 Let p > 2. H T=(V,E) is a tree on n ;:::: 2p vertices, then Tis the pcompetition graph of a loopless Hamiltonian digraph. 11
PAGE 19
Often mathematical induction is a handy tool in proving results on trees. However in the previous theorem, as p grows, so does n 2p, giving us unmanageable base cases for induction for large p. So the proof in [10] involves several lemmas and has a constructive "flavor". H we restrict ourselves to the case when p = 2, then we arrive at the following result via some lemmas (one of which is proved by induction). Theorem 5 H G is a chordal graph on n 5 vertices, then G is the 2competition graph of a loopless Hamiltonian digraph. In attempts to prove a similar resUlt for p, we again have a problem using induction since base cases become increasingly difficult to handle asp grows. The next result is an easy corollary of the above theorem. Corollary 2 H G is an interval graph on n 5 vertices, then G is the 2competition graph of a loopless Hamiltonian digraph. We conclude this section with a sufficient condition for a graph to be the p competition graph of a strongly connected loopless digraph. Theorem 6 Let G be a graph which is the pcompetition graph of some loopless digraph, D, for p 2. Then G is the pcompetition graph of some strongly connected loopless digraph, D'. 12
PAGE 20
The proofinvolves topologically ordering the strong components of D, and then creating a digraph, D', which has fewer strongly connected components, such that G is also the pcompetition graph of D'. The curious reader is referred to [10] for detailed proofs of all results which have been presented in this section. 13
PAGE 21
3 Tolerance Competition Graphs 3.1 Preliminaries In this section, we will assign a tolerance ti from the nonnegative integers N, to each vertex Vi of a graph G = (V,E). Let : NxN + N be a symmetric function. We will deal with = min, = max, and = sum in this chapter. G is a tolerance competition graph if there is a digraph D = (V,A) and an assignment of tolerances ti to the vertices Vi such that fori# j, [w,v;] E E(G) if and only if IO(vi)nO(v;)l 2: (ti,t;) (where O(:r:) is. the outset of vertex :z:). As with competition graphs, we are interested in covering the edges of G with cliques. For this purpose, we define a toleranceedge clique cover (TECC) of G to be a collection S1,S2 ... of subsets ofV such that [vr,vs] E E(G) if and only if at least (tr, ts) of the sets si contain both Vr and Vs The size of a smallest TECC of G taken over all possible tolerance assignments is the tolerance edge clique cover number and is denoted Bq,(G). The following theorem of Brigham, McMorris, and Vitray [3) is easily understood through examination of the example which follows it. Theorem 7 Let be a symmetric function defined from N X N into N. Then G = (V,E) is a tolerance competition graph if and only if Bq,(G) < lVI. Example 3 We will show that G of Figure 5 is a tolerance competition graph 14
PAGE 22
for= (i.e G is a maxtolerance competition graph). To see this construct a digraph D = (V, A) for which G is the maxtolerance competition graph. a b G: d c Figure 5: G is a maztolerance competition graph. ta = tb = 0, tc = td = 2, te = 1 Sets of a maxtolerance ECC: Se = {a,d}, Sc = {e,d}, Sb = {d,a,c}, Sa {d,b,e,c}, sd = {b,c} It is easy to check that (:z:, y] E E(G) if and only if :z: andy occur together in at least max { tr' til} of the si. To construct digraph D (see Figure 6), we simply let Sj be the inset of vertex j in D. This is the point at which we understand the relevance of Theorem 7; we must use the same vertex set forD as we had for G, so 8.p(G) must be less than or equal to lVI. We have vertices a and b competing zero times. However, since max{t0 tb} = O, we do have edge [a, b] in G. Vertices e and c compete only for vertex a, and since max { te, tc} = 2, there is no edge between vertices e and c. Note that D is loopless and Hamiltonian in this case (a Hamiltonian cycle in D 15
PAGE 23
a b D: Figure 6: D is the digraph for which G is the maxtolerance competition graph. is abdeca). This will not always be the case, as will be discussed later. The above example shows the strength of: Theorem 7. We need not construct D every time we wish to show that a graph is a tolerance competition graph. We may instead show that I .VI. 3.2 MinTolerance Competition Graphs 3.2.1 The Basics In this section, we let t/J = min and start with an example. Example 4 We will see that G of Figure 7 is a mintolerance competition graph by constructing a minTECC of G consisting of lVI or fewer sets. We assign tolerances as follows: t1 = tb = td = 1 ta = te = tc = 2. Then the following sets form a minTECC for G: St = {/,a,e}, S2 = {d,e,c}, S3 = {b,a,c}, 84 = {b,e} 4 < 6 = lVI, so G of Figure 7 is a mintolerance competition graph. 16
PAGE 24
a b c G: f e d Figure 7: G is a mintolerance competition graph. Brigham et al. (3] have shown that several classes of graphs are mintolerance competition graphs and have provided some sufficient conditions for a graph to be a mintolerance graph Theorem 8 (3) The following graphs are mintolerance competition graphs: a. Every bipartite graph b. Kn1 ,n2 ,n,. (complete multipartite graphs) c. Every graph G with a(G) where a (G) is the size of a maximal set of independent vertices in G, Ll (G) is the maximal vertex degree in G, and 6 (G) is the minimal vertex degree in G. The authors of (3] leave us with the following open question regarding min tolerance competition graphs: "Are there any graphs which are not mintolerance competition graphs?" It is unknown at this time whether the tenvertex graph shown in Figure 8 is a mintolerance competition graph or not. No mintolerance ECC of size 10 or less has been found thus far. However, proving that none exists is a difficult problem. 17
PAGE 25
Figure 8: Is this graph a competition graph? 3.2.2 MinTolerance Competition Graphs and a Construction of Mycielski We now use a construction of Mycielsk.i [15) to generate large classes of graphs which are mintolerance competition graphs. Most of the graphs we construct do not satisfy the sufficient conditions of Theorem 12, nor are they competition graphs. Thus, we are creating large new classes of mintolerance competition graphs. Given a graph G, we construct the graph as follows. HV(G) = { Vt, v2 vm}, let {at,a2, ... ,am,bt,b2,,bm,c} with [ai,a;) E if and onlyif[vi,v;] E E(G),[ai,b;] E E E(G),[bi,c] E G)), 1 i m, and no other edges. Example 5 Shown in Figure 9 is where G = 05 the cycle on five vertices. 18
PAGE 26
Figure 9: p( 05), also as Grotzsch 's graph. Courtesy of Larsen, Propp and Ullman [11], we have the following two interesting properties of p( G) : a. w(p(G)) = w(G),where w(G) is the size of the largest clique in G. b. x(p(G)) = x(G) + 1, where x(G) is the chromatic number of G. We now show that p(G) is a mintolerance competition graph for several classes of graphs G. Theorem 9 p(.Cn) is a mintolerance competition graph. Proof: Consider p( 04): H we assign the following tolerances, and use the sets Si shown below as a min TECC we can see that p(C4 ) is a mintolerance competition graph. Tolerances: 1 = tc = f00 1 i < 4, 4 = tbn 1 < i 4. 19
PAGE 27
Figure 10: JL( C4). Sets of minTECC: Sc = { c, b2, ba, b4} Sa1 = b2, b4} Sa2 = {a2,b3,b1} Sa3 = {aa,b4,b2} = { a4, ba} Sb1 = {at, a2} = { a2, aa} sb3 = { aa, a4} sb4 = {a4,al} IV(JL(C4))1 = 2(4) + 1 = 9 =the size of the minTECC above. Now consider JL(C3): Tolerances: 1 = tc = tail 1 i 3 3 = tb;, 1 i 3 Sets of minTECC (similar to sets used for C4): Sc = {c,bt,b2,ba} Sa1 = {at,b2,ba} Sa2 = {a2,bt,ba} Sa3 = {aa,b2,bi} Sb1 = {aha2} = {a2,aa} 20
PAGE 28
Figure : 11: : p( Ca). Aga.in we have used lVI sets. Tolerances used for p( C3 ) can also be used for p( Cn), n 2: 5. 1 = tc = tan 1 i n 3 = tbn 1 i n Sets of minTECC: Sc = { c, b17 .. bn} Sa; = {ai, bi1, bi+I} (addition mod n), 1 i < n Sb; = {ai, ai+I} (addition mod n), 1 i n This is a minTECC of p(Cn) which contains 2n+ 1 = IV(p(Cn))l sets, so p(Cn) is a mintolerance competition graph V n > 3. 0 21
PAGE 29
Note that for n ;:;:: 6, condition c of Theorem 8 is not met by p.( Cn), since a(p.(Cn)) = n + for n 2: 6 and n 2:6, n+ < 2n:+n. 2n:tn for n 2: 6, but for Theorem 10 p.(Kn) is a mintolerance competition graph. Proof: p.(K2) = Cs, so p.(K2 ) is a mintolerance competition graph, since every cycle is a competition graph. p.(K3 ) = p(C3). is a mintolerance competition graph by the previous theorem. We start by considering p.(K4 ) (see Figure 12). Let tc = taj = 1, 1 < j < 4 Let tbj = 4, 1 :::; j :::; 4 Figure 12: p.(K4). Sets of a minTECC: {al!a2,a3,a4 }, {ahb2,b3,b4 }, {a2,b3,b4,b1}, { a3, b4, bt, b2}, { a4, bt, b2, b3}, { c, bt, b2, b3, b 4 }. 22
PAGE 30
A similar construction works for p.(K11), n 5: Let tc = ta; = 1, 1 j n and tb; = n, 1 :$ j :$ n Sets of a minTECC: The above minTECC consists ofn + 2 sets, and certainly with n 5 we have n + 2 < 2n + 1 = IV( G) I It is easy to check that :z: and y are adjacent in p.(Kn) if and only if at least min { tz, t11} of the sets above contain both :z: and y. 0 Again, p.(Kn) does not satisfy condition c of Theorem 8. To see this, we consider 5. a(11.(Kn)) = n (2n+l)(2(n1)) (2n+l)(n1) r2 6 Kn)+l) 2(n+l) (n+l) For n > 5 n < (2n+l)(nl) ' (n+l) Theorem 11 H B is a bipartite graph, then p.(B) is a min'tolerance competition graph. 23
PAGE 31
Proof: B be a bipartite graph with bipartition { a17 ar} and {b1 bt}. Without loss of generality assume r $ t. Now consider p.(B), which contains all vertices and edges from B, as well as "new" vertices ai, ... bi, ... and c. p.(B) has 2r + 2t + 1 vertices in all. We must find a minTECC of p.(B) of size at most 2r + 2t + 1. Let tai = ta! = 1, 1 $ i $ r, tc = r + 1, tbi = 2r + 1, 1 $ i $ t, and I tb! = 2r + 2, 1 $ i $ t. I We let N(z] be the closed neighborhood of z, and assign our sets for a minTECC as follows. Sa! = 1 $ i $ r I S2r.f1 = $ i < t} S2r+2 = $ i $ t} S2r+r+l = $ i $ t} It is easy to check that z and y are adjacent in p.(B) if and only if at least min{tz, t11} of the sets Sp above contain both z andy. The size of the minTECC is 3r + 1 < lVI (since r < t). Thus p.(B) is a mintolerance competition graph. 0 When B is bipartite, with r and t defined as in the proof, we see that a(p.(B)) = 24
PAGE 32
2t, lVI = 2r + 2t + 1, 2:: r + t, andh"(p(B)) 7' + 1. With these facts and some tedious algebra, we see that p(B) does not satisfy condition c of Theorem: 8. Now we consider p(G), where G is a connected graph. The following theorem convinces us that p( G) is rarely a competition graph itself. Theorem 12 Let G be a connected graph vertices. p(G) is a competition graph if and only if G is Kn or G has exactly one nonsimplicial vertex Za, and Za is contained in exactly two maximal cliques of G of sizes 3 or greater. Proof: ( <=) We construct p(Kn) and p(H), where H has exactly one nonsim plicial vertex Za and Za is contained in exactly two maximal cliques of H of sizes greater than or equal to 3. Next we give an ECC for each which consists of 2n + 1 or fewer cliques. Let X= { ZJ, ... Zn} be the original vertices of G, let Y = {Yb ... Yn} be their "shadows", and let z be the additional vertex which is adjacent to every vertex ofY. For p(Kn), our ECC consists of then edges incident to vertex z, and Nx(Yi) U {yi} Vi< n. So we have an ECC of p(Kn) consisting of 2n::; 2n + 1 cliques. For p(H), our ECC consists of then edges incident to vertex z, and Vi such that Zi is simplicial in H, we list {Yi} U Nx(Yi) in our ECC. For the one nonsimplicial 25
PAGE 33
vertex zll H, let cl and c2 be the 2.maximal cliques in H which contain Xa Then we complete our ECC of p.(H) with {Ya} U Nc1 (Ya) and {Ya} U Nc2 (Ya) This ECC consists of 2n + 1 = !V(p.(H))! cliques. ( =>) We must show: p.(G) is a competition graph => G is Kn or G has exactly one nonsimplicial vertex :z:11, and Z11 is contained in exactly two maximal cliques of G of size j, k 3. Suppose p.(G) is a competition graph. Then .Qe(p.(G)) < 2n + 1. Consider a minimum ECC of p.(G). The n edges incident at vertex z make up n of the cliques in such an ECC. Since Y (the set of "shadow" vertices) is an independent set, no two vertices from Y will appear together in any clique of the ECC. Since G is connected, we must have at least one clique for each Yi in order to cover edges between X andY. So we have a total of 2n required sets in our ECC thus far. H there are two nonsimplicial vertices in G, say :ell and :cb, then we need at least two cliques to cover edges between Ya and X and at least two cliques to cover edges between Yb and X. This would force the minimum ECC to be of size 2n + 2, indicating that p.( G) is not a competition graph. So there is at most one vertex Yi such that :Ci is nonsimplicial in G. Furthermore, :Ci must be in just two maximal cliques of G (otherwise the minimum ECC contains more than 2n + 1 cliques). Hone (or both) of these maximal cliques is K2 then p.(G) is not a competiton graph. We conclude that G is Kn or G has exactly one nonsimplicial vertex, :ell, 26
PAGE 34
and 2:0 is contained in exactly two maximal cliques of G of sizes greater than or equal to three. D Theorem 13 H G is a competition graph, then p(G) is a mintolerance compe tition graph; Proof: Let G be a competition graph on n vertices, at, ... an. To create p(G), we add vertices b17 bn, and c, with appropriate edges as described earlier. Since G is a competition graph, we know we can cover the edges of G with n or fewer cliques. We now specify a minTECC for p(G). Assignment of tolerances: ta; = tc = 1, 1 i < n and tb; = n + 2, 1 i n We can start our minTECC of p(G) with the same cliques used in a minimal covering of G (there will be less than or equal ton of these, since Be( G) :::; n). We will also use the set { c, b1 ... bn} (to cover all edges incident to c). The edges that remain to be covered are between V(G) and B = {b1 bn}, so let our final sets be {ai} U NB(ai), 1 i < n, where B= {bt, ... bn} Note that t&; = n + 2, so no edges will appear between any of the bi's. The maximum number of sets in this minTECC is 2n + 1 = IV(p(G))I. Thus p(G) is a mintolerance competition graph. D 27
PAGE 35
Note that .since cycles and complete graphs are competition graphs, Theorems 13 and 14 are direct corollaries of Theorem 13. 3.3 Max .. Tolerance Competition Graphs In [3), the authors briefly discuss the situation for = max. The following theorem is due to them. Theorem 14 For all n 1, K2,n "is a maxtolerance competition graph. More over, this can be demonstrated using only tolerances 0,1, and 2. The idea of the proof was demonstrated in Example 3 (the graph shown there was K2 3). The proof simply lists the tolerances we must use, and the sets of a maxTECC that will work for all K2,n It is interesting to note that unlike the case for = min, there are graphs which have been identified as not being maxtolerance competition graphs. The one given as an example in [3) is K3,a. The authors tell us that this fact "has been demonstrated in a long multicase analysis based on the maximum tolerance used". They also show us a single subcase which is rather lengthy. Reading this subcase emphasizes the difficulties that one encounters in trying to prove that a graph is not a tolerance competition graph, whatever may be. The principal difficulty is that one must consider all possible assignments of tolerances before concluding that a graph is not a tolerance competition graph. 28
PAGE 36
3.4 Competition Graphs For sumtolerance competition graphs, we define as follows: (ti, t;) = ti + t; i.e. We have an edge between two vertices vi and Vj in the graph if and only if they "compete for" at least ti + t; vertices in the digraph. Example 6 The graph of Figure 13 is a sumtolerance competition graph, as demonstrated by the list of tolerances and the sumTECC that follow. a d G: b e Figure 13: G is a sumtolerance competition graph. We assign tolerances as follows: ta = tb = tc = 1 ta = te = t1 = 0 AndthesetsofoursumTECCare{a,b,c}, {a,b}, {a,c}, {a,d}, {c,e},and {b, e }. We note that the vertices d, e, and f form a clique in G but are not listed together in any of the sets of the sumTECC. However, since they have been assigned tolerance zero, the edges between them are automatic, without being listed in 29
PAGE 37
the sumTECC. Also notice that vertices band c have been listed together once in the This is allowable since the sum of their tolerances is 2. They would have to be listed together at least twice in order to have the edge [b, c] appear in the graph. The authors of [3] bring up an interesting point which distinguishes sum:tolerance competition graphs from maxand mintolerance competition graphs. They note that there are graphs which are competition graphs if we allow noninteger tolerances which a:re not sumtolerance competition graphs using the usual definition (where all tolerartces are restricted to the nonnegative integers). The example they give is, again, Ka,3 X y z Figure 14: The complete bipartite graph, K3 3 The tolerance assignment the authors use is: Then the following sets form a sumTECC for K3 3 : S1 = {a,c,z,z}, S2 = {b,c,y,z}, Sa= {a,y}, S4 = {a,z}, Ss = {b,z}, and Ss = {b,z} 30
PAGE 38
The proof which the authors give to show that K3 3 is not a sumtolerance com petition graph if all tolerances are from the nonnegative integers is lengthy, even in its incomplete form, again emphasizing the difficulty in proving that a graph is not a tfotolerance competition graph. The authors [3] pose the following question, "Are there graphs which are not sumtolerance competition graphs if noninteger tolerances are allowed?" 3.5 Twotj>Tolerance Competition Graphs In this section we concern ourselves only with those tfotolerance competition graphs which have tolerances assigned strictly from the set {p,q}, where p and q are nonnegative integers. Such a graph is called a twotolerance competition graph First, we note that certainly a pcompetition graph is a {p, q}maxtolerance competition graph and a {p, q}mintolerance competition graph. And, likewise, a qcompetition graph is a {p, q}maxtolerance competition graph and a {p, q}mintolerance competition graph. We follow this point with an example of a graph which is not a pcompetition graph and not a qcompetition graph but which is a {p, q}tf>tolerance competi tion graph. 31
PAGE 39
Example, 7 K2,s {see Figure 15) is an example of a graph which is not a competition graph and not a 2competition graph, hut which is a {1,2}maxtolerance competition graph. We know that since Oe(K2,s) = 12 > 8 = jV(K2,s)l K2,s is not a !competition graph. We also know {from [8]) that K2 6 is not a 2competition graph. The tolerances and sets of a maxTECC given below, however, show that K2 6 is a {1,2}maxtolerance competition a b c d e f g h Figure 15: The complete bipartite graph K2 6 Tolerances: ta = tb = = t1 = 1, and t9 = th = 2 Sets of a maxTECC: S1 = {a,c,h}, S2 = {a,d,h}, S3 ={a, e,g}, S4 = {a,j,g}, Ss = {b,c,g}, Sa= {b,d,g}, S1 = {b,e,h}, and S8 = {b,j,h} It is easy to check that [z,y] E E(G) if and only if z andy are together in at least max{ tz, t11} of the sets listed above. 32
PAGE 40
The of [2) point out that when p and q are any two positive integers, the problem of determining whether or not a graph is a {p, q}tfotolerance competition graph is still rather difficult. The problem is simpler if we restrict one of the tolerances to zero. 3.5.1 {O,q}Tolerance Competition Graphs The following theorem of [2] is very helpful in categorizing {O,q}mintolerance competition graphs. Theorem 15 Graph G of order n is a {O,q}mintolerance competition graph if and only if n where M is the set of vertices of degree n1. An alternate wording would be: Graph G of order n is a {O,q}mintolerance competition graph if and only if (GM) U JIM! is a qcompetition graph, where JIM! is the graph consisting of IMI isolated vertices. Example 8 G shown in Figure 16 is a {O,q}mintolerance competition graph for 1 < q 4, since G{ m1 } U 11 is a qcompetition graph for 1 :5 q :5 4. In all cases, we assign tolerance zero to the vertex of degree n 1, m17 and assign tolerance q to all others, w, :z:, y, and z. 33
PAGE 41
ml w Zt w & G: (GM)Ult: .., :z: y z :z: y z Figure 16: The graphs G and (GM}Ul1 For q = 1, the 1ECC of ( GM)U 11 consists of the sets { :z:, y} and {y, z }. For q = 2, the sets are {:z:,y,z}, {:z:,y}, and {y,z}. For q = 3, the following four sets form a 3ECC for (GM)UJ1 : {:z:,y,z}, {:z:,y,z}, {:z:,y}, and {y,z}. And finally for q = 4, the following five sets form a 4ECC: {:z:,y,z}, {:z:,y,z}, {:z:,y,z}, {:z:,y}, and {y,z}. However, it is easy to see that G is not a {0,5}mintolerance competition graph, since the smallest possible 5ECC for P3 is of size 6, which is greater than IGI=5. H GM has no isolated vertices, then the authors of [2] simplify the previous theorem as follows. Theorem 16 Let G be a graph of order n, let M be the set of its vertices of degree n1, and suppose GM has no isolated vertices. Then G is a {O,q}mintolerance competition graph if and only if G is a qcompetition graph. The idea of the proof of necessity is to start with a qECC of GM (which by the previous theorem will be of size nor smaller), and add the vertices of M to 34
PAGE 42
every one of those sets, thus creating a qECC of G which is of size nor smaller, implying that G is a qcompetition graph The following theorem of [2] is quite useful in determining whether or not a given graph is a {0,1}maxtolerance competition graph. Theorem 17 Graph G of order n is a {0,1}ma.xtolerance competition graph if and only if e;(G) :::; n + 1 The proof for necessity{::::}) involves taking a of size at most n and turning it into a 1ECC of size at most n + 1 by simply adding a set which consists of those vertices which were originally assigned tolerance 0. The idea of the proof for sufficiency ( {:::) is to take a 1ECC of G of size at most n + 1 and drop one of the sets arbitrarily. To all vertices in that set, assign tolerance 0, and assign 1 to all others. This idea is used in the example that follows. Example 9 For G of Figure 17, it is clear that 8! = 7 = n + 1. a b c G: d e f Figure 17: G is a maztolerance competition graph. 35
PAGE 43
The seven.sets required in a 1ECC of G are: {a,b}, {b,c}, {c,j}, {f,e}, {e,d}, {d,a}, and {b,e}. H we drop one set arbitrarily, say {b, e}, and assign tolerance 0 to vertices band e and 1 to all others, then it is easy to see that (:c, y] EE( G) if and only if :c and yare in at least sets of the new maxTECC. 3.5.2 !Competition Graphs Which Are Not 2Competition Graphs In considering the question, "Are there any graP:hs which are {0,1}mintolerance competition graphs which are not {0,1}sumtolerance competition graphs?" [2], we have come across some interesting problems. One is, Which !competition graphs are not 2competition graphs? This is because every !competition graph is a {0,1}mintolerance competition graph and every 2competition graph is automatically a {0,1}sumcompetition graph (we would put tolerance 1 on ev ery vertex). So, if we find graphs which are !competition graphs but not 2competition graphs, we might find a {0,1 }mintolerance competition graph which is not a {0,1}sumtolerance competition graph. We have identified only a few graphs which are !competition graphs but not 2competition graphs. One of them is 04 the cycle on 4 vertices (proven in [8]), and the others are closely related to the graph G of Figure 18. Unfortunately, all of them are also {0,1} sumtolerance competition graphs, so we have not yet answered the question originally posed. 36
PAGE 44
a b G: d c Figure 18: G is not a 1competition graph and not a 2competition graph. G of Figure 18 is not a !competition graph, since li!(G) = 6 > 5 :._ IV(G)I. However, it can easily be made into a !competition graph, as we will soon see. The most important thing to note about G at this point concerns the size of a smallest 2ECC of G. Theorem 18 For G of Figure 18, e;(G) = 7. Proof: We know that a 2ECC of just the 4cycle a, b, c, e requires 5 sets (from [8]). We can cover G with 7 sets, so 5 :s; e;(G) :s; 7. There is only one way to cover the 4cycle a, b, c, e with 5 sets. It is: {a, b, c, e} {a, b} { b, c} { c, e} { e, a} It is easy to see that we cannot cover edges [a, d] and [d, c] by only adding vertices to these existing 5 sets. Thus 6 :s; G) < 7. To see that e;(G) # 6, we must consider several cases. Case i: We cover the 4cycle a, b, c, e with 5 sets. Let those 5 sets be the same as before: S1 = {a,b,c,e}, S2 = {a,b}, Sa= {b,c}, S4 = {c,e}, Ss = {e,a} We know we will have to add a sixth set, by previous arguement. In order to have 37
PAGE 45
this sixth be of use, it must list [a, d] or [d, c]. It cannot list both of the edges [a, d] and [d, c], since this would create the unwanted edge [a, c]. So, without loss of generality let S6 = {a, d}. Now, given these six sets, we must list [a, d] again, and [d, c] twice, without creating any unwanted edges. It is quite easy to see with our limited choices that this is not possible. So, the conclusion for case i is: when we cover the 4cycle a, b, c, e with 5 sets, it is impossible to cover G with 6 Case ii: We cover the 4..:cyde a, b, c, e with 6 sets (which do not include the 5 sets from case i). There is only one way (up to equivalence) to cover a 4cycle with six sets (which do not include the sets from case i). Thus without loss of generality, let our six sets b.e S1 = {a,b,c}, S2 = {a,b,e}, Sa= {a,e}, S4 = {b,c}, S5 = {e,c}, and Sa = {e, c}. Again, we are quite limited when we try to cover edges [a, dJ and [d, c]. After careful analysis, we realize that it is impossible to do without creating a seventh set. WecancoverGwith. thefollowingsevensets: S 1 = {a,b,c,d,e}, S 2 = {a,b}, Sa= {b,.c}, S4 = {c,e}, Ss = {e,a}, Sa= {a,d}, and S1 = {d,c}. ThusiJ!(G) = 7. 0 So we have seen that G = K2,a is Ii.ot a !competition graph, since IJ!(G) = 6 and it is not a 2competition graph, since B!(G) = 7. However, we are interested in 38
PAGE 46
graphs which are !competition graphs but not 2competition graphs. The work just shown will be very helpful in showing that the following graphs do meet that description. Figure 19: Graphs which are 1competition graphs and not 2competition graphs. For each of the six graphs G of Figure 19, o;(G) = 6 and o;(G) 7. Thus each of those graphs is a !competition graph but not a 2competition graph. Note that a seventh graph (a disconnected one) could be added to Figure 19; we simply leave the bottom vertex isolated and keep the other six edges. We can generalize the above method quite nicely to a result which is great in theory, but rather difficult to implement. 3.5.3 Creating 1competition graphs which are not 2competition graphs. Let us begin by considering the graphs previously discussed. All six had K2 3 as a generated subgraph. In each of the six cases, we started with K2 3 and added one vertex, being careful to add edges from which would keep of our new graph equal to 6. But since each of the six graphs has K2 3 as a generated subgraph and o;(K2 3 ) > 7, we know that o; for each of the six new graphs is 39
PAGE 47
also than or equal to 7, which is one more than the number of vertices. It is easy to see, then, that the following method will always result in a graph which is a !competition graph but not a 2competition graph. Start with a graph G on n vertices with 9!(G) = n + 1 and e;(G) n + 2. Add a vertex z which is adjacent to all vertices of G (or just some of the cliques of G), creating the new graph, G'. Then B!(G') is still n+ 1, so G' is a !competition graph. However, G' still has G as a generated subgraph, so e;(G') n + 2, and G' is not a 2competition graph. We can, in fact, generalize this notion further by starting with G on n vertices with B!(G) = n + k and e;(G) n + k + 1, k > 1. Then we can add k vertices to G, one at a time, making each vertex adjacent to all of those in the graph preceding it. The new graph G' will have B!(G') = n + k, but since G is a generated subgraph of G', e;(G') n + k + 1. Thus G' will be a !competition graph but not a 2competition graph. As mentioned previously, the method discussed here is a nice theoretical tool; however, from a practical standpoint it is quite difficult to use. The problem comes in the first stepfinding G such that B!(G) = n+ k and e;(G) n+ k+ 1, k > 1. The difficulty in finding such a G was illustrated by the graph K2 3 where n = 5 and k = 1. For larger nand k, the proof for e;(G) > n + k + 1 becomes 40
PAGE 48
quite unwieldy. 3.5.4 More on !competition graphs which are not 2competition graphs. In conclusion, we present some ideas which are useful in narrowing the search for more !competition graphs which are not 2competition graphs. First, note that any such graph will not be chordal or unicyclic (except 04). This is because chordal graphs and unicyclic graphs are graphs (see (9]). The following lemma, a proof of which is given in (6), allows us to narrow the search even further. Lemma 4 Every connected trianglefree graph G with n = IV( G)! or fewer edges is either a tree or a tree with an additional edge. We use this lemma to prove the following result. Theorem 19 H G is a connected trianglefree graph with nor fewer edges, then G is a 2competition graph or G is 04 Proof: Let G be of order n with nor fewer edges and assume G is not 04 By the lemma, G is a tree, or G is a tree with one extra edge. H G is a. tree, then G is chordal and is therefore a 2competition graph. H G is a. tree with one extra. edge, then G is unicyclic, and is therefore a 2competition graph. 0 41
PAGE 49
The for more !competition graphs which are not 2competition graphs has been reduced (in the connected case) to nonchordal, nonunicyclic !competition graphs with at least one triangle. The six graphs presented earlier do meet this description, but the search for more continues. 42
PAGE 50
4 Conclusion There are many directions in which the topics discussed here can be taken for future research. We by listing some of those possibilities. Open Problem 1: Which graphs are pcompetition or competition graphs of symmetric digraphs (with or without loops)? [See [14] for an analogous result for interval competition graphs.] Open Problem 2: Can .we finda family of gr,aphs g such that the following statement is true? H IV(G)I = n, then G is a 2competition graph of a digraph that has no loops if and only if G fl g and o;( G) < n. Some graphs which are known to be in this set g are K2, K 2 U Kh P3 K3 (all courtesy of [9]) and the graph shown in Figure 20. What other graphs belong in I2J Figure 20: A graph which is a !competition graph of an arbitrary digraph with loops, but not of a digraph without loops. Open Problem 3: How might we minimize or maximize the number of arcs in D without changing G, where G is the pcompetition graph or the competition graph of D? [See [7] for a related result for competition graphs.] 43
PAGE 51
Open Problem 4: What if we expand on some of the ideas briefly mentioned at the end of Chapter 1 and consider such graphs as pniche graphs, niche graphs, pcompetitioncommon enemy graphs, and competition common enemy graphs? Can we find any results analogous to those that are known for niche graphs and competitioncommon enemy graphs [see [18) and (4)]? Open Problem 5: Which acyclic digraphs have pcompetition graphs which are interval graphs? [See (13) for results on competiton graphs.) Open Problem 6: What if we make analogous definitions using clique covers of vertices rather than edges? What can be determined in such cases? One might wonder whether Joel Cohen ever would have imagined in 1968 the possibilities hidden in his food web model. The open problems listed above certainly barely scratch the surface in terms of where research in this area could possibly go. 44
PAGE 52
References (1] R. C. Brigham and R. D. Dutton. A characterization of competition graphs. Discrete Applied Mathematics, 6:315317, 1983. (2] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Two
PAGE 53
[9] S. R Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. pcompetition graphs. To appear in Linear Algebra and Its Applications, 1994. [10] L. Langley, J. R. Lundgren, P. A. McKenna, S. K. Merz, and C. W. Ras mussen. Some characterizations of pcompetition graphs of strongly con nected and Hamiltonian digraphs. manuscript, 1994. [11] M. Larsen, J. Propp, and D. Ullman. The fractional chromatic number of Mycielski's graphs. to appear in of Graph Theory, 1994. [12] J. R. Lundgren. Food webs, competition graphs, en emy graphs, and niche graphs. In F.S. Roberts, editor, Applications of Com binatorics and Graph Theory to the Biological and Social Sciences. Springer Verlag, 1989. In IMH Volumes in Mathematics and Its Applications, vol. 17. [13] J. R. Lundgren a.nd J. S. Maybee. Food webs with interval competition graphs. In Graphs and Applications: Proceedings of the First Colorado Sym posium on Graph Theory. Wiley, New York, 1984. [14) J.R. Lundgren, J.S. Maybee, and C.W. Rasmussen. Interval competition graphs of symmetric digraphs. Discrete Mathematics, 119:113122, 1993. [15] J. Mycielski. Sur le coloriage des graphes. Colloquium Mathematicum, 3:161162, 1955. 46
PAGE 54
[16] F. S Roberts. Discrete Mathematical Models1 with Applications to Social1 Biological1 and Environmental Problems. Prentice Hall, Englewood Cliffs, New Jersey, 1976. [17] F. S. Roberts and J. E. Steif. A characterization of competition graphs of arbitrary digraphs. Discrete Applied Mathematics, 6:323326, 1983. [18] D. D. Scott. The competitioncommon enemy graph of a digraph. Discrete Applied Mathematics, 17:269280, 1987. 47
PAGE 55
In summary, a subgraph of interval graph G induced on vertices a b, c, d, e, and f is a 4fan about nonsimplicial edge [a, b] hinged at a if {a, b, c} is a maximal clique of G, [e, c], [e, a], [f, d], [f, a] E E(G), possibly [b, f] E E(G), and no other edges are present. The figure below shows two such 4fans. e a f e a f To construct our collection S of sets, we use the chart that follows. For every nonsimplicial edge of G, we determine its type, and add set(s) to the collection S. For example, if [a, b] is a Type 2 nonsimplicial edge, we add two sets to S, as described in the chart. Note that we also add sets based on maximal cliques of size at least 4 in G which contain only simplicial edges (see section 6 of chart). 48
PAGE 56
Sets of S Type of Nonsimplicial Edge Set Definition Set Type (1) [a, b] contained only in s. N[[a, b]] (1) cliques of size at least 4 (2) [a,b] contained only s., N([a, bJ) (2a) in cliques of size 3, and there are no induced 4fans about [a, b) s., {a, b} (2b) (3) [a, b] contained only in s., = N([a, bJ) (3a) cliques of size 3, and there is at least one 4fan about [a, b] s., = {a,b} (3b) {a, c, d}, one such (3c) set for each 4fan about [a, b] hinged at a s.J = {b,p, q}, one such set (3d) for each 4fan about [a, b] hinged at b (4) [a, b) is contained in s., the union of all (4a) both cliques of size at least cliques of size at least 4 4 and of size 3, and there containing [a, b] are no 4fans about [a, b] (induced or otherwise) s., = N(la, bJ) {4b) (5) [a, b] is contained in Se, = the union of all (5a) both cliques of size at least cliques of size at least 4 4 and of size 3, and there containing [a b] is at least one 4fan about [a, b] (perhaps not induced) s = N([a, b]) {5b) {a,c,d}U{all cliques (5c) of size .at least 4 containing [a, bl}{b},one such set for each 4fan about (a, b] hinged at a Se; {b,p, q}U{all cliques (5d) of size at least 4 containing (a, b]}{a},one such set for each 4fan about [a, b] hinged at b s. = Cm, where Cm is a (6) cliqueof size at least 4 with no nonsimplicial edges 49
PAGE 57
Theorem 13 If G is a chordal graph, then S forms a (2)neighborhood cover of G. Proof: This follows from the fact that S is an extension of the family 'T of Section 3.2, which was proved to form a (2)neighborhood cover of G. It is easy to see from the definitions given in the chart that those sets in S which are not in 'T do form cliques in N2 (G). Corollary 3 LetS'= {SeE SISe is maximal}, and suppose G is chordal. Then S' is a {2)neighborhood cover of G. 4.3 Main Result In this section, we prove five lemmas, each relating to a different type of non simplicial edge of interval graph G, and a sixth lemma which relates to those maximal cliques of size at least 4 in G which have no nonsimplicial edges. The lemmas convince us that each set of S' defined in Section 4.2 corresponds to a maximal clique of N2 (G). We then use the lemmas to show that the family S' forms a (2)neighborhood cover of G which consists of maximal cliques of N2(G). We conclude with a necessary and sufficient condition for an interval graph G to have an interval (2)neighborhood graph. 50
PAGE 58
In each of the following lemmas, we will assume the following facts, unless stated otherwise: The graph G is an interval graph. We let the (distinct) consec utively ranked maximal cliques of G be C1 ... Cr, and edge [a, b] is contained in precisely Ci, ... Ci+kt Notice that the closed neighborhood of edge [a, b], N[[a, b]] = Lemma 7 If edge [a, b] is a Type 1 nonsimplicial edge of G, then the set Be in S' associated with it is a maximal clique in N2(G). Proof: Suppose Be E S' and Be is associated with nonsimplicial Type 1 edge [a, b]. To show that Be is a maximal clique in N2 (G), assume there are two paths of length 2 from vertex x to every vertex in Be; we will show x E Be. Assume not. If X Be, then X N[[a, b]] = Suppose without loss of generality that X E Cm implies m < i. Consider clique ci+k1, the last clique in the consecutive ranking to contain both a and b. Clique Ci+k1 contains a vertex d such that Ci+kt is the first clique in the ranking in which d appears. We know d exists by the maximality of the cliques in the ranking. Case 1: Vertex xis adjacent to neither a nor b. Since there are two paths of length 2 from x to d, there exist two vertices f and gin V(G) such that [f, d], [!, x], [g, d], and [g, x] E E(G). Note that f # a, b and g # a, b. Then, by the consecutive ranking, f and g appear together in cliques ci1, ... 'ci+k1, and possibly more. 51
PAGE 59
Hence (!, g] E E(G), and in fact (!, g] is a nonsimplicial edge of G Edge (!, g] is not a Type 1 nonsimplicial edge, since N[(f, g]] properly contains N[[a, b]] (we see this from the consecutive ranking of the maximal cliques of G), so [f, g] is Type 4 or Type 5. In either case, the only cliques of size at least 4 containing (!, g] are precisely Ci, ... Ci+kt (by maximality of Be inS'). Thus {x, j g} is a maximal clique Cp of G, and p < i. Vertex x is not adjacent to any vertex in other than f and g. This is because if it were adjacent to some vertex v E v =/:. j, g, then { v, j, g, x} would be a clique of G of size ;:::: 4 containing f and g but not in {Ci, ... Ci+kI} Every clique in { Ci, ... Ci+kr} contains a, b, j, and g. Since k ;:::: 2, there exist vertices p and q in such that p and q are each adjacent to all of X q a, b, j, and g but [p, q] E(G). Thus in G we have g b Recall that there are two paths of length 2 from x to every vertex in N[[a, b]]. This includes f and g; thus there exist J', g' E V(G) such that [x, !'], [!',f), [x, g'], and [g', g] E E(G). Note that [!', g], [g', f], [x, q] E(G), since the addition of any of these edges creates a clique of size at least 4 containing x, j, and g. This also convinces us 52
PAGE 60
that f' =/; g'. Then the subgraph of G induced on vertices x, j, g, f', g', and q convinces us that G is not an interval graph, a contradiction. f' g' g q Case 2: Vertex x is adjacent to one of a and b. Without loss of generality, suppose [x, a] E E(G). Then there exists g E V(G) such that [x, g], [g, d] E E(G). Recall that Ci+kl is the first clique in the ranking in which d appears. Then g and a appear together in at least Ci_1 ... Ci+k1 Hence [g, a] is a nonsimplicial edge, either of Type 4 or 5 (not Type 1, because N[[a, b]] is properly contained in N[[a,g]]). Thus {a,g,x} is a maximal clique of G. There are two paths of length 2 from x to every vertex in N[[a, b]], including a and g, thus there exist vertices r,s E V(G) such that [x,r],[r,a],[x,s], and [s,g] E E(G). Note that r =/; s, since this would create clique {a, g, x, r = s}, contradicting the maximality of clique {a,g,x}. For the same reason, [a,s],[r,g] (/. E(G). This leads to the following subgraph in G: We conclude that G is not an interval graph, a contradiction. 53
PAGE 61
d a s X r The two cases convince us that x E N[[a, b]] = Se, and hence Se is a maximal clique of N2 (G). Lemma 8 If edge [a, b] is a Type 2 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2 (G). Proof: Suppose Se E S' and Se is associated with nonsimplicial Type 2 edge [a, b]. To show that Se is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex in Se; we will show x E Se Assume not. Case 1: The set Se is a Type (2a) set. Then x (j. Se = N([a, b]). Subcase a: Assume x E N[[a, b]]. Recall that x (j. N([a, b]); thus without loss of generality, assume x = a. Certainly there is one path of length 2 (through b) from x = a to each vertex in N((a, b]). Suppose vertex c belongs to Ci and no later cliques in the ranking, and let vertex d belong to Ci+k1 and no prior cliques in the ranking. Note, then, that Ci = {a,b,c}, and Ci+k1 = {a,b,d}. Since no two vertices in N([a, b]) are adjacent, there exists u E V(G) such that 54
PAGE 62
u E Cm implies m < i and [x, u], [u, c] E E(G), and there exists v E V(G) such b d that v E Ci implies j > i + k1 and [x, v], [v, c] E E(G). U x=a v Vertices v, u (j_ N([a, b]), so [v, b], [u, b] (j_ E(G). Also, by the consecutive ranking of the maximal cliques of G and the fact that JCqJ = 3 if a, b E Cq, we know [v, c], [u, d], [u, v] (j_ E(G). So we have the following induced subgraph in G: b d ill u x =a v This is an induced 4fan about [a, b], a contradiction. Subcase b: x (j_ N[[a, b]J. Let vertex d be in Ci + k1 and no prior cliques in the ranking. Since there are two paths of length 2 from x to d, d and x have two common neighbors. Any neighbor of d can be adjacent to at most one of a and b (otherwise a and b are contained in a clique of size greater than 3), so at least one of these two common neighbors is neither a nor b; let v be such a common neighbor. Since [d, v] E E(G) and [x, v] E E(G), we have v in each maximal clique Cib ... Ci+kl and perhaps more. But this contradicts the fact that JCiJ = 3, i j i + k1, when we consider maximality of the cliques in the ranking. Hence x E N([a, b]) =Be or x E N[[a, b]J. 55
PAGE 63
We conclude that if Se is a Type (2a) set, then x E Se. Case 2: The set Se is a Type (2b) set. Then x Se = {a, b}. Subcase a: x E N[[a, b]J. Since there are two paths of length 2 from x to a, there exists y E V(G) such that [x, y], [y, a] E E(G), [y, b] E(G). There are also two paths of length 2 from x to b, so there exists z E V (G) such that [x, z], z, b] E E(G), [z, a] E(G). Then we have the subgraph shown below, and G is not an interval graph, a contradiction. y a z b d Subcase b: x ft N[[a, b]]. Without loss of generality, suppose x E Cm implies m < i. Vertex x is adjacent to at most one common neighbor of a and b, c, where c E Ci. Suppose without loss of generality [x, b] E(G). Then, since there are two paths of length 2 from x to a, there exists y E V (G) such that [x, y], [y, a] E E(G). Also, because [a, b] is nonsimplicial, there exists d =f. c E N[[a, b]], dE Ci+kl, and [c, d) E(G). We must add a chord to 4cycle xyac. Chord [a, x], with or without chord 56
PAGE 64
[y, c) creates a 4fan about nonsimplicial edge [a, c), causing {a, b, x} to be a set in S', contradicting the maximality of the set {a, b} = Be in S'. Thus chord [y, c] E E(G), and chord [a, x] rf_ E(G). Thus far, we know of one path oflength 2 from x to b, the path through c, and since [y, b] rf_ E(G), we know there exists z E V(G) such that [x, z], [z, b] E E(G). By reasoning similar to above, we have chord [c, z] for 4cycle xcbz, since [b, x] creates a 4fan about nonsimplicial edge [b,c], putting {x,a,b} inS'. Then the subgraph induced on vertices a,b,c,d,y, and z indicates that G is not an interval graph, a contradiction. y a z b d If x is not adjacent to any common neighbors of a and b, then a has a neighbor y such that [y, b] rf_ E(G) and [x, y], [y, a] E E(G), and b has a neighbor z such that [z, a] rf_ E(G) and [x, z], [z, b] E E(G). Then G has a chordless 4cycle of size 4 or greater (either yabz or yabzx), a contradiction. We conclude that x E Be = {a, b}, and hence Be is a maXimal clique in N2 (G) 57
PAGE 65
Lemma 9 If edge [a, b] is a Type 3 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2 (G). Proof: Suppose Be E S' and Be is associated with nonsimplicial Type 3 edge [a, b]. To show that Be is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to each vertex in Be; we will show x E Be. Assume not. Case 1: The set Be is a Type (3a) set. Then x = N([a, b]). Without loss of a d ffi generality, assume there is a 4fan about edge [a, b] hinged at b. f b g Subcase a: x E N[[a, b]]. Suppose x = b. Then there are two paths of length 2 from x = b to c and two paths of length 2 from x = b to d (via a and f and via a and g, respectively). If c and d are the only neighbors of [a, b], then { c, d, b} is a Type (3d) set, contradicting the maximality of Be = N([a, b]) = { c, d} E S'. Thus a and b have another common neighbor h. Since [h, g] would create the chordless 4cycle hgda and [h, f] would create the chordless 4cycle hfca, we know [h, g], [h, f] E(G). Thus there exists y E V(G) such that [b, y], [y, h] E E(G). Edge [a, y] E(G), since if it were, we would have {a, b, h, y} contained in some clique of G, contradicting the fact that [a, b] is a Type 3 nonsimplicial edge. Then we have NC7 as an 58
PAGE 66
induced subgraph of G (on vertices a,c, d, h, j, g, and y), contradicting the fact that G is an interval graph. g d a h y Now suppose x =a. Since there are two paths of length 2 from x to d and two paths of length 2 from x to c, we know there exists y E V (G) such that [c, y], [y, a] E E(G). The addition of edge [b, y] forces [a, b] into a clique of size greater than 3, so [b, y] fj. E(G). Then we have the following subgraph induced on vertices a, b, c, d, j, andy, convincing us that G is not interval. y x=a f b d Subcase b: x fj. N[[a, b]]. Suppose without loss of that x E Cm implies m < i. Let {a, b, c} = Ci, and {a, b, d} = Ci+l Since there are two paths of length 2 from x to d, d and x have two common neighbors, one of which, call it y, is neither a nor b. Thus [x, y], [y, d] E E(G). By the consecutive ranking of the cliques of G, y =c. However, this contradicts the fact that [a, b] is contained only in cliques of size 3, as {a, b, c, d} becomes a clique of G. 59
PAGE 67
We conclude from Case 1 that Be is not a Type (3a) set. Case 2: The set Be is a Type (3b) set. Since the reasoning used in Case 2 of the proof of Lemma 2 did not rely upon the fact that there were no 4fans about [a, b], we may use the same arguments here. We conclude that Be cannot possibly be a Type (3b) set. Case 3: The set Be is a Type (3c) set. Suppose Be corresponds to the 4fan about b d [a, b] hinged at a shown below. Then x {a, c, d}. ffi f a 9 Subcase a: x E N[[a, b]]. Then [x, c], [x, d] E(G). Thus there exists y E V(G) such that y N[[a, b]], [x, y], [y, a] E E(G), and thus [y, b] E(G). Then we have NC7 as an induced subgraph of G (on vertices b, c, d, x, j, g, and y), contradicting the fact that G is an interval graph. Subcase b: x N[[a, b]]. Suppose that x E Cm implies m < i, and let Cp be the last clique in the ranking in which vertex x appears. Suppose also that cj = {a, b, c} and ck = {a, b, d}' with j < k. Since X and d have two common neighbors, those neighbors both appear in cliques CP, ... Ck, and perhaps others. 60
PAGE 68
This includes Cj, so those two common neighbors must be a and b, contradicting x tj_ N[[a, b]]. We conclude that Be is not a Type (3c) set. Case 4: The set Be is a Type (3d) set. Precisely those arguments used in Case 3 of this proof (with a's and b's interchanged) convince us that Be is not a Type (3d) set. The four cases presented convince us that x E Be, and therefore Be is a maximal clique in N2 (G). Lemma 10 If edge [a, b] is a Type 4 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2(G). Proof: Suppose Be E S' and Be is associated with nonsimplicial Type 4 edge [a, b]. To show that Be is a maximal clique in N2(G), assume there are two paths of length 2 from x to every vertex in Se; we will show x E Se. Assume not. Case 1: The set Be is a Type (4a) set. Then xis not in Be, the union of all cliques of size at least 4 containing [a, b]. Subcase a: x E N[[a, b]]. Note x =/= a, b, since a, b E Be. Then {x, a, b} is a maximal clique of G, and hence x has no neighbors in N([a, b]). We see that there are two paths of length 2 from x to every vertex in Be {a, b} (one path through 61
PAGE 69
a and one path through b). Thus x must have two paths of length 2 to each of a and b. We have one path of length 2 from vertex x to b through vertex a and we need another. Hence there exists v r N[[a, b]] such that [x, v], [v, b] E E(G), and a we have a 4fan about [a, b] hinged at b, a contradiction. q b v Subcase b: x r N[[a, b]]. Without loss of generality assume x E Cm implies m < i Let Cq be the first clique in Ci, ... Ci+k1 of size ;::: 4. Suppose {a, b, j, g} s; Cq. We show q = i. If q =/= i, then Ci is a clique of size 3, let ci = {a, b, h}. Since X rt N[[ a, b]] and there are two paths of length 2 from X to g' there exists v E V(G) such that [x,v],[v,g] E E(G). By the consecutive ranking of the cliques of G, we have v = h. But then {a, b, h, g} is contained in a maximal clique of G, contradicting the maximality of {a, b, h} as a clique, so q = i. This same argument convinces us that the cliques of size at least 4 containing [a, b] occur consecutively and at the beginning of the list Ci,.:., Ci+k1 Suppose the number of maximal cliques of size at least 4 containing both a and b is n. Then they are Ci, ... Ci+n1 Also, suppose the number of maximal cliques of size = 3 containing both a and b is t. Those cliques are Ci+n, ... Ci+n+t1 = Ci+k1 Since [a, b] is a Type 4 nonsimplicial edge, we haven, t =/= 0. 62
PAGE 70
If n 2, then the arguments used for a Type (1) set (see proof of Lemma 1) convince us that G is not interval, a contradiction. We conclude that Se is not a Type ( 4a) set. We must consider the instance where n = 1. Suppose {a, b, g, h} Ci, and cliques Ci+ll ... Ci+k1 are of size 3. Note that n = 1 implies Se = Ci. Since x (j. N[[a, b]], without loss of generality suppose [x, b] (j. E(G). If x is adjacent to 3 or more members of Ci { b}, then we contradict the maximality of Ci = Se as a set in S', as { x} U Ci is contained in some set of S' associated with a different nonsimplicial edge of G. If x is adjacent to exactly two members p and q of Ci{b}, then there exist p' and q' E V(G) such that [x,p'], [p',p], [x, q'], [q', q] E E(G). Note that [p', q], [q', p] (j. E( G), since this would create a set in S' associated with nonsimplicial edge [p, q] that contains both x and Ci, a contradiction. This also explains why p' =/= q'. Then the subgraph induced on x,p, q,p', q', and b, shown here contradicts the fact that G is an interval graph. Suppose xis adjacent to exactly one member of Ci. If xis adjacent to a, we know of one path of length 2 from x to b (through a), and we know there exists b' E V(G) such that [x, b'], [b', b] E E(G). Since [x, b] (j. E(G), we know [b', a] E E( G), otherwise we have a chordless 4cycle xabb'. Because 63
PAGE 71
f' g' g q the maximal clique containing {a, b', x} occurs before Ci in the consecutive ranking of G's maximal cliques, we know {a, b, b'} Ci, but this contradicts the fact that X is adjacent to only one member of ci (recall [x, b'] E E{G)). We conclude that [x,a] fj_ E(G). It remains to consider the case that x's one neighbor in Ci, g, is neither a nor b. Note that a and b have no common neighbors that are neighbors of x other than g, by consecutive ranking and the fact that Ci is the first clique in the ranking to contain both a and b. Then there exists b' E V (G) such that [x,b'],[b',b] E E{G). We know [b',g] E E{G), otherwise we have chordless 4cycle xb'bg. Also, there exists a' E V(G) such th.at [x, a'], [a', a] E E{G), and we know [a', g] E E(G), otherwise we have chordless 4cycle xa'ag. From the above, we know [a', b], [b', a] fj_ E(G). Let Ci+1 = {a, b, c}. Then the graph induced on vertices a', a, c, b, b', and g indicates that G is not an interval graph, a contradiction. 64
PAGE 72
a' a b' b c If x is adjacent to no members of Ci, then there exist a', b' E V(G) such that [x, a'], [a', a], [x, b'], [b', b] E E(G). Notice that a and b have no common neighbor that is adjacent to x, since ci is the first clique in the ranking to contain both a and b. Hence [a'b], [b', a] '. E(G). When we consider the graph induced on vertices x, a', a, b, and b', we see that we have chordless 4cycle a'abb' if [a', b'] E E(G) and chordless 5cycle xa'abb' otherwise. Both possibilities contradict the fact that G is an interval graph. Subcases a and b convince us that x E Se or Se is not a Type ( 4a) set. Case 2: The set Se is a Type (4b) set. Then x '. Se = N([a, b]). Subcase a: x E N[[a, b)]. Without loss of generality suppose x =a. It is clear that there are at least two paths of length 2 from x = a to any vertex in a clique of size at least 4 containing a and b. Let { d, a, b} be a maximal clique of G. There is a path of length 2 from x to d through b, but there has to be another such path. Hence there exists v E V(G) such that [x, v], [v, d] E E(G) This 65
PAGE 73
creates a 4fan about edge [a, b), a contradiction. We conclude that x tJ. N[[a, b]] or x E Be= N([a, b]). Subcase b: x tJ. N[[a, b]]. Again, suppose x E Cm implies m < i. Suppose [a, b] is contained in exactly n maximal cliques of size at least 4. By the same argument as in Case 1, Subcase b of this proof, we know these n maximal cliques occur consecutively and at the beginning of the list Ci, ... Ci+kl Thus Ci+n is the first maximal clique in the ranking that contains both a and b and is of size 3. Let Ci+n = {a, b, c}. Since x and c have two common neighbors, and since Ci+n is the first clique in the ranking in which c appears (by maximality of cliques in the ranking), those two common neighbors must be in Ci+n' and therefore must be a and b. This contradicts the fact that x tJ. Be= N([a, b]). We conclude from the two subcases that x E Be or Be is not a Type ( 4b) set. Cases 1 and 2 convince us that x E Be, and thus Be is a maximal clique in Lemma 11 If edge [a, b] is a Type 5 nonsimplicial edge of G, then the sets inS' associated with it are maximal cliques in N2 (G). Proof: Suppose Be E S' and Be is associated with nonsimplicial Type 5 edge [a, b]. To show that Be is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex in Be; we will show x E Be. Assume not. 66
PAGE 74
Case 1: The set Se is a Type (5a) set. Then Se is the union of all cliques of size at least 4 containing edge [a, b], and x Se. Subcase a: x E N[[a, b]]. Then {a, b, x} is a maximal clique of G, and x has no neighbors in N([a, b]). We can easily identify two paths of length 2 from x to every vertex in Se {a, b}, one through a and one through b. We consider the fact that there are two paths of length 2 from x to b. We find one such path through a, and conclude that there exists v E V(G) such that [x, v], [v, b] E E(G). Similarly, there are two paths of length 2 from x to a, and since {v, a] fi E(G), there exists y E V(G) such that [x, y], [y, a] E E(G), and [y, b] fi E(G). Let q be some neighbor of [a, b] other than x. Then [q, x] fi E(G), and the subgraph of G induced on vertices a, b, x, y, v, and q indicates that G is not an interval graph, a contradiction. y X q b v Subcase b: x fi N[[a, b]J. Again suppose x E Cm implies m < i. As in Lemma 4, Case 1, Subcase b and Lemma 4, Case 2, Subcase b, the cliques of size at least 67
PAGE 75
4 containing [a, b] occur consecutively and at the top of the list Ci, ... Ci+kI Again, if [a, b] is contained in at least two cliques of size at least 4, then the argument in the proof of Lemma 1 convinces us that G is not interval. It remains to consider the case that [a, b] is contained in exactly one maximal clique of size at least 4 in G. Then Se = Ci 2 {a, b, p, q}. The same argument as was used in the proof for set Type (4a) (Lemma 4, Case 1, Subcase b, n = 1) is appropriate here, and convinces us that G is not interval. The subcases convince us that Se is not a Type (5a) set. Case 2: The set Se is a Type (5b) set. Then x rf Se = N([a, b]). Subcase a: x E N[[a, b]], without loss of generality x = a. We claim [a, b] is in at most two maximal cliques of size 3. Suppose not. Suppose Cu ={a, b, c}, Cv = {a, b, d}, and Cw = {a, b, f} are maximal cliques of G. Notice that i u, v, w i + k1. Suppose without loss of generality that i u < v < w i + k 1. Since there are two paths of length 2 from x = a to c, there exists y E V(G) such that y rf N[[a, b]] and [a, y], [y, c] E E(G). As a result we see that [y, b] rf E(G). By maximality of cliques in the ranking, and because y rf N[[a, b]], one of the following must be true: cEq or c E Ci+k1 (1). Note that [y, d] and [y, f] are not edges of G, since these two edges create 68
PAGE 76
chordless 4cycles ycbd and ycbf respectively. Thus we can use precisely the same argument as above to conclude that one of the following must be true: dE Ci or dE Ci+k1 (2) and one of the following must be true: f E Ci or f E Ci+k1 (3). Clearly it is not possible for (1), (2), and (3) to all hold, so [a, b] is in at most two maximal cliques of size 3 in G. Suppose [a, b] is in exactly one maximal clique of size 3 in G, say {a, b, c}. Again, vertex y exists such that [y, b] fj_ E (G), and [y, a], [y, c] E E (G). Then we have a 4fan about [a, b] hinged at a, and N([a, b]) is properly contained in a set Sq E S', where Sq is a Type (5c) set associated with edge [a, b], contradicting the maximality of Be inS'. Suppose [a, b] is in exactly two maximal cliques of size 3, {a, b, c}, and {a, b, d}. Statements (1) and (2) must hold, so without loss of generality, let Ci ={a, b, c}, and Ci+k1 ={a, b, d}. The arguments just used convince us that y and z exist such that [a, y], [y, c), [a, z], [z, d) E E(G) and [y, b], [z, b] fj_ E(G). We know [y, z] fj_ E(G), since y E Cm implies m < i, and z E Cn 69
PAGE 77
implies n > i + k 1. Then we have an (induced) 4fan about [a, b] on d b & vertices a, b, c, d, y, and z. y x =a z Then the Type (5c) set associated with this 4fan and edge [a, b] properly contains N([a, b]), a contradiction to the maximality of Se inS'. We conclude that x N[[a, b]]. Subcase b: x N[[a, b]]. Since the argument in the proof of Lemma 4, Case 2, Subcase b does not involve a 4fan about [a, b), we may use the same argument to arrive at a contradiction in this case. We conclude from the two subcases that x E Se or Se is not a Type (5b) set. Case 3: The set Se is a Type (5c) set. Set Se is associated with a 4fan about [a, b] hinged at a. Suppose the 4fan is on vertices a, b, c, d, /,and g, as depicted b d & in the figure. f a g Then x Se = {a, c, d} U {all cliques of size at least 4 containing [a, b]}{b }. At least one of [b, f], [b, g] E(G), say [b, g] E(G). 70
PAGE 78
We claim [d, f] E(G). This is because [d,j] E E(G) implies [b, f] E E(G) (otherwise we have chordless 4cycle bdfc). However, if [d, j], [b, f] E E(G), then Se is properly contained in UCp, where a, bE Cp and jCpl 2: 4, contradicting the maximality of Se inS'. Hence [d, f] E(G). Then [c, g] E(G), since existence b d of [c, g] would create the chordless 4cycle bdgc. f a g Subcase a: x E N[[a, b]]. Suppose x =b. Certainly there are two paths of length 2 from x = b to a and two from x = b to any vertex in UCp, where a, bE Cp and jCpj 2: 4. We know of one path of length 2 from x = b to d and one from x to c. There is another path of length 2 from x = b to d, so there exists y E V (G) such y d that [b,y], [y,d] E E(G). f a g Since G is interval, [a, y] E E(G), otherwise we have the following subgraph in G. 71
PAGE 79
y c a g y d Thus we have the following subgraph in G. f a g If [b, f] or [y, c] E E(G), then Se is properly contained in UCP, where a, bE CP and ICPI 2: 4, so [b, !], [y, c] rf_ E(G). (Depicted above.) There is another path of length 2 from x = b to c, so there exists z E V (G) such that [b, z], [z, c] E E(G). Consider the subgraph of G induced on vertices a, b, c, d, J, and z. z f a d We know [a, z] E E(G), or else G is not interval. However, [a, z] E E(G) 72
PAGE 80
implies Se is properly contained in UCP, where a, bE Cp and ICPI 4. We conclude that x =I b. Suppose x = v, where {a, b, v} is a maximal clique of G, v =I c, d. Then [v, d], [v, c] rt E(G). It is clear that there are two paths of length 2 from x = v to every vertex in Se except a. We know of only one path of length 2 from x = v to a at this point, and that path is through b. Notice that [ v, f], [ v, g] E (G), since existence of these edges would create chordless 4cycles v fad and vbdg respectively. f a g Then there exists y y E V(G) {b,c,d,j,g} such that [v,y], [y,a] E E(G). f a g We see that [y, b] E(G), since this would create clique {a, b, v, y}, contradieting the maximality of clique {a, b, v}. Then [b, f] E E( G), since lack of this edge would create induced subgraph NC7 on vertices b, c, d, j, g, v, and y. f a g 73
PAGE 81
But then the set in S associated with the 4fan about [a, b] hinged at a induced on vertices a, b, d, g, v, and y is { v, d, a} U {UCP, where a, b E Cp and ICPI 4}, which properly contains Se, a contradiction. We conclude that x fj_ N[[a, b]]. Subcase b: x fj_ N[[a, b]]. By the definition of a 4fan, {a, b, d} is a maximal b d & clique of G; let Ci = {a, b, d}. f a g Suppose without loss of generality that x E Cm implies m < i. By the same reasoning as in the proof of Lemma 4, Case 1, Subcase b, the maximal cliques of G of size 4 that contain [a, b] occur consecutively and at the beginning of the list Ci, ... Ci+kl Thus Ci is the first clique in the ranking in which vertex d appears, and i < j i + k 1. Vertices x and d have two common neighbors, since dE Se. By the consecutive ranking, those neighbors are a and b. However x fj_ N[[a, b]], so x can't possibly be adjacent to both a and b. Hence we have a contradiction and conclude that Se is not a Type (5c) set. Case 4: The set Se is a Type (5d) set. Precisely those arguments used in Case 3 of this proof (with a's and b's interchanged) convince us that Se is not a Type (5d) set. 74
PAGE 82
We conclude from Cases 1, 2, 3, and 4 that x E Be and Be is a maximal clique Lemma 12 If a set in S' corresponds to a maximal clique of size at least 4 in G that has no nonsimplicial edges, then the set is a maximal clique in N2 (G). Proof: Suppose Ci = Be E S' and Ci is a maximal clique of G of size at least 4 with no nonsimplicial edges. To show that Be is a maximal clique in N2(G), assume there are two paths of length 2 from vertex x to every vertex in Be; we will show x E Be. Assume not. Also suppose { t, u, v, w} Be. Since Be has no nonsimplicial edges, any vertex not in Be (in particular x) is adjacent to at most one vertex in Be. Subcase a: Vertex x is adjacent to one vertex v in Be. There is another path of length 2 from x to u, so there exists a vertex y
PAGE 83
since [u, v] is not nonsimplicial. Consider the subgraph of G induced on vertices uy2xz1v. We know [y2, z1] (j: E(G), since this would create chordless 4cycle uy2z1v But the 5cycle uy2xz1 v is not chordless, since G is an interval graph. In fact, G interval implies that [x, u], [x, v] E E(G). Then {x, u, v} is a clique of G, contradicting the fact that [u, v] is not nonsimplicial. Hence x E Be and Be is a maximal clique in N2(G). Theorem 14 The collection of sets S' for a given interval graph G zs a {2) neighborhood cover of G consisting of maximal cliques of N2(G). Proof: This theorem follows directly from Lemmas 7 through 12. Corollary 4 An interval graph G has an interval {2)neighborhood graph if and only if S' has a consecutive ranking. We can use Corollary 4 to identify a class of interval graphs whose (2)neighborhood graphs are interval. Corollary 5 If G is an interval graph and the nonsimplicial edges of G are contained only in maximal cliques of size at least 4, then N2(G) is an interval graph 76
PAGE 84
Proof: Suppose G is an interval graph in which all nonsimplicial edges occur in maximal cliques of size at least 4. Let 01 ... Cr be a consecutive ranking of the maximal cliques of G. If G contains no nonsimplicial edges, then the only elements of S' are those maximal cliques of size at least 4. Certainly S' has a consecutive ranking, and thus (by Corollary 4) N2(G) is an interval graph. Assume G has at least one nonsimplicial edge. Define C([a, b]) to be the union of those cliques of G which contain nonsimplicial edge [a, b]; then C([a, b]) = N[[a, b]] and this set is the union of some consecutive cliques in the ranking Ct, ... Cr. The set S consists of cliques of size at least 4 with no nonsimplicial edges, and the sets C([a, b]) (one such set for every nonsimplicial edge [a, b]). In S', we have only the maximal sets of S; S' is essentially a "collapsed" version of the consecutive ranking C1 ... Cr, so S' certainly has a consecutive ranking, and N2 ( G) is an interval graph. 77
PAGE 85
5. The (2)Neighborhood Graphs of Interval Graphs Are Weakly Chordal. 5.1 Introduction The necessary and sufficient condition given in Chapter 4 for an interval graph to have an interval (2)neighborhood graph is a bit unwieldy. We concentrate in this chapter on the properties of interval graphs whose (2)neighborhood graphs are not interval. We will need the definition that follows. Definition : A graph G is weakly chordal if G contains no chordless cycles of length 5 or greater. Notice that weakly chordal graphs are perfect graphs. 5.2 If G is interval, then N2(G) is weakly chordal. Theorem 15 If G is an interval graph, then N2(G) is a weakly chordal graph. Proof: Suppose G is an interval graph and N2(G) contains the chordless cycle Suppose every pair of consecutive vertices on the cycle v1 v2 ... vk1 vk is adja cent in G. Since G is interval, some of the chords of the cycle are also in E(G). 78
PAGE 86
However, no matter which chords of the cycle are in E(G), some pair of noncon secutive vertices of the cycle ends up diagonally opposed on some 4cycle of G. This creates a chord in the chordless kcycle in N2 (G), a contradiction. Hence, there exists some consecutive pair of vertices on the kcycle, say v1 and v2 that is not adjacent in G. Suppose without loss of generality that C11 C2 ... Cr is a consecutive ranking of the maximal cliques of G in which the maximal cliques containing v1 appear strictly before those containing v2 (recall [v1 v2 ) fl. E(G)). Since v1 and v2 are adjacent in N2(G), IN(v1 ) n N(v2)1 ;::: 2 in G. Suppose x1 and x2 are both adjacent to v1 and v2 in G. Edge [x1,x2 ] E E(G), since G is interval. Since [vt,vk] E E(N2(G)), IN(vk) n N(v1)1 ;::: 2 in G. Notice that vk is not adjacent to both x1 and x2 in G, since if it were, edge [vk, v 2 ] would be in N2(G). Thus the maximal cliques containing vertex vk appear either before or after those containing both vertices x1 and x2 in the consecutive ranking. If the maximal cliques of G containing vertex vk appear after those containing both x1 and x2 in the consecutive ranking, then the common neighbors of vertices v1 and vk (of which v 2 is not one, since [v1 v 2 ] fl. E(G)) are also adjacent to v 2 This forces [vk, v 2 ] E E(N2(G)), a contradiction. Hence the maximal cliques of G containing 79
PAGE 87
vk all appear before those containing both x1 and x 2 in the consecutive ranking. Similar reasoning convinces us that the maximal cliques of G containing v3 all appear after those containing both x1 and x2 in the ranking. Extending the argument, we find that the maximal cliques containing Vkl through respectively, appear before those containing both x1 and x2 in the ranking. Case 1: k is odd. In this case, we find that the maximal cliques containing v3 ... appear after those containing both x1 and x2 However, the maximal cliques of G containing vertex must appear both before and after those containing x1 and x2 in the ranking, a contradiction We conclude that N2(G) contains no induced odd cycle of length 5 or greater. Case 2: k is even. Here we find that the maximal cliques of G containing v3 ... VI 2 appear after those containing both x1 and x2 in the ranking. Since the maximal cliques of G containing v &+2 appear before those containing x1 and x2 in the rank2 ing and those containing V!+1 appear after, we know thaf two common neighbors 2 of Vl+ 2 and V!+1 are adjacent to xb x2 and all of the common neighbors of x1 2 2 and x2 in G. However, this creates unwanted chords (for example [v1 V!+1]) in 2 N2(G), a contradiction. We conclude that N2(G) contains no induced even cycle of length 6 or greater. 80
PAGE 88
Hence, if G is an interval graph, N2 (G) is weakly chordal. 5.3 What if N2(G) contains a chordless 4cycle? Conjecture 1 IfG is an interval graph and N2(G) contains a chordless 4cycle, then G contains one of the following as an induced subgraph. VV\ Figure 5.1: If N2(G) has a chordless 4cycle as a generated subgraph, then G has one of the graphs above as a generated subgraph. Beginning of Proof: Suppose abed is a chordless 4cycle in N2(G). Then a and b are diagonally opposed on some 4cycle of G. Case I. A 4cycle in G on which a and bare diagonally opposed is contained in a complete subgraph. Suppose the subgraph of G induced on vertices a, b, x, and 81
PAGE 89
y in G is complete. Since [ c, d] is an edge of N2 (G), c and d have (at least) two common neighbors in G. The possibilities (without loss of generality) are: (1) c and dare both adjacent in G to a and b, (2) c and dare both adjacent in G to a and x, (3) c and dare both adjacent in G to x andy, ( 4) c and d do not have two common neighbors in the set {a, b, x, y}. Suppose (1) holds. Then [c, d], [c, x], [c, y], [d, x], [d, y] (/_ E(G). This is because any one of these edges would create chord [a, c) or chord [b, d] in N2(G). Since c and a are both adjacent tobin G, c and a have no other neighbors in common in G. Similarly, b and d have only one common neighbor in G, vertex a. Thus there exist two other vertices, say v and w, so that [a, v], [d, v], [c, w], [b, w] E E( G). Hence we c a v d have the following graph as an induced subgraph of G. Suppose (2) holds. Then we have the graph shown in the figure below as a subgraph of G, and as a result in N2 (G) we have edge [b, d], a contradiction. 82
PAGE 90
b a c y X d Suppose (3) holds. Then we have the graph shown in the figure below as a subgraph of G, and as a result [a, c], [b, d] E E(N2(G)), a contradiction. a X c b y d Suppose (4) holds. Without loss of generality, there are 3 subcases to consider (4)[1] c and dare both adjacent to a in G, (4)[2] c and dare both adjacent toxin G, (4)[3) c and d have no common neighbors in the set {a,b,x,y} We first consider the case (4)[1]. X b Let another common neighbor of c and d be labelled v (see the figure above). Note v (/. {a,b,x,y}, since we are in Case (4)[1). Since G is chordal, either [a,v] 83
PAGE 91
or [c, d] is an edge of G, but not both, since the presence of both in G would produce [a,c] in N2(G). Suppose [a, v] E E(G) and [c, d] E(G). Because band d have a as a common neighborinG, there must be no other vertices to which both band dare adjacent. The same is true for a and c, which are both adjacent to v in G. These two facts force the following nonedges in G: [d, y], [d, x], [b, v], [c, b], [c, x], and [c, y]. The forced nonedges of G are indicated in the figure below with dotted lines. The only remaining possible edges between the vertices mentioned thus far are [y, v], [x, v], and [b, d]. If [b, d] E E(G), then [x, v], [y, v] E(G), since these edges would create chordless 4cycles bdvx and bdvy respectively in G This would contradict the fact that G is an interval graph. Thus if [b, d] E E(G), we have the following induced subgraph in G. X Because b and c have a as a common neighbor, and no other vertices in the set {a, b, c, d, v, x, y} are adjacent to both band c, there exists a vertex q, not in the set 84
PAGE 92
{a, b, c, d, v, x, y} such that [b, q], [c, q] E E( G). There is only one way to consecu tively rank the four maximal cliques of G containing {a, b, x, y}, {a, b, d}, {a, d, v}, and {a, v, c}. In fact, the listing given is the only way to consecutively rank them. Since the ranking is consecutive and [b, q], [c, q] E E( G), q is adjacent to a, d, and v (see the figure below). This forces edges [a, c] and [b, d] in N2(G), a contradiction. We conclude that [b, d] E(G). X Thus we have in G the subgraph shown in the figure below, possibly with edge [v, x] or [v, y] (perhaps both). X b If [v, x] is an edge of G and [v, y] is not (see the figure below), then there exists a vertex q that is adjacent to both band c in G (otherwise they only have a as a common neighbor). y X 85
PAGE 93
By consecutive ranking of the maximal cliques of G, q is in a maximal clique of G containing a, x, and v, forcing [a, c] into the edge set of N2(G), a contradiction (see the figure below). y X The same reasoning as above convinces us that it is not possible for [v, y] to be in the edge set of G if v, x] is not. Can both [v, y] and [v, x] be edges in G? The answer is no. If they both were, then we would have the graph shown in the figure below as an induced subgraph of G. y X Again, the consecutive ranking of the maximal cliques of G is forced to have a maximal clique containing {a, x, y, v} between a maximal clique containing b and one containing c. Vertices b and c must have a common neighbor q that is not in the set {a, b, c, d, v, x, y }. Then the consecutive ranking just mentioned forces 86
PAGE 94
q to be adjacent to a, x, y, and v. Then a and c are both adjacent q and v, a contradiction. The only possibility that remains to be considered in this subcase of (4)[1] in which [a, v] E E(G) and [c, d] E(G) is the one in which neither [v, y] nor [v, x] is in E(G). Thus we have the subgraph shown below induced in G. X b Let q be adjacent to both a and d, with q {a,b,c,d,v,x,y}. Edges [b,q] and [q, c] in G would force edges [b, d] and [a, c] in N2(G), so neither [b, q] nor [q, c] is an edge in G. Thus there exists another vertex p not in {a, b, c, d, v, x, y, q} that is adjacent to both band c. We must consider the 4cycle acpb in G. Since G is interval, this 4cycle must have at least one chord. However, both chords [a,p] and [b, c] force a and c to be diagonally opposed on 4cycles of G, thus forcing edge [a, c] into N2(G), a contradiction. We conclude that in case (4)[1], it is not the case that [a, v] E E(G) and [c, d] E(G). Recall that it is not possible to have both edges [a, v] and [c, d] in E(G). Thus it remains to consider the case where [c, d] E E(G) and [a, v] E(G). Because a and c are both adjacent to d, the following nonedges are forced: [c, b], [c, x], 87
PAGE 95
and [c, y]. Since band dare both adjacent to a, [b, v], [d, y], and [d, x] are forced non edges in G (see the figure below). c v X b The edges that we can possibly add are: [v, y], [v, x], and [b, d]. Suppose [b, d] E E(G). Then [v, y], [v, x] rJ E(G), since they create chordless 4cycles in G. Thus [b, d] E E(G) implies the graph below is an indilced subgraph of G. y a c r>
PAGE 96
Vertices a and d are both adjacent to vertex c. Let q be another neighbor of a and d, q rf. {a, b, c, d, v, x, y }. The following nonedges are forced: [q, v], [q, c], [q, b]. the only possible edges to consider at this point are [q, x] and [q, y] (see the figure below). c q Suppose [q, x] E E(G) and [q, y] rf. E(G)? Then we are locked into one choice for the consecutive ranking of the maximal cliques of G that contain {a, b, x, y}, {a, x, q}, {a, q, d}, {a, d, c}, and { d, c, v} respectively, as the figure below indi cates. c v q Thus far, We are aware of one common neighbor of b and c, vertex a. No other vertex in the set {a, b, c, d, v, x, y, q} is adjacent to both b and c. Let p be a vertex adjacent to both b abd c. Then by the consecutive ranking, p is in a 89
PAGE 97
maximal clique with a, x, and q and in another one with a, q, and d. Then a and c are both adjacent to p and to d, a contradiction. We conclude that it is not the case that [q, x] E E(G) and [q, y] (/. E(G). Suppose we have [q, y] E E(G) and [q, x] (/. E(G). the same argument as directly above leads to a contradiction. It remains to consider the case that both [q, x] and [q, y] E E(G). A look at the figure below convinces us that the only possible ranking of the maximal cliques of G containing {a,b,x,y}, {a,x,y,q}, {a,q,d}, {a,d,c}, and {d,c,v} respectively is in precisely the given order. c v q Vertices band c have some common neighbor p (/.{a, b, c, d, v, x, y, q}. Thus, by consecutive ranking, p is adjacent to a, q, d, x, and y. However, p adjacent to both b and d implies [b, d] E E(N2(G)), a contradiction. We conclude that neither [q, y] nor [q, x] is an edge of G. 90
PAGE 98
c v q Thus the graph shown above is an induced subgraph of G. There must exist a vertex, m (j. {a, b, c, d, v, x, y, q}, that is adjacent to both b and c. However, this creates 4cycle acmb, and both chords [a, m] and [b, c] force [a, c] into the edge set of N2(G), a contradiction. We conclude that it is not possible to have [b,d] (j. E(G). This concludes subcase (4)[1). Hence, if the two common neighbors of c and d are a and v, where v (j. {a, b, x, y}, then G has the graph depicted below as an induced subgraph. y a c I>
PAGE 99
6. Conclusion There are many directions in which the research discussed here can be taken for future study. We conclude by listing some of those possibilities. As mentioned at the end of Chapter 2, it remains an open problem to fully classify those (trianglefree) graphs which are (2)neighborhood graphs, and the question for [2]neighborhood graphs is yet to be considered. The necessary and sufficient condition for an interval graph to have an interval (2)neighborhood graph given in Chapter 4 can certainly be further explored. It would be nice to find more classes of interval graphs which satisfy the necessary and sufficient condition. To this end, the work begun in Chapter 5 will most likely be helpful. Completion of the proof of Conjecture 1 is an obvious starting point. Future work should also include attempts to generalize other results on neigh borhood graphs to (p )neighborhood graphs. Some questions to consider are "when is a graph isomorphic to its (p)neighborhood graph?' and "when is the complement of G isomorphic to Np( G)?" There are many other results for the case p = 1 whose generalizations to larger p would make an interesting study. 92
PAGE 100
References [1] B. D. Acharya and M. N. Vartak. Open neighborhood graphs. Research Report 7, Indian Institute of Technology Dept. of Mathematics, 1973. Bombay400 076, India. [2] C. A. Anderson, L. Langley, J. R. Lundgren, and S. K. McKenna, P. A. and Merz. New classes of pcompetition graphs and >tolerance competition graphs. Congressus Numerantium, 100:97107, 1994. [3] J. W. Boland, R. C. Brigham, and R. D. Dutton. The difference between a neighborhood graph and a wheel. Congressus Numerantium, 58:151156, 1987. [4] J. W. Boland, R. C. Brigham, and R. D. Dutton. Embedding arbitrary graphs in neighborhood graphs. Journal of Combinatorics, Information, and System Sciences, 12:101112, 1987. [5] R. C. Brigham and R. D. Dutton. A characterization of competition graphs. Discrete Applied Mathematics, 6:315317, 1983. 93
PAGE 101
[6) R. C. Brigham and R. D. Dutton. On neighborhood graphs. Journal of Combinatorics, Information, and System Sciences, 12:75 85, 1987. [7] R. C. Brigham, F. R. McMorris, and R. P. Vitray. Tolerance competition graphs. Linear Algebra and Its Applications, 217:41, 1995. [8] R. C. Brigham, F. R. McMorris, and R. P Vitray. Two>tolerance compe tition graphs. Discrete Applied Mathematics, 66(2):101, 1996. [9) J. E. Cohen. Interval graphs and food webs: A finding and a problem Document 17696PR, RAND Corporation, 1968. [10) D. C. Fisher, J. R. Lundgren, S. K. Merz, and K. B. Reid. Domination and competition graphs of tournaments. To appear in Journal of Graph Theory, 1996. [11) K. F. Fraughnaugh, J. R. Lundgren, J. S. Maybee, S. K. Merz, and N. J. Pullman. Competition graphs of strongly connected and Hamiltonian di graphs. SIAM Journal on Discrete Mathematics, 8(2):179185, 1994. [12) D. R. Fulkerson and 0. A. Gross. Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15:835855, 1965. [13] F. Harary and T. McKee. The square of a chordal graph. Discrete Mathe matics, 128: 165172, 1994. 94
PAGE 102
[14] G. Isaak, S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. 2competition graphs. SIAM Journal on Discrete Mathematics, 5:524538, 1992. [15] S. Kim. Competition graphs and scientific laws for food webs and other systems. PhD thesis, Rutgers University, 1988. [16] S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. pcompetition numbers. Discrete Applied Mathematics, 46:8792, 1993. [17] S. R. Kim, T. A. McKee, F. R. McMorris, and F. S. Roberts. pcompetition graphs. Linear Algebra and Its Applications, 217:167178, 1995. [18] L. Langley, J. R. Lundgren, P. A. McKenna, S. K. Merz, and C. W. Ras mussen. The pcompetition graphs of strongly connected and Hamiltonian digraphs. Submitted to Ars Combinatoria, 1995. [19] L. Langley, J. R. Lundgren, and S. K. Merz. The competition graphs of interval digraphs. Congressus Numerantium, 107:3740, 1995. [20] J. R. Lundgren, J. S. Maybee, and C. W. Rasmussen. An application of gen eralized competition graphs to the channel assignment problem. Congressus Numerantium, 71:217224, 1990. 95
PAGE 103
[21] J. R. Lundgren, S. K. Merz, J. S. Maybee, and C. W. Rasmussen. A char acterization of graphs with interval twostep graphs Linear Algebra and Its Applications, 217:203 223, 1995. [22] J. R. Lundgren S. K. Merz, and C. W. Rasmussen. A characterization of graphs with interval squares. Congressus Numerantium, 98 : 132 142, 1993. [23] J. R. Lundgren and C. W. Rasmussen. Twostep graphs of trees. Discrete Mathematics 119:123140 1993. [24] J.R. Lundgren, J.S. Maybee, and C W. Rasmussen. Interval competition graphs of symmetric digraphs. Discrete Mathematics, 119:113122, 1993. [25] G. E. Major. pedge clique coverings of graphs. Masters Thesis, University of Louisville, Louisville, KY, 1990. [26] G. E. Major and F. R. McMorris. pedge clique coverings of graphs. Con gressus Numerantium, 79:143145, 1990. [27] A. Raychaudhuri. Intersection assignments, tcolorings, and powers of graphs. PhD thesis, Rutgers University, 1985. [28] A. Raychaudhuri and F. S. Roberts Generalized competition graphs and their applications. Methods of Operations Research, 49:295311, 1985 96
PAGE 104
[29) F. R. Roberts and J E. Steif. A characterization of competition graphs of arbitrary digraphs. Discrete Applied Mathematics, 6:323326, 1983. [30) F. S. Roberts. Discrete Mathematical Models, with Applications to Social, Biological, and Environmental Problems. Prentice Hall, Englewood Cliffs, New Jersey,. 1976. [31) F. S. Roberts. Applications of edge coverings by cliques. Discrete Applied Mathematics 10: 93109 1985 97

