DOMINATION GRAPHS OF NEARREGULAR
TOURNAMENTS
AND THE DOMINATIONCOMPLIANCE GRAPH
by
Guillermo Jimenez
B.S., California State University San Marcos, 1994
M.S., University of Colorado at Denver, 1997
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
1998
This thesis for the Doctor of Philosophy
degree by
Guillermo Jimenez
has been approved
by
J. Richard Lundgren
David C. Fisher
Kathryn L. Fraughnaugh
Stephen C. Billups
Gary A. Kochenberger
Date
Jimenez, Guillermo (Ph. D., Applied Mathematics)
Domination Graphs of NearRegular Tournaments
and the DominationCompliance Graph
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
The competition graph C(D) of a digraph D is the graph on the same
vertex set as D with an edge between vertices x and y if and only if there
is a vertex z ^ x,y such that (x,z) and (y,z) are arcs in D. Competition
graphs were first introduced in 1968 by J.E. Cohen in conjunction with his
study of food webs. Most recently, in 1994 Fisher, et al., studied competi
tion graphs of tournaments. In their examination of competition graphs of
tournaments, Fisher, et al., introduced the domination graph of a tournament.
The domination graph dom(T) of a tournament T is the graph on the same
vertex set as T with edges between vertices which together beat every other
vertex in T. Since the introduction of domination graphs, Fisher, et al., have
successfully characterized domination graphs of arbitrary tournaments. In this
work, we concentrate on a series of problems closely related to the work on
the domination graph of a tournament. First, we address the question, Which
tournaments have connected domination graphs? We answer this question and
m
present characterizations for all tournaments that have connected domination
graphs. Next we examine a graph that is closely related to the domination
graph. The dominationcompliance graph DC(T) of a tournament T is the
graph on the same vertex set as T with edges between pairs of vertices that
together either beat every other vertex in T or are beaten by every other ver
tex in T. Our primary goal for this work is to find a characterization for the
dominationcompliance graph of a tournament. We will present some initial re
sults on this topic. Finally, we examine the domination graph for nearregular
tournaments. We characterize all connected graphs and all forests of nontrivial
paths that are the domination graphs of nearregular tournaments. In addi
tion, we develop several large classes of nearregular tournaments which have
interesting structural properties.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
J. Richard Lundgren
DEDICATION
I would like to dedicate this work to my wife, son, mother, father,
three brothers and baby sister. Thanks for your love and support.
v
ACKNOWLEDGEMENT
First and foremost, I would like to thank my advisor J. Richard Lund
gren for his guidance, support, patience, encouragement and especially for his
friendship.
I would also like to thank my committee members David Fisher,
Kathy Fraughnaugh, Steve Billups and Gary Kochenberger for their advice
and help in preparing this work.
Lastly, I would like to thank K. Brooks Reid and Carolyn Mahoney
for encouraging me to go to graduate school.
vi
CONTENTS
Chapter
1. Introduction................................................... 1
1.1 Overview ........................................................ 6
1.2 Definitions and Notation......................................... 7
2. Tournaments with Connected Domination Graphs................... 10
2.1 Introduction.................................................... 10
2.2 Tournaments with connected domination graph..................... 11
3. The DominationCompliance Graph of a Tournament................ 32
3.1 Introduction.................................................... 32
3.2 DominationCompliance Graph of Tournaments...................... 35
3.3 Consequences of the upper bound and forbidden subgraphs .... 48
3.4 Characterization for reducible and regular tournaments.......... 51
4. Domination Graphs of NearRegular Tournaments.................. 59
4.1 Introduction.................................................... 59
4.2 Connected Domination Graphs of NearRegular Tournaments . 60
5. NearRegular Path Tournaments.................................. 89
5.1 Introduction.................................................... 89
5.2 Forests of m even paths and n nontrivial odd paths.............. 90
vii
6. Odd Gapped Pendant Restricted Caterpillars
144
6.1 Introduction................................................... 144
6.2 Families of Odd Gapped Pendant Restricted Caterpillars......... 145
6.3 Subtournaments Induced by OGPR Caterpillars.................. 152
7. NearRegular Forest Tournaments.................................. 169
7.1 Introduction................................................... 169
7.2 Two Constructions.............................................. 169
8. Conclusion....................................................... 200
Appendix
A. Proof of Theorem 3.10........................................... 201
References.......................................................... 218
viii
1. Introduction
The focus of this dissertation is the study of two graph theoretic con
cepts: domination graphs of nearregular tournaments and the domination
compliance graph of a tournament. These two concepts are closely related and
have their origins in competition graphs.
A digraph D is a set V(D) of vertices and a set A(D) of ordered pairs
of distinct vertices called arcs. The competition graph C(D) of a digraph D
is the graph on the same vertex set as D with an edge between vertices x and y
if and only if there is a vertex z ^ x,y such that (x, z) and (y, z) are arcs. Com
petition graphs were first introduced and studied in 1968 by J. E. Cohen [11], in
conjunction with his study of food webs in ecology. Competition graphs have
several important applications, such as frequency assignments in large com
munication networks, simplification or modification of large scale computer
models, communications over noisy channels, military communications, and
radio and television transmissions [36, 37]. In the last 20 years, an extensive
amount of literature has been devoted to the study of competition graphs.
Some samples of this literature include [7, 12, 20, 21, 24, 25, 26, 29, 30, 32, 35].
Generalizations of the competition graph have also been introduced
and studied. These include the resource graph, the niche graph and the com
petition/resource graph. The resource graph R(D) of a digraph D is the
1
graph on the same vertex set as D with an edge between vertices x and y if and
only if there exists a vertex z ^ x,y such that (z, x) and (z, y) are arcs. Re
source graphs have been considered by Sugihara [40] and Wang [41]. The niche
graph N(D) of a digraph D is the graph on the same vertex set as D with
an edge between vertices x and y if and only if there exists a vertex z ^ x,y
such that either (z, x) and (z, y) are arcs or (x, z) and (y, z) are arcs. Niche
graphs were first introduced by Cable, et al, in [8]. Since their introduction,
niche graphs have been studied by Anderson, et al., [1, 2, 3], Bowser and Cable
[4, 5], and Fishburn and Gehrlein [13, 14, 15]. The competition/resource
graph CR(D) of a digraph D is the graph on the same vertex set as D with
an edge between vertices x and y if and only if there is an edge joining x and y
in both the competition graph and resource graph of D. Competition/resource
graphs have been studied by Jones, et al, [23], Kim, et al, [27], Seager [39],
and Scott [38].
v
u
V
u
Figure 1.1. A digraph and its competition graph.
2
In recent years, the literature on competition graphs has focused on
the study of competition graphs for a specified class of digraphs [17, 20, 28].
Of these, the most recent has been the study of competition graphs of tourna
ments. A tournament is a digraph without loops in which every pair of distinct
vertices is joined by exactly one arc. In 1994, Fisher, Lundgren, Merz and Reid
[17] were the first to consider competition graphs of tournaments. While ex
amining the competition graph of a tournament, Fisher, et al, introduced the
concept of the domination graph. The domination graph dom(T) of a tour
nament T is the graph on the same vertex set as T with an edge between
vertices x and y if for all vertices z ^ x,y either (x, z) is an arc or (y, z) is an
arc. We will say that two such vertices form a dominant pair. See Figure
1.2.
The domination graph of a tournament is closely related to the com
petition graph of a tournament in the following way: the domination graph of
a tournament T is the complement of the competition graph of the reversal of
T, where the reversal of a tournament T is the tournament obtained from T
by reversing all the arcs. Thus, results obtained for the domination graph of a
tournament yield results for the competition graph of a tournament. The mo
tivating factor behind studying domination graphs over competition graphs is
that the domination graph of a tournament generally has fewer edges than the
competition graph of a tournament, which makes it easier to state and prove
3
results. As a consequence, Fisher, et al., [17] determined all possible domina
tion graphs of tournaments as stated in Theorem 1.1. A vertex in a graph is a
pendant vertex if it is the endpoint of exactly one edge in the graph. A cycle
of length n is a graph with vertex set x\,x2,.........r and edges [xi,xi+1], for
1 < i < n 1, and [xn,x\}. An oddspiked cycle is a graph such that removal
of all pendant vertices yields a cycle with odd length. Note that every odd
cycle is an oddspiked cycle. A path with n vertices is a graph with vertices
x\,x2,.....r and edges [xi,Xi+1] for all i with 1 < i < n 1. A tree is a
connected graph with no cycles. A caterpillar is a tree such that the removal
of all pendant vertices yields a path (possibly the trivial path on one vertex).
Note that every path is a caterpillar.
Theorem 1.1 (Fisher et al. [17]) Let T be a tournament. Then dom(T)
is either an oddspiked cycle with or without isolated vertices, or a forest of
caterpillars.
T =
Figure 1.2. A tournament and its domination graph.
4
Much further work has been devoted to domination graphs. In [18],
Fisher, et al., extended their results in [17] to oriented graphs. Also in [16, 19],
Fisher, et al., investigated and answered the following two questions: Which
connected graphs are the domination graphs of tournaments and Which forests
of nontrivial caterpillars are the domination graphs of tournaments? Cho, Kim
and Lundgren have recently considered domination graphs of regular tourna
ments [10]. Doherty and Lundgren [9] are currently examining domination
graphs of path tournaments. Path tournaments will be defined in Chapter 5.
As with competition graphs, generalizations of the domination graph
have also been introduced and studied. The compliance graph com(T) of a
tournament T is the graph on the same vertex set as T with an edge between
vertices x and y if for all vertices z ^ x,y either (z, x) is an arc or (z, y) is
an arc. The compliance graph was first introduced by Jimenez and Lundgren
and will be discussed in Chapter 3. In addition, the compliance graph of a
tournament is related to the domination graph in the following way: the com
pliance graph of a tournament T is the domination graph of the reversal of T,
where the reversal of a tournament T is the tournament obtained from T by
reversing all the arcs in T. Note that this relationship gives us that a graph
is the compliance graph of a tournament if and only if it is also the domina
tion graph of a tournament. Thus, since domination graphs of tournaments
have been characterized, we get that the compliance graphs of tournaments
5
are also characterized. The mixedpair graph mp(T) of a tournament T is
the graph on the same vertex set as T with an edge between vertices x and y if
for all vertices z ^ x,y either (x,z) and (z,y) are arcs or (z,x) and (y,z) are
arcs. The mixedpair graph of a tournament has been examined by Bowser,
Cable, and Lundgren [6]. The dominationcompliance graph DC(T) of a
tournament T is the graph on the same vertex set as T with edges between
vertices x and y if either there is an edge joining x and y in the domination
graph of T or there is an edge joining x and y in the compliance graph of T.
The dominationcompliance graph of a tournament is studied in Chapter 3.
1.1 Overview
As noted earlier, Fisher, et al, examined the question, Which con
nected graphs are the domination graphs of tournaments?. In [19], they deter
mined all connected graphs that are the domination graphs of tournaments.
Since all connected domination graphs of tournaments have been determined,
we found it natural to ask the following: Which tournaments have connected
domination graphs? We address and answer this question in Chapter 2. The
work presented in Chapter 2 will also prove to be of fundamental importance
to the chapters that follow Chapter 2.
Which graphs are the dominationcompliance graphs of tournaments?
Chapter 3 addresses this question. In Section 3.2, we exhibit an upper bound
on the number of edges in the dominationcompliance graph of a tournament.
6
In Section 3.3, we examine consequences of the upper bound on the number
of edges and exhibit some forbidden subgraphs. Lastly, in Section 3.5, we pro
vide characterizations for the dominationcompliance graphs of reducible and
regular tournaments.
In Chapters 4 through 7, we examine domination graphs of near
regular tournaments. In particular, we address the question: Which graphs are
domination graphs of nearregular tournaments? We do so by examining the
following three questions: Which connected graphs are the domination graphs
of near regular tournaments, Which forests of paths are the domination graphs
of nearregular tournaments and Which forests of caterpillars are the domi
nation graphs of nearregular tournaments? The first two questions are the
focus of Chapters 4 and 5, respectively. The last question will be addressed in
Chapters 6 and 7.
Finally in Chapter 8, we present avenues for future work with respect
to the topics presented in this dissertation.
1.2 Definitions and Notation
A graph G is a set V(G) of elements called vertices and a list E(G)
of pairs of those vertices called edges. We will denote an edge e E E(G)
with its endpoints x,y E V(G) as [x,y\ and say that x and y are adjacent or
neighbors in G. The degree of a vertex x E V(G) is the number of edges
that have x as an endpoint. A vertex is isolated if it has degree 0. A vertex
7
is pendant if it has degree 1.
A subgraph of a graph G is a graph H such that V(H) C V(G)
and E(H) C E(G). An induced subgraph of a graph G, induced by
a vertex set S C V(G), is a subgraph H with vertex set S and edge set
/:(//) = {[x,y] e E(G) : X,ye S}.
A cycle Cn of length n is a graph with vertex set x1;x2, ....r
and edges [xi,xi+1], for 1 < i < n 1, and [xn.xi]. An oddspiked cycle
is a graph such that removal of all pendant vertices yields a cycle with odd
length. Note that every odd cycle is an oddspiked cycle. A path Pn with
n vertices is a graph with vertices x\,x2,... ,xn and edges [xi,Xi+1] for all i
with 1 < i < n 1.
A tree is a connected graph with no cycles. A caterpillar is a tree
such that the removal of all pendant vertices yields a path (possibly the trivial
path on one vertex). This path will be referred to as the spine of the cater
pillar, and the number of vertices on the spine is the length of the caterpillar.
A forest is a graph whose connected components are trees.
A proper coloring of a graph G is an assignment of one color to each
vertex such that if two vertices are adjacent, then they are assigned different
colors.
A directed graph or digraph D is a set V(D) of vertices and a set
A(D) of ordered pairs of distinct vertices called arcs. We denote an arc from
8
vertex x to vertex y by either (x, y) E A(D) or x > y and say that x beats y.
For all vertices x E V(D) the outset Od(x) or O(x) of x is the set of vertices
that x beats. Similarly, the inset Id(x) or I(x) is the set of vertices that beat
x. Let d)(x) or d' (x) = 0(x) be the outdegree of x in D. We will also
refer to the vertices in O(x) (I(x)) as outneighbors (inneighbors) of x.
A tournament is a digraph without loops in which every pair of dis
tinct vertices is joined by exactly one arc. An ntournament is a tournament
with n vertices. A transmitter is a vertex in an ntournament with outdegree
n 1. Let S be a subset of V(T). Then T(S) will denote the subtournament
induced by the set of vertices in S. The reversal T of a tournament T is the
tournament obtained from T by reversing all the arcs. An ntournament is
71 1
regular if n is odd and every vertex has outdegree . An ntournament
is nearregular if n is even and every vertex has outdegree either ^ or ^ 1.
A tournament is reducible if its vertex set can be partitioned into nonempty
sets A and B such that every vertex in A beats every vertex in B. A tourna
ment is strongly connected if it is not reducible.
For more basic graph theory definitions see West [42]. Also for more
on tournaments see Moon [31], Beineke and Reid [34], and Reid [33].
9
2. Tournaments with Connected Domination Graphs
2.1 Introduction
In this chapter, we characterize those tournaments with connected
domination graphs. In the introductory chapter, we presented Theorem 1.1
which determines all possible domination graphs of a tournament. Due to this
theorem, one can see that the only possible connected domination graphs of
tournaments are oddspiked cycles and caterpillars. However, Fisher, et al.,
discovered that not every caterpillar is the domination graph of a tournament.
In [19], Fisher, et al., determined that the only caterpillars that are domination
graphs of tournaments are those that have three or more vertices pendant to
at least one end of the spine. We summarize their result below. A star is a
tree with one vertex adjacent to all others and a nonstellar caterpillar (a
caterpillar that is not a star) is a caterpillar that has at least two vertices on
its spine.
Theorem 2.1 (Fisher, et al., [19]) A connected graph is the domination
graph of a tournament if and only if it is an oddspiked cycle, a star, or a
nonstellar caterpillar with three or more vertices pendant to at least one end of
the spine.
10
Knowing which connected graphs occur as the domination graphs of
tournaments, we find it natural to ask: Which tournaments have these graphs
as their domination graphs? In the remainder of this chapter, we will consider
this question. In particular, we shall determine all tournaments that have stars,
oddspiked cycles, and caterpillars with three or more vertices pendant to at
least one end of the spine, as their domination graphs.
2.2 Tournaments with connected domination graph
We open this section with an important digraph that will prove useful
not only in this chapter but throughout this dissertation.
Define an orientation of an undirected graph to be an assignment of
order to each of the edge pairs that results in a digraph. Then the domination
digraph X>(T) of a tournament T is an orientation of dom(T) induced by T,
i.e., V(T) is the digraph on the same vertex set as T with an arc (x,y) if x
and y form a dominant pair and x beats y in T. The domination digraph
of a tournament will be an important tool in this chapter for reasons to be
explained below and which are largely due to the following lemma.
Lemma 2.2 (Fisher, et al., [18]) Let T be a tournament and let x E V(T).
In T>{T), we have that /(a;) < 1 and at most one vertex in O(x) can have
nonzero outdegree.
11
Stated differently, Lemma 2.2 says that in the domination digraph a
vertex can have at most one inneighbor and at most one outneighbor with
outneighbors. Now as we mentioned above, the domination digraph and in
particular Lemma 2.2 will be an important tool in this, as well as in the forth
coming chapters. In this chapter it will be used as follows: Let G be a connected
graph that is known to be the domination graph of a tournament. Then for
all tournaments that have G as their domination graph, their corresponding
domination digraphs must be an orientation of G. Since Lemma 2.2 provides
restrictions on the structure of the domination digraph, then by abiding to
these restrictions we can determine all possible orientations of G that would
give a valid domination digraph. Therefore, Lemma 2.2 is being used to de
termine all possible domination digraphs for all tournaments that have G as
their domination graph. Then by using all these possible domination digraphs
as a starting point, we will then be able to proceed in constructing all tour
naments that have G as their domination graph. The next theorem illustrates
this procedure. Let Kijn denote a star on n + 1 vertices.
Theorem 2.3 Let T be an ntournament with n > 2. Then the domination
graph of T is a star if and only if T has a transmitter or two distin
guished vertices x and y such that
i) y beads x,
12
ii) for all vertices z ^ x,y, it follows that x beats z and z beads y, and
Hi) T {x,y} induces a subtournament without a transmitter.
Proof: First assume that T is a ntournament whose domination graph is
1 Let x be the vertex with degree n 1 in Consider V(T). By
Lemma 2.2, in the domination digraph a vertex can have indegree at most 1
and can have at most one outneighbor with outneighbors. Thus, we have two
possible orientations for V(T). These are described in the following figure.
Figure 2.1. Two possible orientations of a domination graph that is a star.
First consider Orientation 1. Note that under this orientation, x has
outdegree n 1, so x is a transmitter.
Next consider Orientation 2. Under this orientation, x has outdegree
n 2. Also note that there is one vertex y with outdegree 1. Let z be an
arbitrary vertex such that z ^ x,y. Since [z,x] dom(T) and y beats x,
it follows that z beats y. Let T {./. y} denote the subtournament of T
on V(T)\{x, y}. Now suppose that the subtournament T {x,y} contains
a transmitter w. Then since x beats every vertex in V(T)\{x,y,w} and y
13
beats x, we have that y and w form a dominant pair. This is a contradiction
since [w,y] dom(T). Thus, T {x,y} must be a subtournament without a
transmitter.
For the converse, first assume that T is a tournament that contains
a transmitter x. If y e F(T)\{a;}, then x and y form a dominant pair since
x beats every vertex in F(T)\{a;}. Thus, K^n_i C dom(T). To show that
dom(T) = /\'i. i it suffices to show that no other pair of vertices form a
dominant pair. Let y,z F(T)\{a;}. Since x beats both z and y, it follows
that z and y cannot possibly form a dominant pair.
Next assume that T is a tournament with two distinguished vertices
x and y such that i) y beats x, ii) for all vertices z ^ x,y, it follows that x
beats z and z beats y, and in) T {x,y} induces a subtournament without a
transmitter. First we show that is a subgraph of dom(T). Since (x,z)
is an arc for all vertices z ^ x,y, we may conclude that [x,y\ e dom(T). In
addition, since (z, y) is also an arc for all z ^ x,y, it follows that [z, x]
dom(T) for all z Â£ V(T)\{x,y}. Thus K^n_i C dom(T). To show that
dom(T) = /\'i. i it suffices to show that no other pair of vertices form a
dominant pair. Let z and tv be in V(T)\{x,y}. Since (x,z) and (x,w) are
arcs, [z,w] 0 dom(T). In addition, z and y cannot possibly form a dominant
pair. This follows from the fact that T {./. y} does not have a transmitter.
So there must exist a vertex u such that u beats z and by construction u beats
14
y. Therefore, dom(T) = K
Another important digraph that will play an important role is Un.
Let Un denote the tournament on the set of vertices {.rt...,xn} with arcs
(xi,xj) if i j is odd and negative or even and positive. Notice that Un is a
regular tournament when n is odd and is a nearregular tournament otherwise.
We leave the verification of this fact to the reader.
Now in [17], Fisher, et al., determined that if dom(T) is an odd cycle
('. then the only possibility for 7' is Therefore, we have the next result.
Theorem 2.4 (Fisher, et al., [17]) Let T be a ntournament where n is
odd. Then dom(T) = Cn if and only if T = Un. Furthermore, for all i,
[xi,Xi+1] e dom(Un), where i + 1 = (i mod n) + 1.
Figure 2.2. The tournaments U5 and Ue.
15
Observe that Theorem 2.4 explicitly tell us what pairs of vertices
form dominant pairs in Un, for n odd. In addition, Theorem 2.2 is implicitly
providing information regarding pairs of vertices that do not form dominant
pairs. Specifically, it gives us that if j i + l,i l {mod n), then for vertices Xi
and Xj in V(Un), there must exist a vertex xi V(Un) such that xi beats both
Xi and Xj. This is true because Xi and Xj do not form a dominant pair in Un
when j i + l,i 1 (mod n). This observation will be exploited throughout
this work. Now it was mentioned above that Un is a regular tournament when n
is odd. Due to this fact the next result will provide a useful property regarding
dominant pairs in Un.
Lemma 2.5 Let T he a regular tournament. If vertices x,y V{T) form, a
dominant pair, then O(x) fl O(y) = 0.
Proof: Let T be a regular ntournament and .r. // t V(T). Assume x and y
form a dominant pair and that x beats y. Then since [x, y\ dom(T), we have
that \0{x) U 0(y)  = n 1. Thus, since every vertex in a regular ntournament
has outdegree ^ ^ ^ follows that \0(x) HO{y)\ = \0(x) \ + \ 0{y) \ \0(x) U
0(y) = n 2 ^ + n ^ ^ (n 1) = 0. Therefore, O(x) fl 0(y) = 0.
Lemma 2.5 along with the following result will prove useful in the
characterization of those tournaments whose domination graphs are oddspiked
cycles. A proof of the following result can be found in [17].
16
Lemma 2.6 (Fisher, et al., [17]) Let S be an induced subdigraph of a di
graph D. Then the induced subgraph of dom(D) on the vertices of S is a
subgraph ofdom(S).
In [17], Fisher, et al., provided the following construction for a tour
nament T, given an oddspiked cycle G. Let {.rt... ,Xk}, where k is odd,
represent the set of vertices on the cycle of G and represent the set of
vertices pendant at x,. The tournament T is constructed by first letting
T({x\, X2, , Xk}) Uk and then orienting arcs from Xi to every vertex in
for all 1 < i < k. Next, if x, beats Xj, then arcs are oriented from vertices
in Vi to vertices in \). every vertex in \) beats x,, and Xj beats every vertex in
V^ Finally, arcs within each pendant set V] are oriented arbitrarily. Fisher, et
al., showed that the tournament T constructed by this method had the prop
erty that its domination graph is G. We extend this result by showing that
if T is a tournament whose domination graph is an oddspiked cycle, then T
must be constructed by the method just described.
Let r0 denote the set of all tournaments T with the following prop
erties. The vertex set of T can be partitioned into the sets {x\,X2,...,Xk},
V\, U......and with k odd. The arcs in T are as follows:
The subtournament T({x\, x2,..., Xk}) Uk
For all i, arcs are oriented from x, to vertices in V%.
The arcs within each set Vt are arbitrary.
17
The remaining arcs in T are as in Figure 2.3. In other words, if re*
beats Xj, then arcs are oriented from vertices in Vj to vertices in V},
from Xj to vertices in Vj, and from vertices in Vj to Xj.
Figure 2.3. This figure determines the arcs between the Vjs and rcjs
If a tournament T belongs to I'. we will say that T is a spiked cycle tourna
ment. Notice that the construction that was discussed above always produces
a spiked cycle tournament.
Theorem 2.7 Let T be a tournament. Then the domination graph ofT is an
oddspiked cycle if and only if T is a spiked cycle tournament.
Proof: Let T be a tournament whose domination graph is an oddspiked cycle.
Assume the cycle of dom(T) consists of k vertices where k is odd. Label the
vertices along the cycle x1;x2,./>. For 1 < i < k, let represent the set of
vertices pendant to the vertex xt, where it is possible that Vj = 0. By Lemma
2.2, in V(T) a vertex x can have indegree at most 1 and at most one vertex in
) can have nonzero outdegree. Therefore, all the arcs in V(T) on the
cycle must be oriented either clockwise or counterclockwise and the remaining
arcs must be oriented toward each pendant set. So, without loss of generality
18
assume that V(T) is as depicted in Figure 2.4.
Figure 2.4. One of two possible orientations for the domination
digraph of an odd spiked cycle.
We proceed to show that T is a spiked cycle tournament. We begin
by showing that the set of vertices induce a subtournament isomorphic to
Uk By Lemma 2.6, we have that C'k is a subgraph of the domination graph
of the subtournament induced by the set of vertices {x\, X2, Xk} Then by
Theorem 1.1, the domination graph of the subtournament T({x\, x^,..., Xk})
must be C'k. So, we may conclude by Theorem 2.4, that the subtournament
induced by the set of vertices {.r t...,Xk} is isomorphic to Uk
Next we show that the arcs in T between the pendant sets and the
vertices on the cycle must be as prescribed by Figure 2.3. For the following
we will take i + 1 to mean (i mod k) + 1. Now suppose that (xi,xj) A(T).
19
If Vi = Vj = 0, there is nothing to prove. If \\ 4 0 and Vj 4 0, let w Â£
Vi and z Â£ Vj. Since Xj and z form a dominant pair and (xi,Xj) is an arc, we
have (z,Xi) Â£ A(T). Then since tv and Xi form a dominant pair and (z,x.j) is
an arc, (tv, z) Â£ A(T). But then since z and Xj form a dominant pair and (tv, z)
is an arc, (xj,tv) Â£ A(T). If Vj 4 0 and Vj = 0, let tv Â£ Vj. Since (xi,xj) is an
arc and Xj and Xj+1 form a dominant pair, it follows that (xj+i,Xi) Â£ A(T).
Then since Xi and tv form a dominant pair and (xj+i,Xi) is an arc, we have
that (w,Xj+1) Â£ A(T). But then since xj and Xj+1 form a dominant pair
and (w,Xj+i) is an arc, (Xj,w) Â£ A(T), as desired. Finally assume Vj = 0
and Vj 4 0. Let z Â£ Vj be arbitrary. Since z and Xj form a dominant pair
and (xi,Xj) is an arc, (z,Xj) Â£ A(T). Therefore, it follows that the arcs in T
between the pendant sets and the vertices on the cycle are as prescribed in
Figure 2.3.
Finally we show that the arcs within each pendant set may be oriented
arbitrarily. Since Xi beats every vertex in Vj, no two vertices in Vj can form
a dominant pair in T, regardless of the structure of the arcs within Vj. Thus,
since no two vertices in Vj are adjacent in dom(T), the arcs within Vj can be
oriented arbitrarily.
For the converse, suppose that T is a spiked cycle tournament. We
will proceed by showing that dom(T) is an oddspiked cycle. Without loss of
generality assume that '/'({.r t..., Xk}) = 14
20
First we show that [a;*, xi+\} e dom(T) for all i, with 1 < i < A: 1, and
that [xk,xi] e dom(T). Since /'( {.rt... a;*,}) = Uk, we know by Theorem
2.4 that [re*,:Cj+i], for 1 < i < k 1, and [xk,xi] form dominant pairs in the
subtournament induced by the set of vertices {.r t... ,Xk} Thus, the pairs
{.r,. x;. i}. for 1 < i < k 1, and {xu,x\} beat every vertex in {.ri. ..., Xk}
Therefore, in order to show that these pairs form dominant pairs in T, it suffices
to show that they also beat every vertex in Vj, for all j. Consider the pair of
vertices Xi and a^+i, for 1 < i < k 1. Let z V, with 1 < l < k. We will
show that z is beaten by either Xi or xi+\. If l = i,i + 1 there is nothing to
prove. So assume that l < i. If / is odd, then since /'({./1. ay.... ,Xk}) = Uk,
we have that xi beats all vertices Xj for j > l and j even. Since i is either odd
or even, xi beats either a^ or xi+\. Then by Figure 2.3, it follows that in either
case if xi beats Xi, then x% beats z and if x\ beats Xi+\, then xi+\ beats z. If
l is even, then by a similar argument either a^ beats z or xi+i beats z. Next
assume that l > i + 1. If / is odd, then again since 7'( {a j. ay.... ,Xk}) = Uk,
it follows that xi beats Xj for j < l and j odd. Since i must either be even
or odd, we have that xi beats either xi or Xi+\. Again by Figure 2.3, in either
case if xi beats xi, then xi beats z and if xi beats Xi+\, then xi+\ beats z. If
l is even, then by a similar argument either a^ beats z or xi+i beats z. Thus,
Xi and Xi+\ form a dominant pair in T for all i, with 1 < 7 < A; 1. A similar
argument is used to show that [xk,xi] e dom(T).
21
Next let z Â£ Vi be arbitrary. We will show that [z,Xj] Â£ dom(T).
Since T is a spiked cycle tournament, we have by Figure 2.3 that any vertex
w Â£ V(T)\Vi that beats is beaten by Thus, since xt beats every vertex
in we may conclude that [z,xi\ Â£ dom(T).
Lastly, we need to show that no other pair of vertices forms a dominant
pair. We have shown that the set of vertices {.rt... ,Xk} induces an odd
cycle in the domination graph of T. If there exists another pair of vertices that
forms a dominant pair, then this dominant pair would create a second cycle in
dom(T). But Theorem 1.1 tells us that the domination graph of a tournament
can have at most one cycle. Thus, there cannot exist any other dominant pairs.
Therefore, dom(T) is an oddspiked cycle.
Recall that a caterpillar is a tree such that the removal of all the
vertices of degree one results in a path, which we refer to as the spine. As
was pointed out earlier, the extreme ends of the spine have at least one vertex
pendant to each of them in the caterpillar. Now Theorem 2.1 states that
a caterpillar G is the connected domination graph of a tournament if and
only if G has three or more vertices pendant to at least one end of the spine.
Therefore, in order to characterize those tournaments that have a caterpillar
as their domination graph, we only need to consider those caterpillars which
have three or more vertices pendant to at least one end of the spine. We will
say that such caterpillars have a triple end. In the remainder of this section,
22
we will determine every tournament that has a caterpillar with a triple end as
its domination graph.
Let G be a caterpillar with a triple end. By Theorem 2.1, we may
conclude that G is the domination graph of some tournament. So let T be a
tournament such that doni{T) = G. If we consider V(T), we have by Lemma
2.2 that in the domination digraph of T a vertex can have indegree at most
one and can have at most one outneighbor with outneighbors. Thus, we can
see that there are only two possible orientations up to isomorphism for the
domination digraph of T. The two orientations arise from the orientation of
the arc between v and x and are depicted in Figure 2.5. Regardless of the
orientation of T>(T), one aspect of the structure of V(T) is fixed, as stated in
the next result.
Figure 2.5. This depicts the two possible orientations for the
domination digraph of a nonstellar caterpillar with a triple end.
Lemma 2.8 (Fisher, et al., [19]) Let G be the union of k caterpillars, with
k > 1 and assume that G is the domination graph of a tournament T. Assume
H is com,poneMt of G. Them removing all vert,ices with outdegree 0 from, the
subdigraph ofV(T) on V(H) results in a directed path.
X
V
23
Assume a caterpillar G is the domination graph of a tournament T.
Define the directed spine of V(T) to be the directed path that results when
all vertices of outdegree 0 are removed from V(T). We will use the directed
spine of V(T) to label the vertices of G as follows: Let xi,x2, ,xk represent
the vertices of G that correspond to the vertices on the directed spine of V(T).
Also let Vi represent the set of vertices in G that have outdegree 0 in V(T)
and that are beaten by Xi in V(T). Figure 2.6 depicts this labeling along with
V(T). Note that the set V\ may be empty if x\ corresponds to a pendant vertex
in G that beats an end vertex on the spine of G in V(T). See Figure 2.5.
Figure 2.6. A labeling of the domination digraph of a nonstellar
caterpillar with a triple end.
On a side note, if a forest of caterpillars G is the domination graph
of a tournament and H is a component of G, then we define the directed spine
of the subdigraph of V(T) on V(H) analogously to the above definition. In
addition, we also label the vertices of H as we describe above, i.e., by using
the directed spine of the subdigraph of V(T) on V(H).
24
Now it will be useful to properly color the caterpillars G under con
sideration with two colors, red and blue. The next result, of Fisher, et al,
determines the remaining arcs in Figure 2.6, except for those within the sets
hi
Lemma 2.9 (Fisher, et al., [19]) Let G be the union of k caterpillars, with
k > 1, and assume that G is the domination graph of a tournament T. Assume
H is a com,poneMt of G and is properly 2colored (such a coloring exist and is
unique for a caterpillar). If the subdigraph ofV(T) on V(H) is as depicted in
Figure 2.6, then the following arcs must be in T(H):
1. Arcs that are not within a set \), are oriented to the right between vertices
of different colors and to the left between vertices of the same color.
2. Arcs within each set \), for i f k, may be oriented arbitrarily.
Let rc denote the set of tournaments T with the following properties.
The vertex set of T can be partitioned into the sets {.r t.......//,}. \ i. \ .
and T4, with k even and at least 2. The arcs in T are as follows:
The subtournament T({x\, x^,..., Xk}) Uk
For all i, arcs are oriented from to vertices in V^.
The arcs within each \f with 1 < i < k 1, are oriented arbitrarily.
The arcs within yield a subtournament T(yf) without a transmitter.
Note that this implies that Vk must have at least 3 vertices, because
any tournament with fewer than 3 vertices always has a transmitter.
25
The remaining arcs in T are as in Figure 2.3. In other words, if re*
beats Xj, then arcs are oriented from vertices in \\ to vertices in V},
from Xj to vertices in Vj, and from vertices in Vj to Xj.
If a tournament T belongs to I',, we will say that T is a caterpillar tourna
ment. These tournaments were used by Fisher, et al., in [19] to show that
any caterpillar with a triple end is the domination graph of some tournament.
We will now show that essentially these are the only tournaments that have a
caterpillars (with a triple end) as their domination graphs.
Theorem 2.10 Let T be a ntoumament with n > 4. Then the domination
graph of T is a caterpillar with a triple end if and only if T is a caterpillar
tournament or a tournament with a transmitter.
Proof: Let T be a tournament for which dom(T) is a caterpillar with a triple
end. If dom(T) is a star, then by Theorem 2.3, we may conclude that T is
either a caterpillar tournament or a tournament with a transmitter. Therefore,
assume that dom(T) is a nonstellar caterpillar. Now Lemma 2.8 provides the
existence of the directed spine in V(T). Thus, we may assume without loss of
generality that V(T) is as depicted in Figure 2.6. In addition, assume that the
vertices of G are labeled as in Figure 2.6. Properly color G with the colors red
and blue such that X\ is assigned the color red. We proceed by showing that
T is a caterpillar tournament.
First we show that k must be even. Suppose that k is odd. Note
26
that Xi and Xk are both assigned the color red. Then a consequence of Lemma
2.9 is that x\ beats all the blue vertices to the right and Xk beats all the red
vertices to the left. Thus, whether or not the triple end exists at x\ or at
Xk, we have that X\ and Xk form a dominant pair in T, a contradiction since
[x\,Xk} dom(T). Therefore, k must be even.
Next we show that G must have a triple end at Xk and that T(Ffe)
must induce a subtournament without a transmitter. So assume that \Vk\ < 2.
Let v be the vertex in V* such that v is a transmitter in the subtournament
T(Vk). Such a vertex exists for all tournaments with at most 2 vertices. Since
k is even, Xk is colored blue and so we have that v is colored red. Then it
follows by Lemma 2.9 that x\ beats all vertices to the right that are colored
blue and v beats all vertices to the left that are colored red. Note that every
vertex in V* is beaten by v, since v is a transmitter in T(Vk). In addition, note
that every vertex in V\ is beaten by x\. Therefore, it follows that X\ and v
form a dominant pair, a contradiction since [xi,h] 0 dom(T). Therefore, we
may conclude that \\%\ must be at least 3. In addition, by the same argument
T(Vk) must induce a subtournament without a transmitter.
Finally, with the proper coloring assigned to the vertices of G, Lemma
2.9 determines that T is a caterpillar tournament.
For the converse, let T be a ntournament with n > 4. First assume
that T has a transmitter. Then by Theorem 2.3, it follows that dom(T) is a
27
caterpillar with a triple end. In particular, dom(T) is a star with at least three
pendant vertices. Therefore, we may assume that T is a caterpillar tournament
on n > 4 vertices. Without loss of generality assume that T({x i,x2,..., xk}) =
Uk. Note that k must be even. We proceed by showing that dom(T) is a
caterpillar with a triple end.
First we show that [xi,xi+1] E dom(T), for all i with 1 < i < k 1.
Consider the pair of vertices and xi+i for some i E {1, 2,..., A: 1}. First
note that every vertex in \) is beaten by Xi and every vertex in V*+i is beaten
by xi+\. Thus to show that [xi,xi+1] E dom(T), we will show that for all
xi E {.r i. .....//,}. with l ^ %, % + 1, the vertex x\ together with every vertex
in Vi is beaten by either x% or Xi+\. So let xi E {.r t... ,xk}, with l ^ i,i + l.
Assume that l < i. If A is odd, then since '/'({.r t... ,xk}) = Uk, we have
that xi beats all vertices Xj for j > l and j even, and is beaten by all vertices xm
for m > l and m odd. Thus, since i must be either odd or even, xi beats exactly
one of Xi or xi+\. In addition, since T is a caterpillar tournament, we have by
Figure 2.3 that whichever vertex xi beats from Xi and xi+i, that same vertex
beats every vertex in \). Therefore, in either case whether xi beats Xi or Xi+\,
it follows that xi and every vertex in Vi is beaten by either xi or Xi+\. Similarly,
if l is even, then xi and every vertex in \) is beaten by either Xi or xi+\. Next
assume that l > i +1. If / is odd, then since 7'( {.rt........//,}) = ( ),. it follows
that xi beats all vertices Xj, for j < l and j odd, and is beaten by all vertices
28
xm, for m < l and m even. Thus, since % must be either odd or even, xi beats
exactly one of Xi or Xi+\. In addition, since T is a caterpillar tournament, we
have by Figure 2.3 that whichever vertex xi beats from xi and Xi+\, that same
vertex beats every vertex in \). Therefore, in either case whether xi beats Xi
or Xi+1, we may conclude that xi and every vertex in V is beaten by either xi
or xi+\. Similarly, if l is even, then xi and every vertex in Vi is beaten by either
Xi or xi+\. Therefore, since i was arbitrary in {l,2,...,/r 1}, it follows that
Xi and Xi+\ form a dominant pair in T, for all i with 1 < i < k 1.
Next let z E Vi be arbitrary. We will show that [z,x^\ E dom(T).
Since T is a caterpillar tournament, we have by Figure 2.3 that any vertex
w E V(T) Vi that beats Xi is beaten by Thus, since xt beats every vertex
in Vi, it follows that [z,x^\ E dom(T). Therefore, since \Vk\ is at least 3, we
may conclude that a caterpillar with a triple end is a subgraph of dom(T). See
Figure 2.7.
V,
vq
Figure 2.7. A subgraph of the domination graph of a caterpillar
tournament.
29
To show that dom(T) is a caterpillar with a triple end, it suffices to
show that no other pair of vertices can form a dominant pair in T. Notice that
we have shown the existence of n 1 dominant pairs in T. By Theorem 1.1,
we have that the domination graph of any tournament on n vertices can have
at most n dominant pairs. Thus, there can exist at most one more dominant
pair. If there exists another dominant pair in T, then by Theorem 1.1 it must
be one such that the domination graph is an oddspiked cycle. Note that there
are four possibilities. These are
(1) [xi,v], for a vertex v E 14, if 14 is nonempty,
(2) [tv, Xk], for a vertex tv E Vi, if 14 is nonempty,
(3) [x2,Xk], if 14 is empty, or
(4) [xi,v], for a vertex v E 14, if \ \ is empty.
The above are the only possibilities because these are the only possible edges
that will create an oddspiked cycle. We proceed by showing that none of
these can occur. First assume that 14 is nonempty. Since X\ beats every
vertex in 14 and beats Xk, we have that [w,Xk] dom(T), for any tv E 14.
Also since T(14) induces a subtournament without a transmitter, it follows
that for every vertex v E 14 there exists a vertex v' E 14 such that v' beats
v. Thus, since every vertex in 14 beats X\, we conclude that [xi,v] 0 dom(T),
for any v E 14. Next assume that 14 is empty. Since x\ beats both x2 and Xk,
it follows that [x2,xk] 0 dom(T). Also since T(14) induces a subtournament
30
without a transmitter, then for every vertex v \ there exists a vertex v' e \),
such that v' beats v. Thus, since every vertex in beats aq, it follows that
[x\,v] 0 dom(T), for any v V*. Therefore, dom(T) is a caterpillar with a
triple end.
Observe that the domination graph of a caterpillar tournament has
an even spine, if Vi ^ 0 and an odd spine, if Vi = 0.
On a final note, if we are given a connected graph G that is known
to be the domination graph of a tournament, then we can use Theorems 2.3,
2.4, 2.7 and 2.10 to construct a tournament that has G as its domination
graph. But note that this tournament need not be unique. For example, using
Theorem 2.3, we can construct the two nonisomorphic tournaments in Figure
2.8 that have Kit3 as their domination graph.
Figure 2.8. Two nonisomorphic tournaments on four vertices
that have Kit3 as their domination graph.
Therefore, it would be interesting to determine all connected graphs that are
the domination graphs of unique tournaments. We leave this final problem as
a possible avenue in which the research on this topic can be continued.
31
3. The DominationCompliance Graph of a
Tournament
3.1 Introduction
In this chapter, we introduce and study a generalization of the dom
ination graph, the dominationcompliance graph of a tournament. Vertices x
and y are a compliant pair in a tournament T if every other vertex z ^ x,y
beats either x or y, i.e., x and y are a compliant pair if I(x) U I(y) U {x, y} =
V(T) or equivalently if O(x) fi 0(y) = 0. The compliance graph com(T) of
a tournament T is the graph on the same vertex set as T with edges between
vertices that form a compliant pair. It is easy to see that the domination graph
is related to the compliance graph in that com(T) = dom(T), where T is the
reversal of T. This relationship has the consequence that every graph that is
a domination graph is also a compliance graph.
The dominationcompliance graph DC(T) of a tournament T
is the graph on the same vertex set as T with edges between vertices which
form either a dominant pair or a compliant pair. Observe that DC(T) =
dom(T) U com(T).
A graph which is closely related to the dominationcompliance graph
is the competition/resource graph. Recall that the competition graph C(T)
32
Figure 3.1. A 7tournament and its dominationcompliance graph.
of a tournament T is the graph on the same vertex set as T in which ver
tices x and y are adjacent if and only if there exists a vertex z ^ x,y such
that (x,z) and (y,z) E A(T). Also recall that the resource graph R(T) of
tournament T is the graph on the same vertex set as T in which vertices
x and y are adjacent if and only if there exist a vertex z ^ x,y such that
(z,x) and (z,y) E A(T). It is not hard to see that the domination graph of
a tournament T is the complement of the resource graph of T and that the
compliance graph of a tournament T is the complement of the competition
graph of T. This is true only when the digraph is a tournament. As a re
sult of this relationship, competition and resource graphs of tournaments have
been characterized. See Fisher, et ah, [17, 18, 19] for more about the compe
tition and resource graphs of tournaments. The competition/resource graph
of a tournament is the graph on the same vertex set as T in which vertices
x and y are adjacent if and only if x and y are adjacent in both the com
petition graph and the resource graph. Observe that CR(T) = C(T) fi R(T).
33
Competition/resource graphs have been studied for arbitrary digraphs, but not
specifically for tournaments. See [23, 27, 39].
The next result illustrates the relationship between the domination
compliance graph and the competition/resource graph. Let ()c represent the
complement operation.
Lemma 3.1 (Jimenez and Lundgren [22]) If T is a tournament, then
(CR(T)Y = DC(T).
Proof: By DeMorgans Theorem, (CR(Tj)c = (C(T)f]R(Tj)c
= (C(T))C U (R(T))C
= com(T) U dom(T)
= DC(T). m
From Lemma 3.1, we see that results for the dominationcompliance
graph of a tournament correspond to results for the competition/resource graph
of a tournament. However, since the dominationcompliance graph of a tourna
ment generally has fewer edges than the competition/resource graph, it is more
convenient to state and prove results on the dominationcompliance graph of a
tournament. In addition, doni{T)C\coni{T), also known as the mixed pair graph
of a tournament, has been studied and characterized in [6] by Bowser, Cable
and Lundgren. Therefore, since the domination graph, compliance graph, com
petition graph, resource graph and the mixed pair graph have all been studied
34
for tournaments, the only items remaining to be studied are the domination
compliance graph of tournaments and the competition/resource graphs of tour
naments. In this chapter, we begin an examination of these last two items.
We will exhibit an upper bound on the number of edges in the domination
compliance graph of a tournament. In addition, we will give characterizations
for the dominationcompliance graphs of two specific classes of tournaments.
3.2 DominationCompliance Graph of Tournaments
Which, graphs can be the dominationcompliance graphs of tourna
ments? We will start to partially answer this question by stating and proving an
upper bound on the maximum number of edges in the dominationcompliance
graph. This, in turn, will lead to forbidden subgraph results.
Lemma 3.2 Let T be a regular tournament and x,y E V(T). Then [x,y] E
dom(T) if and only if [x,y] E com(T).
Proof: Let T be a regular ntournament and x. y E V(T). Suppose that x and
y form a dominant pair. Then since T is a regular tournament, it follows by
Lemma 2.5 that O(x) fi 0(y) = 0. Thus, [x,y] E com(T).
Next assume that x and y form a compliant pair in T and that x beats
y. Then since [x,y\ E com(T), we have that \I(x)Ul(y)\ = n 1. Thus, since T
is regular, \I(x)nl(y)\ = \I(x)\ + \I(y)\^\I(x)Ul(y)\ = n ^ ^ +n ^ (re1) =
0. Therefore, it follows that I(x) fi I(y) = 0 and so [x,y] E dom(T).
35
Recall that Un is the tournament on vertex set X\, x2,..., xn with
(.Xi,Xj) E A(Un) if i j is either odd and negative or even and positive. Also
recall that Un is a regular tournament when n is odd. Let P* be the graph
with vertices x\, x2,..., xn and edges [x\, xf\, [x%, Â£3], , [xni, x\, [x\, xn^i]
and [x2,xn]. See Figure 3.2. Note that for n = 1,2,3, the graph P* is the
path on one, two, and three vertices, respectively.
Figure 3.2. The graph Pfu.
Lemma 3.3 (Jimenez and Lundgren [22]) If T
Pf if n is even
Cn if n is odd.
= Un, then
DC(T)
Proof: Let T be an ntournament isomorphic to Un, n > 1. First assume that
n is odd. Since Un is a regular tournament, Theorem 2.4 and Lemma 3.2 imply
that DC(T) 9* Cn.
Next assume n is even. The result is trivial if n = 2, so assume that
n > 4. First we show that [xi,Xi+1] E IX'( !'). for all 1 < < A: 1. Let
xi E V(T), with l ^ i,i + 1. Assume that l < i. If / is odd, then xi is beaten
by all vertices Xj with j > l and j odd. Since i is either odd or even, it follows
36
that either re* or xi+\ beats X(. Similarly, if l is even, then xi is beaten by
either xi or Xi+\. Next assume that l > i + 1. If / is odd, then xi is beaten
by all vertices Xj with j < l and j even. Since i is either odd or even, then
either Xi or xi+i beats X[. Similarly, if l is even, then xi is beaten by either
Xi or Xi+\. Therefore, it follows that Xi and Xi+\ form a dominant pair in T.
Since the domination graph is contained in the dominationcompliance graph,
[x,i,xi+1] E DC(T), for 1 < % < k 1.
Next, we show that [x\,xni} and [x2,xn] E DC(T). Since x\ beats
Xj, for j even, and xn^i beats Xj, for j < n 1 and j odd, it follows that
[a;i,a;n_i] e dom(T) C DC(T). Similarly, since xn is beaten by Xj, for j odd,
and X2 is beaten by Xj, for j > 2 and j even, it follows that [x2, xn] e com(T) C
DC(T).
Finally, we need to show that no other pair of vertices forms an edge
in DC(T). Assume that j ^ i + 1, i 1 and i,j E {2, 3, ...n 1}. We will show
that Xi and Xj are not adjacent in DC(T) If i and j are odd, then Xi and Xj
beat X\ and are beaten by x2 If i and j are even, then Xi and Xj beat xn^i
and are beaten by x. If i and j are of opposite parity, then assume without
loss of generality that i < j. Since \i j\ > 3, we conclude that Xi and Xj beat
xi+i and are beaten by xi+2
Next assume that i = 1, j >2 and j ^ n 1. We will show that x\
and Xj are not adjacent in DC(T) If j is even, then x\ and Xj beat x2 and
37
are beaten by x?J. If j is odd, then x\ and Xj beat xn and are beaten by xn_i.
Similarly, xn is not adjacent to xj for j < n 1 and j ^ 2.
The converse of this last lemma is not true. For example, consider
the tournament on seven vertices and its corresponding dominationcompliance
graph in Figure 3.3.
Figure 3.3. DC(T) is C7, but T is not isomorphic to U7.
The next result is analogous to Lemma 2.6.
Lemma 3.4 (Jimenez and Lundgren [22]) Let R be an induced sub
digraph of a digraph D. Then the induced subgraph of DC(D) on the vertices
of R is a subgraph of DC(R).
Proof: Let x. y e V(R) where [x,y] e DC(D). Then either [x,y] e dom(D) or
[x,y] e com(D). Since V(R) C V(D), we have that either [x,y] e dom(R) or
[x,y] e com(R). Thus, [x,y] is an edge in DC(R).
Theorem 2.7 from Chapter 2 will prove useful in the verification of
the next result.
38
Lemma 3.5 (Jimenez and Lundgren [22]) Let T be a tournament whose
domination graph is an oddspiked cycle. Assume that {.r t... ,Xk} are the
set of vertices on the cycle of dom{T). In addition, assume that Vj, for j =
1.2....k. is the set of vertices pendant to Xj in dom(T). Then the following
are the only possible edges in com(T).
i) Let v E Vj. Then [xi,v\ E com(T) if and only if d^v^(v)=0.
ii) Let v E Vj and tv E Vj. Then [v,w] E com(T) if and only if j = i +
1 (mod k) and dj,^v^(w) = 0 or j = i 1 (mod k) and dj,^(v) = 0.
Hi) [xi,Xj] E com(T) if and only if j = i + 1 (mod k) and Vi = 0 or j =
i 1 (mod k) and Vj = 0.
iv) Let v E Vj and assume i ^ j. Then [v,Xj] E com(T) if and only if
j = i + 2 (mod k) and Vi+i 0.
Proof: Let T be a tournament whose domination graph is an oddspiked cycle.
Then it follows by Theorem 2.7 that T must be a spiked cycle tournament. So
assume without loss of generality that '/'({.ri. ..., Xk}) = Uk Note that the
vertices Xi and the sets Vj are related by Figure 2.3. Therefore, since every
vertex in \) beats every vertex ,r( that beats Xi, we have that no pair of vertices
in Vj, for all i, can be an edge in com(T).
i) Let v E V^ We begin by showing that if there exists a vertex
z E V(T) that both Xi and v beat, then z must be an element of Vj. Assume
39
Â£ E 0(v)C\0(xi), for some 2 E F(T). First, 2: cannot be an element of Vj, with
j 4 i, because if xt beats 2, then since T is a spiked cycle tournament, it follows
from Figure 2.3 that 2 must beat v. Second, z cannot be any vertex xj, with
j 4 %, because if x,i beats Xj, then again since T is a spiked cycle tournament,
we have by Figure 2.3 that Xj beats v. Therefore, z must be in Vj. Thus,
<^T(vl)(v) = 0 ( i.e, v beats no vertex in ) if and only if 0(v) Cl 0(xi) = 0.
Therefore, we have that d^v^(v) = 0 is equivalent to 0(xj) fi 0(v) = 0 which
in turn is equivalent to [xi,v\ E com(T).
ii) Let v E Vj and w E Vj. First we show that iij i + l {mod k),
then [v, w} 0 com(T). A consequence of Theorem 2.4 is that the only dominant
pairs in [4 are [xi, xi+\}, for 1 < i < k 1, and [^1,0;*]. Thus, if j ^ i + 1, i
1 (mod k), then there exist a vertex xi, l ^ %,j, in 7'( {.rt..., Xk} = Â£4 such
that Xi and Xj are beaten by X(. But then since T is a spiked cycle tournament
and xi beats both Xi and Xj, we have by Figure 2.3 that both v and tv beat xi
and so it is not possible for v and w to form a compliant pair. Therefore, we
may conclude that [i>, w] 0 com(T) for j ^ i + l,i 1 (mod k).
Now we show that [v,w] E com(T) if and only if j = i + 1 (mod k)
and dj,^{w) = 0 or j = i 1 (mod k) and d^v^{v) = 0. Note that it suffices
to show that it is true for exactly one of these last two conditions. So without
loss of generality assume that j = i + 1 (mod k). Let 2 E 0{v) f1 0{w) for
40
some z e F(T). First, z cannot be in \\ with l ^ j, because if v dominates
z, then by Figure 2.3 it follows that z beat re*. Then since z beats Xi and
[xi,Xj\ e dom(T), we have that Xj beats z. But then by Figure 2.3, we may
conclude that z beats w. Second, z cannot be any vertex xi with l ^ %,j,
because if both v and w beat z, then by Figure 2.3 we have that xi beats
both Xi and Xj, a contradiction since [xi,Xj] dom(T). Thus, it follows that
z must be an element of Vj. Note that since Xi beats Xj, we have by Figure
2.3 that every vertex in \) beats every vertex in \). Therefore, since v beats
every vertex in Vj, we may conclude that dX (w) = 0 (i.e, w beats no vertex
in Vj) if and only if 0(v) fi 0(w) = 0. From these observations, we have
that [v,w] com(T) is equivalent to 0{v) fi O(w) = 0 which is equivalent to
j = i + 1 {mod k) and dX. (w) = 0orj = i^l (mod k) and dX. (i>) = 0.
in) First we show that if j ^ i + l,i 1 (mod k), then [xi,Xj] 0
com(T). A consequence of Theorem 2.4 is that the only dominant pairs in
/'({./1. .....//,}) = Uk are [xi,Xi+1], with 1 < i < k 1, and [^1,0;*]. In
addition, Lemma 3.2 implies that in a regular tournament a pair of vertices
forms a dominant pair if and only if they form a compliant pair. Thus, since
Uk is a regular tournament, we may conclude that the only compliant pairs in
Uk are [xi,xi+1] with 1 < i < k 1 and Thus, if a pair of vertices
in {.r 1. ... ,Xk} cannot form a compliant pair in 7( {.r 1. ... ,Xk}), they
41
certainly cannot form a compliant pair in T. Therefore, [xi,Xj] 0 com(T)
when j ^ i + 1, i 1 {mod k).
Next we show that [x^, Xj\ e com(T) if and only if j = i + 1 (mod k)
and Vi = 0 or j = i 1 (mod k) and Vj = 0. Note that it suffices to show that
it is true for exactly one of these two conditions. So without loss of generality
assume that j = i + 1 (mod k). Let z O(xi) fl O(xj). First, z cannot be
in V[, with l ^ %, because if x% beats z, then by Figure 2.3 it follows that xi
beats xi. Then since [xi,Xj] dom(T), we have that Xj beats X(. But then
by Figure 2.3, we can see that z beats Xj. Second, z cannot be any vertex
xi on the cycle, because Xi and Xj are compliant pair in the subtournament
7'( {.r i. ... ,Xk}) = Uk and so it is not possible for both of them to beat a
vertex in {.r t... ,Xk}. Therefore, z must be in Vj. Note that since Xi and
Xj form a dominant pair in T and j = i + 1 (mod k), we can see by Figure
2.3 that Xj beats every vertex in Vj. Thus, O(xi) fl O(xj) = 0 if and only if
Vj = 0. Therefore, we may conclude that [xi,Xj\ e com(T) is equivalent to
0(xj) fl 0{xj) = 0 which is equivalent to j = i + 1 (mod k) and Vj = 0 or
j = i 1 (mod k) and Vj = 0.
iv) Let v e Vj and j ^ i,i + 2 (mod k). We begin by showing that
v and Xj cannot be a compliant pair. This will be accomplished by showing
that if Xi beats Xj, then both v and Xj beat Xj2 and if Xj beats Xi, then both
42
v and Xj beat Xj+\. For the following, all arithmetic is done modulo k.
Assume that x, beats Xjt. Note that j 2 ^ i since j ^ i + 2 (mod k).
Then since Xj1 and Xj form a compliant pair in '/'( {.rt, Xk}), it follows
that Xj and Xj1 cannot both beat Xi. Thus, Xj1 is beaten by re*. Then
since [xj2,Xj\] dom(T), we have that Xj2 beats Xj. But then we can
see by Figure 2.3 that v beats Xj_2 I11 addition, since Xj2 beats Xj1 and
[xj\,Xj] dom(T), we may conclude that Xj beats Xj2. Therefore, both v
and Xj beat Xj2 and so they cannot be a compliant pair in T.
Next assume that Xi beats xr Note that j l {mod k) since x^i
beats Xi. Thus, since [xj,Xj+1] e dom(T), we have that Xj+1 beats Xj. Then
by Figure 2.3 it follows that v beats Xj+\. But Xj also beats Xj+1 and so v and
Xj cannot be a compliant pair in T.
We finish this proof by showing that [v,Xj] com(T) if and only if
j = i + 2 (mod k) and Vi+i = 0. So assume that j = i + 2 (mod k). Note that
j 1 = i + 1 (mod k). Thus, [xi,Xji] e dom(T). Let z e 0{v) fi 0(xj1).
We will show that z must be in Vi+\. First, z cannot be in \). with l ^ i + 1,
because if Xj beats z, then it follows by Figure 2.3 that xi beats Xj. Then since
[xj\,Xj] dom(T), we have that Xj1 beats X(. Then since Xi and Xj1 are a
compliant pair in Y'( {.r 1. ... ,Xk}), we may conclude that xi must beat Xi.
But then by Figure 2.3 it follows that v beats xi and from the same figure z
43
beats v. Second, z cannot be a vertex xi, with l ^ i,j, because if Xj beats X[,
then since xji and xj form a compliant pair in '/'( {.r t... ,Xk}), we have
that xi must beat Xj1. Then since [xi,Xjf\ e dom(T), it follows that Xi beats
X[. But then by Figure 2.3 we may conclude that xi beats v. Therefore, z must
be in V*+i. Note that since Xi beats xji and xji beats Xj, we have by Figure
2.3 that both v and Xj beat every vertex in V)_i. Therefore, O(xj) fl 0(v) = 0
if and only if Vi+i 0. And so we may conclude that [v,xf\ com(T) is
equivalent to 0(xj) fl 0{v) = 0 which is equivalent to j = i + 2 {mod k) and
Fi+2 = 0
Theorem 3.6 (Jimenez and Lundgren [22]) Let T be an ntournament.
The maximum number of edges in DC(T) is 2(n 1) and this bound is the best
possible for n > 4.
Proof: Suppose \E(DC(T))\ > 2(n 1). A consequence of Theorem 1.1 is
that the domination graph of a tournament with n vertices can have at most
n edges. Thus, since com(T) = dom(T), we can see that the compliance
graph of a tournament with n vertices can have at most n edges. Now since
DC{T) = dom(T) U com(T) and \E(DC(T))\ > 2(n 1), then at least one
of dom(T) or com(T) must have n edges. Since com(T) = dom(T), we may
assume without loss of generality that \E(dom(T))\ = n. Then the only way
that the dominationcompliance graph can have more than 2(n 1) edges is if
we have one of the following configurations:
44
(1) \E(dom(T)) \ = n \E(com(T)) \ = n, and \E(dom(T) fi com(Tj)\ = 0.
(2) \E(dom(T)) \ = n \E(com(T)) \ = n, and \E(dom(T) fi com(Tj)\ = 1.
(3) \E(dom(T)) \ = n \E(com(T)) \ = n 1, and
E(dom(T) fl com(Tj) \ = 0.
Now since \E(dom(T))\ = n, then dom(T) must be an oddspiked cycle. If
dom(T) is an odd cycle, then it follows by Theorem 2.4 that T must be iso
morphic to l with n odd. But since Un is a regular tournament when n is
odd, we may conclude by Lemma 3.2 that DC(T) = doni{T) = com(T), which
does not have more than 2(n 1) edges. Thus, if the above configurations exist,
then dom(T) must be an oddspiked cycle with at least one pendant vertex.
Case 1. Suppose the existence of Configuration 1 or Configuration 3.
Since \E{doni{T))\ = n, we have by the above observation that dom(T) must
be an oddspiked cycle with at least one pendant vertex. Thus, by Theorem
2.7, we have that T must be a spiked cycle tournament. Let x\, x2, , rep
resent the vertices on the cycle of dom(T) and be the set of vertices pendant
at Xi. Without loss of generality assume that '/'({.rt... ,Xk}) = UNow
since E(dom(T) C\com(T)) \ = 0, no edges of the form [xi,Xi+1] in dom(T) can
be edges in com(T). By iv) of Lemma 3.5, this will hold true if and only if
Vi ^ 0. Thus, it follows that for all i, the set is nonempty. In addition, no
edges of the form for v Vi, can be edges in com(T). By i) of Lemma
3.5, this will hold true if and only if no vertex in Vt has outdegree 0 in T(Vj).
45
But now since every pendant set must be nonempty, it follows by iv) of Lemma
3.5 that no vertex in {.rt... ,Xk} can form an edge with any other vertex
of T in com(T). Thus, {.r t..., Xk} is an independent set in com(T). Then
since com(T) = dom(T), it follows by Theorem 1.1 that com(T) must be an
oddspiked cycle with at least k isolated vertices or a forest of caterpillars with
at least k isolated vertices. In either case, com(T) can have at most n k
edges. Therefore, since k must be at least three, it follows that com(T) can
have at most n 3 edges, contrary to our assumption that com(T) has either
n edges (Configuration 1) or n 1 edges (Configuration 3). Hence, we may
conclude that Configuration 1 and 3 cannot exist.
Case 2. Suppose the existence of Configuration 2. Since \E(dom(T))\
= n, we may conclude by the above observations that dom(T) is an oddspiked
cycle with at least one pendant vertex. So assume T to be as in Case 1. Now
since \E(dom(T) fl com(T))\ = 1, then we must have that exactly one of the
edges of the form [xi,xi+i} or [z, Xi], where z V*, must be in com(T).
First suppose [xi,xi+1], for some i, is an edge in com(T). Then by
Hi) of Lemma 3.5, we have that V* = 0. Now since \E(dom(T) fi com(T))\ = 1,
no other edges of the form [xj,xj+1], with j ^ i, in dom(T) can be edges in
com(T). By iv) of Lemma 3.5, this will hold true if and only if Vj ^ 0. Thus,
it follows that for all j ^ i, Vj is nonempty. In addition, no edges of the form
[u),Xj\, for tv e Vj, can be edges in com(T). By i) of Lemma 3.5, this will
46
hold true if and only if no vertex in Vj has outdegree 0 in T(Vj). But now
since every pendant set, other than Vj, must be nonempty, it follows by iv)
of Lemma 3.5 that no vertex in {.rt..., ^i+i} can form an edge
with any other vertex of T in com(T). Thus, {.rt..., Xi+i} is an
independent set in com(T). But then since com(T) = dom(T), it follows by
Theorem 1.1 that com(T) must be an oddspiked cycle with at least k 2
isolated vertices or a forest of caterpillars with at least k 2 isolated vertices.
In either case, com(T) can have at most n (k 2) edges. Therefore, since k
must be at least three, it follows that com(T) can have at most n 1 edges,
contrary to our assumption that com(T) has n edges.
Next suppose that [o,x,j\, where v Vj, is an edge in com(T). By
i) of Lemma 3.5, we must have that v has outdegree 0 in the subtournament
T(Vj). Now since E(dom(T) fi com{T))\ = 1, no edges of the form [xj,Xj+1]
in dom(T) can be edges in com(T). By iv) of Lemma 3.5, this will hold true
if and only if Vj ^ 0. Thus, it follows that for all j, the set Vj is nonempty.
In addition, no other edges of the form [w,Xj], for w e Vj and j ^ %, can
be edges in com(T). By i) of Lemma 3.5, this will hold true if and only if
no vertex in Vj has outdegree 0 in T(V}), for j ^ i. But now since every
pendant set must be nonempty, it follows by iv) of Lemma 3.5 that no ver
tex in {.r i. can form an edge with any other vertex of T in
com(T). Thus, {a;i, x2, , is an independent set in com(T). But
47
then since com(T) = dom(T), we have by Theorem 1.1 that com(T) must be
an oddspiked cycle with at least k 1 isolated vertices or a forest of caterpil
lars with at least k 1 isolated vertices. In either case, com(T) can have at
most n (k 1) edges. Therefore, since k must be at least three, it follows
that com(T) can have at most n 2 edges, contrary to our assumption that
com(T) has n edges. Therefore, it follows that Configuration 2 cannot exist.
Since we have shown that none of the configurations we exhibited can
exist, it follows that it is not possible to have \E(DC(T)\ > 2(n 1). There
fore, DC(T) has at most 2(n 1) edges.
To show that this bound is best possible for n > 4, let T be the
tournament obtained from Un1 by adding a vertex xn with arcs (xi,xn), for
all i with 1 < i < n 1. For this tournament, n 1 edges are obtained from
dom(T) and n 1 edges are obtained from com(T). See Figure 3.4.
3.3 Consequences of the upper bound and forbidden
subgraphs
Theorem 3.6 gives the maximum number of edges in the domination
compliance graph of a tournament. As a result, it is straightforward to deduce
results about graph parameters for the dominationcompliance graph and the
competition/resource graph. In addition, we will also deduce some results
concerning forbidden subgraphs. Below are some examples.
48
Figure 3.4. Two tournaments on six and seven vertices that
have the maximum number of edges in DC(T).
49
Corollary 3.7 The minimum, number of edges in the competition/resource
graph of an ntournament is ( 2 ) ^ 2(n 1).
Let G be a graph. A subset of vertices of G forms a clique if there
are edges between every pair of vertices in the subset. We define the clique
number co(G) of G to be the maximum size of a clique in G. A subset of
vertices of G forms an independent set if there are no edges between any
two vertices in the subset. We define the independence number a(G) of
G to be the maximum size of an independent set in G. Clearly, a:(G) = cu(G)
where G is the complement of G.
Corollary 3.8 Let T be a tournament. Them the clique number of DC(T) is
at most ih
Proof: Let T be an ntournament. The result is trivial for n < 4, so assume
that n > 5. Suppose that /\ , is a subgraph of DC(T). Then by Lemma 3.4,
there must exist a 5tournament T' such that DC(T') = K5. But this cannot
possibly happen since the maximum possible number of edges in DC{T') is
8 and /\ , has ten edges. Therefore, /\ , is not a subgraph of DC(T), for any
ntournament T with n > 5.
Corollary 3.9 Let T be a tournament. Then the independence number of the
competition/resource graph ofT is at most 4
Theorem 3.10 Lf T is a tournament on six vertices, then iL3j3 is not a sub
graph of DC(T).
50
Theorem 3.10 can be verified by one of two methods. The first involves
enumerating all 56 nonisomorphic tournaments on six vertices and verifying
that /\ 3 3 is not a subgraph of DC(T). The second method is by proof and can
be found in Appendix A.
Corollary 3.11 Let T be a tournament. Then is not a subgraph of
DC(T).
Proof: Let T be an ntournament. The result is trivial if n < 5, so assume that
n > 6. If /\3.3 is a subgraph of DC(T), then by Lemma 3.4 there must exist
a tournament T' on six vertices such that /\3.3 is a subgraph of DC(T'). But
this contradicts Theorem 3.10. Therefore, A.*..* is not a subgraph of DC(T).
3.4 Characterization for reducible and regular tourna
ments
In this chapter, we have been investigating the dominationcompliance
graph of a tournament. Our goal of this investigation is to arrive at a result
that characterizes all graphs that are the dominationcompliance graphs of
tournaments. At this point, we have not been able to achieve such a result.
But if we restrict T to be either a reducible or regular tournament, we can get
such a result.
Recall that a tournament T is reducible if it is possible to partition its
51
vertex set into two nonempty sets A and B in such a way that every vertex in
A beats every vertex in B. By definition, reducible tournaments are precisely
those which are not strongly connected. A regular tournament is one in which
every vertex has the same outdegree. Note that if T is a regular tournament,
then T has an odd number of vertices. Let In be the graph with n isolated
vertices.
Lemma 3.12 Let T be a reducible tournament with a partition of its vertex
set into nonempty sets A and B such that every vertex in A beads every vertex
in B. IfT has no transmitter, then dom(T) = dom(T(A)) U I\B\.
Proof: Let T be a reducible tournament with a partition of its vertex set into
nonempty sets A and B such that every vertex in A beats every vertex in B.
Assume T has no transmitter. We will show that dom(T) = dom(A) U I\B\.
Clearly no pair of vertices in B can be a dominant pair in T since
A is nonempty. Since T does not have a transmitter, then for every vertex
x E V(T), we have d+(x) < n 1. Thus, no two vertices x E A and y E B
can be a dominant pair. Therefore, if [x, y\ E dom(T), then both x and y must
belong to A. Thus, by Lemma 3.4, we have [x,y\ E dom(T(A)). Conversely,
if [x,y] E dom(T(A)), then [x,y] E dom(T) since every vertex in A beats all
vertices in B. Therefore, dom(T) = dom(T(A)) U I\B\.
Corollary 3.13 Let T be a reducible tournament with a partition of its vertex
52
set into nonempty sets A and B such that every vertex in A beats every vertex
in B. IfT has no vertex with outdegree 0, then com(T) = com(T(B)) U/a
Lemma 3.14 If T is an ntournament with a vertex of outdegree 0, then
com(T) =
Proof: Let T be an ntournament that has a vertex x of outdegree 0. Note that
for any y E V(T) {a;}, we have that [x, y\ E com(T) since x is beaten by every
vertex in F(T)\{a;}. Thus, i4,ni C com(T). To show that com(T) = i.
it suffices to show that no other pair of vertices form a compliant pair. Let
y, z E V(T) {a;}. Since both y and z beat x, it follows that [y, z] 0 com(T).
Let G and H be two disjoint graphs. Then define the join G V H of
G and H to be the graph obtained from the union of G and H by adding the
set of edges {[x,y] : x E V(G),y E V(H)}.
Theorem 3.15 Let T be a reducible ntournament. Then DC(T) is either
1) two disjoint oddspiked cycles with or without isolated vertices,
2) a forest of caterpillars,
3) an oddspiked cycle and a forest of caterpillars,
4) K2 V 42, or
5) K\ V G, where G is an oddspiked cycle with or without isolated vertices
or a forest of caterpillars.
53
Proof: Let T be a reducible ntournament. Since T is reducible, its vertex set
can be partitioned into nonempty sets A and B such that every vertex of A
beats every vertex of B in T.
First assume that T has no transmitter or vertex of outdegree 0.
Thus, both A and \B\ must be at least 1. By Lemma 3.12, we have that
dom(T) = dom(T(A)) U I\B\ Also by Theorem 1.1, it follows that dom(T(A))
is either an oddspiked cycle with or without isolated vertices or a forest of
caterpillars. Next by Corollary 3.13, com(T) = com(T(B)) U I\a\ It follows
by Theorem 1.1 that com(T(B)) is either an oddspiked cycle with or without
isolated vertices or a forest of caterpillars. In addition, note that E(dom(T)) fl
E(com(T)) = 0. Therefore, since DC(T) = dom(T) U com(T), then DC(T) is
either two disjoint oddspiked cycles with or without isolated vertices, a forest
of caterpillars, or an oddspiked cycle and a forest of caterpillars.
Next assume T has both a transmitter x and a vertex y with out
degree 0. We may conclude by Theorem 2.3 that dom(T) = Also
by Lemma 3.14, we have that coni{T) = In addition, notice that
E(dom(Tj) fi E(com(T)) = {[rc, t/]} Since DC(T) = dom(T) U com(T), we
may conclude that DC(T) = K2 V 2
Now assume T has a transmitter x and no vertex with outdegree 0.
Let A = {a;} and B = F(T)\{a;}. It follows by Theorem 2.3 that dom(T) =
54
iÂ£ijn_i and by Lemma 3.13 that com(T) = com(T(B)) U I\. In addition, by
Theorem 1.1 we know that com(T(B)) is either an oddspiked cycle with or
without isolated or a forest of caterpillars. Now notice that E(dom(T)) fl
E(com(T)) = 0. Thus, since DC(T) = dom(T) U com(T), it follows that
DC(T) is K\ V G, where G is either an oddspiked cycle with or without
isolated vertices or a forest of caterpillars. A similar argument shows that
DC(T) is K\ V G, where G is either an oddspiked cycle with or without
isolated vertices or a forest of caterpillars when T has a vertex with outdegree
0 and no transmitter.
Now suppose that T is a regular ntournament with n odd. Then a
consequence of Lemma 3.2 is that dom(T) = com(T). Thus, since DC(T) =
dom(T) U com(T), we have that DC(T) = dom(T) = com(T) when T is a
regular tournament. Recently, in [10] Cho, Kim, and Lundgren determined
that the domination graph of a regular tournament is either an odd cycle or a
forest of paths. Thus, we have the following theorem.
Theorem 3.16 Let T be a regular ntournament with n odd. Then DC(T) is
either an odd cycle or a forest of paths.
In the case where all the paths are nontrivial, Cho, et al, found a char
acterization for forests of nontrivial paths which are the domination graphs of
regular tournaments. This result is presented in Chapter 4.
55
We now conclude this chapter by presenting some ways in which the
research on the dominationcompliance graph can be continued. Recall that
reducible tournaments are precisely those tournaments which are not strongly
connected. Although we have successfully characterized the dominationcom
pliance graph for reducible tournaments, such a characterization for strongly
tournaments has not yet been found. Thus, a problem one can consider would
be to try to find a characterization for the dominationcompliance graph of
strongly connected tournaments. Note that if such a characterization is found,
then the dominationcompliance graph will be characterized for all tourna
ments.
A second way in which the research on the dominationcompliance
graph could be continued would be to try to determine if the domination
compliance graph of a tournament is always a planar graph. Define a planar
graph to be a graph that can be drawn in the plane without crossing edges.
The reason we pose this problem is because the work presented in this chapter
leads one to believe that that this is in fact true for the following reasons. First,
planar graphs have the property that they have at most 3n 6 edges, where n
is the number of vertices in the graph. For n > 4, the dominationcompliance
graph of a tournament on n vertices has at most 2(n 1) edges. Thus, since
2(n 1) < 3n 6, for n > 4, the dominationcompliance graph always has
56
the right number of edges in the sense that it never exceeds the maximum
number of edges that a planar graph can have. Second, a planar graph never
has K5 or /\3.3 as a subgraph. By Corollaries 3.8 and 3.11, we have that the
dominationcompliance graph of a tournament also has this property. Finally,
the dominationcompliance graphs for reducible and regular tournaments are
planar.
Now notice that the domination graph and the compliance graph can
always be properly colored with at most three colors. Thus, a possibly easier
(preliminary) problem that one might consider would be to try to determine
whether the dominationcompliance graph of a tournament is 4colorable, i.e,
that it can be properly colored with at most four colors. It is well known
that planar graphs can be properly colored with at most four colors. So if
one can show that the dominationcompliance cannot be 4colored, then it will
follow that it is not always the case that the dominationcompliance graph is
a planar graph. On the other hand, showing that the dominationcompliance
graph is 4colorable will strengthen our belief that the dominationcompliance
graph is a planar graph. Therefore, we end this chapter with the following two
conjectures.
Conjecture 3.17 Let T be a tournament. Then DC(T) can be properly col
ored using at most four colors.
57
Conjecture 3.18 Let T be a tournament. Then DC(T) is
a planar graph.
58
4. Domination Graphs of NearRegular Tournaments
4.1 Introduction
The focus of this and the following chapters involves investigating the
domination graphs of nearregular tournaments. Recall that an ntournament
Ti
T is nearregular if n is even and every vertex has outdegree either or
Ti
1. Recently Cho, et al., investigated the domination graphs of regular
tournaments. In [10] they showed that the domination graph of a regular
tournament is either an odd cycle or a forest of paths. The following theorem
summarizes their findings.
Theorem 4.1 (Cho, et al., [10]) Let T be a regular tournament and assume
G is a graph without isolated vertices. Then G is the domination graph of T if
and only if G is an odd cycle or G is a forest of m even paths and n nontrivial
odd paths such that
(i) if m = 0,1, 2, 4, then n must be odd and m + n > 7 and
(ii) if m = 3 or ni>h, then n must be odd.
Since nearregular tournaments make up a large class of structurally nice tour
naments, it was natural to proceed with a study analogous to that in [10].
59
Thus, in this and the following chapters we will investigate the following ques
tion, Which connected graphs are domination graphs of nearregular tourna
ments? As we will see, if T is a nearregular tournament, then the domination
graph of T is not limited to odd cycles and forests of paths.
In the remainder of the chapter we will investigate which connected
domination graphs are the domination graphs of nearregular tournaments. In
particular, we will show that stars, odd cycles and caterpillars are not domina
tion graphs of nearregular tournaments. We will then determine exactly which
oddspiked cycles are the domination graphs of nearregular tournaments. The
following notation will be used in the remainder of this chapter as well as in the
ensuing chapters. Let x be a vertex in a nearregular ntournament T. If the
Ti
outdegree of x is , then we will say that x is a + vertex. If the outdegree
Ti
of a; is 1, then we will say that x is a vertex.
4.2 Connected Domination Graphs of NearRegular
Tournaments
In this section, we characterize those connected graphs that are the
domination graphs of nearregular tournaments. We begin by presenting a
lemma which will provide useful information regarding dominant pairs in a
nearregular tournament.
Lemma 4.2 Let T be a nearregular ntournament and x, y V(T). If[x,y]
60
dom(T), then at least one of x and y is a + vertex. Furthermore, if both
are + vertices, then \0{x) fl 0(y) \ = 1, and if exactly one is a + vertex,
then 10(x) fl 0(y) \ = 0.
Proof: Let T be a nearregular ntournament and x. y e V(T). Assume that x
and y form a dominant pair and that x beats y. Then since [x,y] e dom(T),
we have that 10(x) U 0(y)  = n 1. Thus, both x and y cannot be ver
tices since if they are, then \0(x) U 0(y) \ = \0(x) \ + \0(y) \ \0(x) fl 0(y)\ <
+ vertex. Furthermore, if both x and y are + vertices, \0(x) fl 0(y)
say x, is a + vertex, then \0(x)n0(y) \ = \0(x) \ + \0(y) \ \0(x)l)0(y)
Recall from Lemma 2.2 that in the domination digraph a vertex x
can have indegree at most 1, and at most one outneighbor of x can have
outneighbors. When the tournament is nearregular, we can put further re
strictions on the outdegree of a vertex in the domination digraph.
Theorem 4.3 Let T be a nearregular ntournament. In T>(T), a vertex
can have outdegree at most 1 and a + vertex can have outdegree at most
Proof: Let T be a nearregular ntournament and let x be an arbitrary vertex
in V(T). First assume that x is a vertex and has outdegree at least 2 in
Therefore, at least one of x and y must be a
3.
61
V(T). Let y,z Oz>(t){%) Since x is a vertex and forms a dominant pair
with both y and z, it follows by Lemma 4.2 that both y and z are + vertices.
Also since T is a tournament, we have that either y beats z oy z beats y in T.
Without loss of generality assume y beats But then O(x) fi 0(y) \ > 1 since
z e O(x) fl 0(y), which contradicts Lemma 4.2. Therefore, a vertex can
have outdegree at most 1 in V(T).
Next suppose that x is a + vertex and has outdegree at least 4
in V(T). Let y,z,t,r Ov{t){x). Consider the subtournament T' induced by
the set of vertices {y,z,t,r}. Since T' is a tournament on four vertices there
must exist a vertex in T' with outdegree at least 2. Without loss of generality
assume y is such a vertex in T'. But then since T' is a subtournament of T, we
have that O(x) fl 0(y) \ > 2, which contradicts Lemma 4.2. Therefore, a +
vertex can have outdegree at most 3 in V(T).
Now Theorem 2.1 tells us that the only possible connected domination
graphs of tournaments are oddspiked cycles, stars and nonstellar caterpillars
such that each has a triple end. Trivially, an odd cycle cannot be the domina
tion graph of a nearregular tournament since nearregular tournaments have
an even number of vertices. In addition, we will show, using Lemma 4.2 and
Theorem 4.3, that if G is the connected domination graph of a nearregular
ntournament with n > 4, then G cannot be a star or a caterpillar with a triple
end.
62
Lemma 4.4 If T is a nearregular ntournament with n > 4, then is
not the domination graph of T.
Proof: Let T be a nearregular ntournament with n > 4 and suppose that
dom(T) = Ki)U_i. Since dom(T) = l\fM i. then it follows by Theorem 2.3
that T either has a transmitter or has two distinguished vertices x and y such
that
i) y beats x,
ii) for all vertices z ^ x,y, we have that x beats z and z beats y, and
iii) T {./. y} induces a subtournament without a transmitter.
Suppose T has a transmitter x. Then x has outdegree n 1. But every vertex
in T must have outdegree either or 1, a contradiction since n 1 >
for n > 4 and n even.
Next suppose that T has two distinguished vertices x and y with the
properties stated above. Since /' {.r. y} must induce a subtournament without
a transmitter, the subtournament T {./. y} must have at least three vertices.
Therefore, T must have at least five vertices. Note that in T the vertex x
Ti
has outdegree n 2. But every vertex in T must have outdegree either or
1. Again we arrive at a contradiction since n^2 > forn>5 and n even.
2 s 2
Thus, it follows that Ad,ni is nt the domination graph of any nearregular
ntournament with n > 4.
Let H be a caterpillar with k vertices y\, y^, , yu on its spine. Also
63
let Wi represent the set of vertices pendant at re*. We will say that H is an odd
gapped pendant restricted (OGPR) caterpillar if it has the following
properties:
\Vj\ < 1 for all % with 2 < % < k 1.
The set V\ can have at most two vertices and the set V3 can have at
most three vertices or vice versa.
Consecutive vertices on the spine with degree 3 or more must be sep
arated by an odd number of edges.
Figure 4.1. Two odd gapped pendant restricted caterpillars.
Odd gapped pendant restricted caterpillars play a significant role with
respect to domination graphs of nearregular tournaments. It turns out that
if a caterpillar H is the domination graph of a nearregular tournament, then
H must be an OGPR caterpillar. This will be shown by proving the stronger
result that if a forest G of nontrivial caterpillars is the domination graph of a
nearregular tournament, then each component of G must be an odd gapped
64
pendant restricted caterpillar. In order to do so we need the following result.
Lemma 4.5 (Fisher, et al., [16]) Let G be the union of k nontrivial cater
pillars i?i, i?2, , Rk and suppose G is the domination graph of a tournament
T. Let G be properly 2colored. Also let v.i and Vj be any two vertices in V(Ri)
and V(Rj), respectively, that have the same color. Them, if Vi beads Vj in T and
if v and tv are vertices of Ri and Rj, respectively, we have that v beads w in T
if and only if v and w are the same color.
If a caterpillar H is a component of the domination graph tournament T, then
recall that the directed spine of the subdigraph of V(T) on V(H) is defined
to be the directed path that results when all vertices with outdegree 0 are
removed from the subdigraph of V(T) on V(H).
Theorem 4.6 Let a forest G of nontrivial caterpillars be the domination graph
of a nearregular tournament T. Lf H is a component of G, then H must be
an odd gapped pendant restricted caterpillar.
Proof: Assume a forest G of nontrivial caterpillars is the domination graph
of a nearregular tournament T. Let H be a component of G. Consider the
subdigraph of V(T) on V(H). Lemma 2.8 guarantees the existence of the
directed spine in the subdigraph of V(T) on V(H). Thus, we may assume
without loss of generality that the subdigraph of V(T) on V(H) is as depicted
in Figure 4.2. In addition, assume that the vertices of H are labeled as in
Figure 4.2.
65
Figure 4.2. The subdigraph of the domination digraph on the
vertex set of a component of dom(T).
In Figure 4.2, the sets V represent the set of vertices that are pendant
to Xi in H. Also note that the set Vi maybe empty, in which case X\ is a
pendant vertex in H and the spine of H consists of the vertices .r;>............../>.
Assume G is properly 2colored. We begin by making the following observation
regarding dominant pairs in V(H). First, we have that Orixi) nOr^i+i) = Vi
for 1 < i < k 1. To see this, note that every vertex in \\ has the same
color as xi+i. So it follows by Lemma 2.9 that xi+i beats every vertex in V^
Hence, Vi C 0T(xj) fl 0T(xi+1). Let tv E V(T). Assume tv belongs to V(H')
where H' is a component of G different from H. Then since every component
in G is nontrivial and the vertices Xi and xi+i are colored differently, we have
by Lemma 4.5 that either Xi beats tv or xi+i beats tv, but not both. If w is
in V(H), then again since Xi and Xi+\ are colored differently, by Lemma 2.9
either Xi beats w or Xi+\ beats w, but not both. Therefore, it follows that
0T(xi) fl 0T(xi+1) = Vi, for 1 < i < k 1. Second, let v E Fj. Then by a
similar argument, it follows that if tv E Orixi) fl Ot{v), then tv must be in
66
Vi. With these observations in hand, we proceed by showing that H is an odd
gapped pendant restricted caterpillar.
First we show that \Vj\ < 1 for all i with 1 < i < k 1 and also
that Vk has at most three vertices. Suppose that \Vj] = 2 for some i, with
1 < i < k 1. Since we know that Ot{x,i) fl Ot{xi+i) = V*, we may conclude
that \0T(xi)nOT(xi+i)\ > 2. But this contradicts Theorem 4.2 since [xi,xi+1] E
dom(T). Therefore, \Vj] < 1 for all i with 1 < < A; 1. Now since xk beats
every vertex of Vk in the domination digraph, we have by Lemma 4.3 that Vk
can have at most three vertices.
Note that if V* ^ 0 for some i with 1 < i < k 1, then since
Ov(T){X'j) = { r,. i} U Vi\ = 2, it follows by Lemma 4.3 that Xi must be a
+ vertex in T. Since we know that 0(x;) fl 0(xi+1) = \Vj] = 1 and
[xi,Xi+1] E dom(T), we may conclude by Lemma 4.2 that Xi+\ must also be a
+ vertex. Lastly, if Vk has two or three vertices, then it follows by Lemma
4.3 that xk must be a + vertex in T. We will use these facts to show that
there must be an odd number of edges between two consecutive vertices on the
spine with degree at least 3. Note that these vertices correspond to all vertices
Xi that have outdegree at least 2 and indegree 1 in V(T). Also note that the
only vertex that can have outdegree greater than 2 and indegree 1 is xk.
Assume that i,j E {1, 2,..., A;} with i < j and satisfying the following
properties:
67
The vertex xt has outdegree 2 and indegree 1 in V(T). Note that this
means \Vj\ = 1.
The vertex Xj has outdegree 2 (possibly greater than 2 if j = k) and
indegree 1 in V(T). Note that this means that V} > 1.
Every vertex xi between xi and Xj has outdegree and indegree exactly
1 in V(T). Note that this means that for all l with i < l < j, we have
Fi = 0.
So assume that there is at least one vertex along the spine between xt and
Xj. By the comment in the preceding paragraph, the vertices Xi, xi+i and Xj
are all + vertices in T. In addition, since Ot(xj) fl Ot{xji) = i = 0
and [xj\,Xj] dom(T), it follows by Lemma 4.2 that Xji must be a
vertex in T. Then since T is a nearregular tournament, we have that every
vertex in T must be either a + or a vertex. Thus, there must be at
least two vertices on the spine of H between xt and Xj. So suppose that that
there is an odd number of vertices along the spine between Xi and Xj. Then
there will be two consecutive vertices xi and xi+1, i < l < l + 1 < j, such that
either both are + vertices in T or both are vertices in T. It follows by
Lemma 4.2 that both cannot be vertices in T since [x(,X(+i] e dom(T).
In addition, both cannot be + vertices in T since [xi,xi+1] e dom(T) and
we must have that Ot(xi) fl Ot{xi+i) = 1. But this last condition is not
possible since \0T(xi) fl 0T(xi+1) = \\ and \\ = 0. Thus, we may conclude
68
that there must be an even number of vertices along the spine between re* and
Xj, which is equivalent to having x% and Xj separated by an odd number of
edges. Therefore, it follows that H must be an odd gapped pendant restricted
caterpillar.
Lemma 4.7 Let G be a caterpillar with a triple end. If T is a nearregular
tournament, then G is not the domination graph of T.
Proof: Let G be a caterpillar that is the domination graph of a nearregular
tournament T. Suppose that G has a triple end. Then we may conclude
by Theorem 4.6 that G is an odd gapped pendant restricted caterpillar. In
addition, since dom(T) = G, we have by Theorem 2.10 that T is a caterpillar
tournament. Now consider V(T). Lemma 2.8 guarantees the existence of the
directed spine, thus we may assume that V(T) is as depicted in Figure 4.3.
With respect to Figure 4.3, since T is a caterpillar tournament, then
the spine of G consists of the vertices x\, x2, , Xk if V\ is nonempty and
consists of the vertices ./ ;>......if V\ is empty. Also since G is a caterpillar
with a triple end, it follows from the proof of Theorem 4.6 that the triple end
V,
V,
Figure 4.3. The domination digraph of T.
69
must exist at xk.
Now since T is a caterpillar tournament and G is an odd gapped
pendant restricted caterpillar we have the following in T>(T):
(1) The integer k is even.
(2) The sets V*, for 1 < i < k 1, can have at most one vertex.
(3) The set Vk has exactly three vertices and T(Vk) is a subtournament
without a transmitter.
(4) Let i < j. If xi and Xj are two consecutive vertices on the spine of
G that have indegree 1 and outdegree at least 2 in 1?(T), then they
must be separated by an odd number of edges in G. Note that these
vertices correspond to those vertices on the spine of G that have degree
at least 3.
So using V(T), we will proceed by showing that T cannot be a nearregular
tournament, which is a contradiction.
Case 1: Suppose that Vi ^ 0. Then the spine of G consists of the vertices
X\, x2, , xk. To derive a contradiction, we will show that more than half of
the vertices of T are + vertices. To show this, we first need to establish a
series of results.
Result 1: Vi = 1.
Since T is a caterpillar tournament, x2 beats every vertex in Vf. Thus,
since G dom(T) and x\ beats every vertex in Vi, it follows by Lemma
70
4.2 that  Vi  = 1.
Result 2: Consecutive vert,ices on the spine with outdegree 2 are separated
by an odd number of edges. In addition, half of the vertices between two such
vertices are + vertices in T.
Since we already have that consecutive vertices on the spine with
indegree 1 and outdegree at least 2 in V(T) must be separated by an odd
number of edges, it suffices to show that X\ and Xi are separated by an odd
number of edges, where i is the smallest integer greater than 1 such that Xi has
outdegree at least 2 in V(T). For this i, we may conclude by Lemma 4.3 that
Xi must be a + vertex in T since Xi has outdegree greater than 1 in V(T).
See Figure 4.3. To show that x\ and Xi are separated by an odd number of
edges, we may assume that i > 2, because the result is trivial if i = 2.
Now since T is a caterpillar tournament, 0(xi) fl 0(xi+1) = Vi for all
i with 1 < i < k 1. Thus, since [x\,X2\ G dom(T) and \0{xi) fl 0{x2)\ =
\Vi \ = 1, it follows by Lemma 4.2 that both x\ and x2 must be + vertices
in T. Also since re*] G dom(T), the vertex Xi is a + vertex, and
\0(xii) fl O(xi) = Vj_i = 0, it follows from Lemma 4.2 that Xii must be a
vertex in T. Therefore, there must be at least two vertices between x\
and Xi. So suppose that there are an odd number of vertices between x\ and
Xi. Then since every vertex in T is either a + or a vertex, we will have
two consecutive vertices xi and xi+1, with 1 < l < l + 1 < i, such that both
71
are either
vertices or +" vertices. Since [xi,xi+1] Â£ dom(T), by Lemma
4.2 they cannot both be vertices. In addition, it follows by Lemma 4.2
that they both cannot be + vertices since 10(x\) fi 0(xi+1) = Lj = 0.
Therefore, there must be an even number of vertices between x\ and Xi on the
spine, which is equivalent to having x\ and Xi separated by an odd number of
edges.
Note from the argument just presented, it follows that if Xi and Xj
with i < j are two consecutive vertices on the spine that have outdegree at
least 2 in T>(T), then the vertices between them must alternate between being
+ and vertices. Thus since there are an even number of vertices
between two such vertices xt and Xj, we have that half of the vertices between
them must be + vertices and half must be vertices.
Result 3: Every vertex in V* is a + vertex in T.
Let w Â£ Vk. Since V* = 3 and T(Vk) induces a tournament with
out a transmitter, it follows that T(Vk) = t/3, i.e., the subtournament on
Vk is a 3cycle. Thus, w beats exactly one vertex in Vk. Therefore, since
[xk,w\ Â£ dom(T) and xk beats every vertex in Vk, it follows by Lemma 4.2
that 10(xk) fl 0(w) \ = 1. But by the same lemma, w is a + vertex.
Now using Results 1 through 3 we are ready to derive our contradic
tion. Let r be the number of vertices on the spine that have outdegree at
least 2 in V(T). Note that vertices with outdegree 2 in V(T) have exactly one
72
pendant neighbor. Thus, since \Vk\ = 3, we have that F(T) = k + (r 1) + 3
(k vertices are on the spine and r + 3 vertices are pendant). Next, since k is
even and consecutive vertices on the spine that have outdegree 2 in V(T) have
an even number of vertices between, then it follows that r must be even, i.e.,
there must be an even number of vertices on the spine that have outdegree at
least 2 in V(T). Now note that by Lemma 4.3, every vertex on the spine with
outdegree 2 in V(T) must be a + vertex in T. From Result 2, we have that
half of the vertices between consecutive vertices on the spine with outdegree
2 in V(T) must be + vertices in T. In addition, from Result 3, every vertex
in Vk is a + vertex in T. So counting the number of + vertices in T,
J.; rp J.; p
at least b r + 3 of the vertices in T are + vertices (r H of
them occur on the spine and 3 occur in Vk). But this is a contradiction since
k^r k + (r ^ 1) + 3 \V(T)\
b r + 3 >=and a nearregular tournament must
2 2 2
have the property that exactly half of its vertices are + vertices.
Case 2. Suppose that Vi is empty. Then the spine of G consists of the ver
tices ./:*......//,. Let i be the smallest integer such that the vertex xi has
indegree 1 and outdegree at least 2 in V(T). Note that i > 1. By the choice
of i, all vertices Xj, with j < i, have outdegree 1 in V(T). Therefore, Vj = 0
for all j < i.
Subcase 2.1 Suppose that i is even. Note that there are an odd
number of vertices xj with j < i. Also note that there are an even number
73
of vertices between consecutive vertices on the spine that have outdegree at
least 2 in V(T). Therefore, since k is even, there must be an odd number of
vertices on the spine that have outdegree at least 2 in V(T). So counting the
number of vertices in T, we have an even number of vertices in {.r t..., xk}
and since \Vi\ < %, for % < k and \Vk\ = 3, we have an odd number of vertices
in Vi U V2 U U Vk. But this implies that T has an odd number of vertices.
This is a contradiction since T is nearregular and must have an even number
of vertices.
Subcase 2.2 Suppose that i is odd. From Results 1 through 3, we
have the following:
(1) Every vertex with outdegree at least 2 in V(T) is a + vertex in T.
(2) Half the vertices between consecutive vertices on the spine with out
degree at least 2 are + vertices in T.
(3) Every vertex in \), is a + vertex in T.
So let r be the number of vertices on the spine that have indegree 1 and out
degree at least 2 in V(T). Since i is odd, there is an even number of vertices Xj
with j < i. Thus, since k is even and there must be an even number of vertices
between consecutive vertices on the spine that have indegree 1 and outdegree
at least 2 in T>(T), it follows that r must be an even integer. Thus, as in Case
1, we have that F(T) = k + (r 1) + 3.
Now note that if we show that half of the vertices in {.r t..., x^i}
74
are + vertices, then we shall be able to produce the same contradiction as
in Case 1. Thus, to finish this proof, it suffices to show that half of the vertices
in {.r i. ..., .i; i) are + vertices.
We begin by observing that since T is a caterpillar tournament,
0(xi1) fl 0(xi) = Vj1 = 0. Then since [xi\,x,j\ e dom(T) and Xi is a
+ vertex in T, it follows by Lemma 4.2 that xti must be a vertex
in T. Then since [xi2,Xii] dom(T) and 0(a;i_2) Cl 0(xi1) = V*_2 = 0,
we have by Lemma 4.2 that x%2 must be a + vertex in T. Then since
[:Cj_3, Xi2} C dom(T) and 0(xi_3) fl 0(xi2) = V*_3 = 0, it follows by Lemma
4.2 that Xi3 must be a vertex. Continuing in this fashion, we conclude
that x, is a + vertex in T, for j odd and 1 < j < i 1 and is a vertex
in T, for j even and 1 < j < i 1. Therefore, since i 1 is even we have that
half of the vertices in {.r j. ..., x^i} are + vertices in T. Hence it follows
as in Case 1 that more than half of the vertices in T are + vertices, which
is a contradiction.
Therefore, it follows that a caterpillar G with a triple end cannot be
the domination graph of a nearregular tournament.
Due to Lemmas 4.4 and 4.7, if a connected graph G is the domination
graph of a nearregular ntournament with n > 4, then G must be an odd
spiked cycle. It is not to difficult to see that not all oddspiked cycles are
the domination graphs of nearregular tournaments. For example consider the
75
following oddspiked cycle.
Figure 4.4. An oddspiked cycle which is not the domination
graph of a nearregular tournament.
Theorem 2.7 provides us with the means to construct the set of all tournaments
that have this oddspiked cycle as their domination graph. But none of these
tournaments is a nearregular tournament. We will show that whether an odd
spiked cycle is the domination graph of a nearregular tournament will depend
on the structure of the oddspiked cycle.
Deline an odd gapped single spiked odd cycle to be an oddspiked
cycle with the following properties:
Each vertex on the cycle can have at most one pendant neighbor.
Consecutive vertices on the cycle that have degree 3, or equivalently
that have a pendant neighbor, must be separated by an odd number
of edges. Note that this is equivalent to having an even number of
vertices between consecutive vertices on the cycle which have degree 3.
76
Observe that an odd gapped single spiked odd cycle must always have an odd
number of pendant vertices.
Figure 4.5. An odd gapped single spiked odd cycle.
Odd gapped single spiked odd cycles will play an important role in
determining all connected domination graphs of nearregular tournaments. In
fact, we will show that the only connected domination graphs of nearregular
tournaments are essentially odd gapped single spiked odd cycles. In addition,
we will show that every odd gapped single spiked odd cycle is the domination
graph of a nearregular tournament. This, together with the fact that an
odd cycle, a star, and a caterpillar with a triple end cannot be the domination
graph of a nearregular tournament, will give us the main result of this chapter.
Therefore, we proceed to derive the main result of Chapter 4, which is: A
77
connected graph G on n > 2 vertices is the domination graph of a nearregular
tournament if and only if G is either K2 or an odd gapped single spiked odd
cycle.
Lemma 4.8 Let G be an oddspiked cycle. If G is the domination graph of a
nearregular ntournament T with n > A, then G must be an odd gapped single
spiked odd cycle.
Proof: Let G be an oddspiked kcycle that is the domination graph of a near
regular ntournament T with n > 4. Then it follows by Theorem 2.7 that T
must be a spiked cycle tournament. So let x\,x2,....rt, be the vertices on the
cycle of G with T({x\, x2,..., Xk}) = Â£4 and let Vi, for 1 < i < k, represent
the set of pendant vertices at Xj. The remaining arcs in T, except for those
within each Vi, are determined by Figure 2.3. In particular, note that V(T) is
as shown below.
vi
78
We proceed by showing that G must be an odd gapped single spiked odd cycle.
For the following arguments let i + 1 denote (i mod k) + 1.
First we show that \Vj\ < 1 for 1 < i < k. Assume that \Vj\ > 2 for
some i. Since T is a caterpillar tournament, Figure 2.3 determines that xi+i
beats every vertex in V*. Thus, it follows that \0(xi) fi 0(xi+1) > 2. But this
is a contradiction to Lemma 4.2, since [xi,xi+1] e dom{T). Therefore, that
\Vj\ < 1 for all 1 < % < k.
Next we show that any two consecutive vertices along the cycle that
have a pendant neighbor must be separated by an odd number of edges. First
of all, if there is exactly one vertex xit on the cycle that has a pendant neighbor,
then it is easy to verify that there is an odd number of edges on the cycle when
the cycle is traversed from xt to itself.
So let Xi and Xj, with i ^ j, be two consecutive vertices along the
cycle of G such that
(1) Xi and xj have a pendant neighbor,
(2) there is a path from xt to Xj on the cycle in 1?(T), and
(3) every vertex between xi and Xj on the path from xi to Xj in V(T) has
no pendant neighbors.
By Lemma 4.3, we can see that xt and .r( must be + vertices in T since
they both have outdegree 2 in V(T). If j = i + 1, then trivially Xi and Xj
are separated by an odd number of edges. So assume that there is at least
79
one vertex between Xi and Xj on the path from Xi to Xj in V(T). Since T is
a caterpillar tournament, Oripcj) fl Ot{xi+i) = V*. Thus, since \Vi\ = 1 and
[xi,Xi+1] e dom(T), it follows by Lemma 4.2 that Xi+\ must be a + vertex
in T. Similarly, since i = 0 and [xji,Xj\ e dom(T), it follows by Lemma
4.2 that Xj1 must be a vertex in T. Since every vertex in T is either a
+ vertex or vertex, there must be at least two vertices between xt and
Xj on the path from Xi to Xj in V(T). If the number of vertices along the path
from Xi to Xj in V(T) is odd and at least 3, then there will be two consecutive
vertices xi and xi+1 on this path between Xi and Xj such that both are either
vertices or both are + vertices. By Lemma 4.2, they both cannot
be vertices since they form a dominant pair in T. They also cannot be
+ vertices. To see this, observe that since [xi,xi+1] E dom(T), it follows
by Lemma 4.2 that 0(x[) fl 0(x[+1) = 1. But then since T is a caterpillar
tournament, Ot{x[) fl Ot{x[+i) = V;. Thus, we have a contradiction since
\\ = 0. Therefore, it follows that there must be an even number of vertices
between Xi and Xj on the path from Xi to Xj in V(T), which is equivalent to
having Xi and Xj separated by an odd number of edges. Hence, G is an odd
gapped single spiked odd cycle.
Having established Lemma 4.8, naturally we wanted to know if all
odd gapped single spiked odd cycles are the domination graphs of nearregular
tournaments. We will show that the answer is yes. But before we do so, we
80
present the following two useful results.
Theorem 4.9 Let {4,4, , 4} 4 {1, 2,..., n} such that 4 < 4 < < ik
If the indices i\,i2,... ,ik alternate in parity, then the subtournament of Un
with vertices Xir,Xi2,... ,xik is isomorphic to Uk
Proof: Let T = Un and {4,4, ,4} 4 {1,2, such that 4 < 4 <
< ik Suppose that the indices 4,4,... ,ik alternate in parity. To show
that Y'(K,. x,.,..rn } ) = [4, it suffices to show that xit beats x^ in the
subtournament / ({.r,,.... ,Xik}) if l j is either odd and negative or even
and positive.
Assume l j is odd and negative. Then since the indices i\,i2,..., ik
alternate in parity, we have that i\ and ij are of opposite parity. Also since lj
is negative, i>i < ij. But then since i>i and 4 are of opposite parity, i>i ij is odd.
In addition, since ii < ij, it follows that ii ij is negative. Thus, by definition
of 14, we have that xit beats x^ in Un. Therefore, since Y'( {.rn. x,.r ... ,xik})
is a subtournament of l. it follows that x^ beats x^ in 7( {r/i x;.r ... ,xik}).
Next assume l j is even and positive. Then since the indices
4,4, ,4 alternate in parity, i>i and 4 are of the same parity. Also since
l j is even, ii > ij. But since ii and 4 are of the same parity, ii ij is
even. In addition, since i>i > ij we have that i[ ij is positive. Therefore,
we may again conclude that xit beats x^ in Un. Thus, xit beats x^ in the
subtournament , xi2,..., xik}).
81
In addition to being useful for proving the next result, Theorem 4.9
gives us a nice method for extracting subtournaments of Un that are isomorphic
to Uk, where k < n.
Lemma 4.10 Let G be an odd gapped single spiked odd cycle and assume G
is the domination graph of a tournament T. Let {v^/o^, ...,%} be the set of
pendant vertices such that i\ < i2 < < ik Then the subtournament induced
by the set of pendant vertices is isomorphic to Uk
Proof: Let G be an odd gapped single spiked odd cycle and suppose G is the
domination graph of a tournament T. Then since dom(T) = G, it follows
by Theorem 2.7 that T is a caterpillar tournament. Also since G is an odd
gapped single spiked odd cycle, each vertex on the cycle of G can have at most
one pendant neighbor. So let x\. ... ,xm, with m odd, be the vertices on
the cycle of G such that '/'({.ri. ... ,xm}) = Um. In addition, let {%, t>j2,
..., vik} be the set of pendant vertices, with A < i2 < < A To show that
T({t>il, vi2, ..., vik}) = Uk, it suffices to show that v^ beats vi% if j l is either
odd and negative or even and positive. By definition, since G is an odd gapped
single spiked odd cycle, we have that i\,i2,..., A must alternate in parity. So
assume that j l is either odd and negative or even and positive. Then since
the indices ii,i2,..., A alternate in parity, we have by Lemma 4.9 that
beats xit. Therefore, since T is a caterpillar tournament and beats xit, we
82
may conclude by Figure 2.3 that beats vit. Thus, vi2,..., vik}) = [4.
Lemma 4.11 If G is an odd gapped single spiked cycle, then it is the domina
tion graph of a nearregular tournament.
Proof: Suppose G is an odd gapped single spiked cycle. Let .ri. ......
with m odd, be the vertices on the cycle of G and let ,... ,vik, with k
odd, be the pendant neighbors of those vertices, such that i\ < i2 < < ik
With this labeling of the vertices of G, construct a spiked cycle tournament
that has G as its domination graph (as described in Chapter 2). Without loss
of generality assume '/'({.r t... ,xm}) = Um. Note that the remaining arcs
in T are determined by Figure 2.3. In particular, we have that V(T) is as
depicted in the following figure.
V
m
83
Note that in the figure above, the pendant sets have at most one vertex since
G is an odd gapped single spiked odd cycle. We claim that T is nearregular.
Ti
To show this it suffices to show that every vertex has outdegree either or
n
1 where n = m + k.
n
First we will show that every pendant vertex has outdegree 1
Ti
and that its corresponding neighbor on the cycle has outdegree . Let vir e
, vi2,..., vik}, with 1 < r < k, and xir be its neighbor on the cycle. Since
T({x\, X2, ., xm}) = Um and Um is a regular tournament, Xir beats m 2 ^
vertices in {x\, x2,..., xm} and is beaten by m 2 ^ vertices in {x\, x2,..., xm}.
Note that since T is a spiked cycle tournament, Ot(^v) H OtIw) = 0. Thus,
Tfi 1
since [xir, Vir] e dom(T) and Xir is beaten by  vertices on the cycle,
Tfi 1
vir beats the  vertices on the cycle that beat xir. Next since G is an
odd gapped single spiked odd cycle, the indices %\,%2alternate in parity.
Also since G is the domination graph of T, it follows by Lemma 4.10 that
T({t>il, Vi2,..., Vik}) = Â£4. Thus, since Â£4 is a regular tournament, vir beats
 vertices in {1^,1^, } and is beaten by the other  vertices in
, vi2,..., vik}. Again since Ot(^v) H = 0 and [xir,vir] e dom(T),
k1
we have that xt beats
vertices in {%, i;i2, ...,Vik}. Therefore, since Xj,
beats vir, we conclude that \Or(xi
m 1 k 1 m + k n
+ ^r + 1 = ^r = 2and
7711 k 1 m + k ^ n , . ,
UT\Vir) \ = 1 = 1 = 1, as desired.
Next we will show that the remaining vertices in T have outdegree
84
. n n
either or1.
2 2
First assume that k = 1, in other words, that G has exactly one
pendant vertex. For this case, note that T has n = m + 1 vertices. So without
loss of generality assume that x\ is the vertex on the cycle that has a pendant
neighbor v\. Let Xj, with j ^ 1, be any other vertex on the cycle. Since
/'({./1. ......./,} ) = Um, we know that Xj beats exactly
7711
vertices in
{.r i. ..., xm}. Now if xj beats Xi, then since T is a spiked cycle tournament,
TTI 1
we have by Figure 2.3 that V\ beats Xj. And so, Xj has outdegree  =
Ti
1. If Xj is beaten by Xi, then again since T is a spiked cycle tournament, it
7711
+ 1 =
follows by Figure 2.3 that Xj beats V\. And so, Xj has outdegree
Z Z
Since Xj was an arbitrary vertex on the cycle without a pendant neighbor, we
conclude that all vertices on the cycle without pendant neighbors have the
appropriate outdegree in T.
Next suppose that G has more that one pendant vertex. So let Xi and
Xj, with i ^ j, be two consecutive vertices along the cycle of G such that
(1) and Xj have a pendant neighbor,
(2) there is a path from xi to Xj on the cycle in V(T), and
(3) every vertex between Xi and Xj on the path from Xi to Xj in V(T), has
no pendant neighbors.
For the following, we will take r i to mean (r i) mod m. So let xr be a
vertex between Xi and Xj on the path from Xi to Xj in V(T). We will show
85
1.
Ti Ti
that if r i is odd, then Or(xr) = and if r i is even, then 0(a;r) =
If j = i + 1 {mod m), then the result is trivial since we have already shown
Ti
that every vertex with a pendant neighbor has outdegree . So assume that
there are at least two vertices between Xi and Xj on the path from Xi and
Xj. We proceed by induction on r i. Let r = i + 1 (mod m), so r i is
odd. Since T is a caterpillar tournament and [xi,Xi+1] G dom(T), we have
that O(xi) fl 0(xi+1) = {t>} where v is the pendant vertex at re*. But then
since [xi,Xi+1] G dom(T), it follows that \0{xi) U 0{xi+1) = n 1. Therefore,
71 71
0(ar+i) = 0(a;j)U0(a;j+i)0(a;j) + 0(a;j)n0(a;j+i) = (nl) + l =
Next let r = i + 2 (mod m). Note that r^i is even. Since [xi+\, a;i+2] G dom(T)
and T is a spiked cycle tournament, Ot(%i) fl Ot{xi+2) = Vi+i 0. But
since [xi+\, a;i+2] G dom(T), we conclude that \Ot{xi+i) U Or{xi+2)! = n 1.
71
Therefore, since we have shown that 0(a;i+i) = , it follows that 0(a;i+2) =
71 71
\0(xi+i)U0(xi+2)\\0(xi+i)\ + \0(xi+i)n0(xi+2)\ = (n 1) + 0 = 1.
Assume the result holds for r, with r i > 2. We will show that
the result holds for r + 1. If (r + 1) i is odd, then r i is even. By the
71
induction hypothesis, 0(a;r) = 1. Since T is a caterpillar tournament
and [xr,xr+i] G dom(T), it follows that 0(xr) fl 0(xr+1) = Vr = 0. But then
since [xr,xr+\} G dom(T), we have that 10(xr) U 0(xr+1) = n 1. Therefore,
0(a;r+i) = 10(xr) U 0{xr+i)\ 0(a;r) + 0(a;r) fl 0{xr+1) = (n 1)
86
Tl \ Tl
lj + 0 = . Next if r + 1 i is even, then r ^ i is odd. By the
n
. Since T is a caterpillar tournament and
induction hypothesis, 0(ay)
[ay, ay+i] e dom(T), we may conclude that 0(xr)nO(xr+i) = Vr = 0. But then
since [ay,ay+i] e dom(T), it follows that 0(ay)U0(ay+i) = n 1. Therefore,
Ti
0(ay+i) = \0{xr) UO(rr+i) 0(ay) + \0{xr)C\0{xr+i) \ = (n 1) + 0 =
Ti
1. The result follows by induction.
Theorem 4.12 Let G be a connected graph on n > 2 vertices. Then G is the
domination graph of a nearregular tournament if and only if G is either K2
or an odd gapped single spiked odd cycle.
Proof: If n = 2, then there is exactly one tournament on two vertices which
is nearregular, clearly its domination graph is K2. So let n > 4. Then by
Lemmas 4.4 and 4.7, we may conclude that if G is the domination graph of a
nearregular tournament, then G cannot be a star or a caterpillar. Thus, by
Theorem 1.1, G must be an oddspiked cycle. It follows by Lemma 4.8 that G
must be an odd gapped single spiked odd cycle.
Conversely, for n > 4, we have by Lemma 4.11 that if G is an odd
gapped single spiked odd cycle, then G is the domination graph of a near
regular tournament.
Therefore, we have successfully characterized all the connected dom
ination graphs for nearregular tournaments. Although a caterpillar is never
87
the domination graph of a nearregular tournament, we have been able to de
termine by Lemma 4.6, that if a caterpillar is a component of the domination
graph of a nearregular tournament, then it must be an odd gapped pendant
restricted caterpillar. We will use this fact in Chapters 6 and 7 to construct
infinite families of nearregular tournaments with the property that each has a
forest of nontrivial caterpillars as its domination graph.
5. NearRegular Path Tournaments
5.1 Introduction
In this chapter, we study and characterize all forests of paths that
are domination graphs of nearregular tournaments. In [19], Fisher, et al.,
determined which forests of caterpillars are possible as domination graphs of
arbitrary tournaments. In the special case that each caterpillar is a nontrivial
path, we have the following theorem.
Theorem 5.1 (Fisher, et al., [19]) The union of n nontrivial paths is the
domination graph of a tournament if and only if n = 4 or n > 6.
Note that Theorem 5.1 holds for tournaments in general. Recall Theorem
4.1 which gives a characterization for all forests of paths that are domination
graphs of regular tournaments. In particular, notice that not all combinations
of m even paths and n nontrivial odd paths with ni + n = A oy ni + n> 6, are
domination graphs of regular tournaments. However, when the tournament is
nearregular, we will show that any combination of four or at least six non
trivial paths, except four odd paths, is the domination graph of a nearregular
tournament. Therefore, in the nearregular case, we get closer to the original
result (Theorem 5.1). In the remainder of this chapter, an even path refers to
a path on an even number of vertices and an odd path refers to a path on an
89
odd number of vertices.
5.2 Forests of m even paths and n nontrivial odd paths.
Let p(m,n) denote the set of all graphs that are the union of m even
paths and n odd paths (possibly trivial). Let p*(m,n) denote the set of all
graphs that are the union of m even paths and n nontrivial odd paths. For
the remainder of this chapter, we will focus on answering the question, For
which integers m and n is a graph G e p*(m,n) the domination graph of a
nearregular tournament? We start by introducing some notation which will
simplify the ensuing work.
Suppose G p* (m, n) is the domination graph of a tournament T.
Let G = EiUE2U UU(d,U(d._,L UOn, where Â£) denotes the ith even path
and Oj denotes the jth odd path. The vertex set of Ei is {uu,Ui2,..., Uimi} and
the vertex set of Oj is {'Uji,Vj2, , Vjnj}. Define the following subtournaments
of T as follows:
T(B) with the vertices {tin, U21, , um 1, i>n, i>2i, , fni},
T(E) with the vertices {tin, U21, , um 1},
T(0) with the vertices {i>n, v2i, , iViiK
T(Ei) with the vertices {un, i2) , ibm,}; and
T(Oj) with the vertices {'Uji,Vj2, , Vjnj}.
We will refer to the set of vertices {un,U2i, ,umi,vn,V2i, , wni} as the
base vertices. In particular, un is the base vertex that corresponds to the ith
90
even path Ejt and Vji is the base vertex that corresponds to the jth odd path
Oj. In the remainder of this chapter, we will let R4 denote an arbitrary path
when it is not specified whether it is an even or odd path. In addition, we will
let {.r, 1. ... ,xiSi} denote the vertex set of i?j. Now by properly coloring
each path with two colors, red and blue, we are able to derive the following
results.
Lemma 5.2 Let G G p*(m,n) be the domination graph of a tournament T
and let T(Ei) be the subtournament on the vertex set {un,Ui2, of the
even path E;t and Tj be the subtournament on the vertex set {xji,Xj2,
of a path Rj different from, Ej. Then for all vertices Xjk G V{Tf), \0(xjk) fl
Tfl
V(T(Ei)) \ = II(xjk) n V(T(Ei)) \ = d.
Proof: Properly 2color the vertices Eri and Rj using colors red and blue such
that un and Xj\ are colored red.
Assume that Un beats Xji in T. Let Xjk G V{Tf). If k is odd, then Xjk
is colored red. Since un and Xj\ have the same color, we have by Lemma 4.5
that Xjk beats all the vertices in T{Ef) that are colored blue and is beaten by
all the vertices in T(Â£'i) that are colored red. Since T(E,{) has exactly A red
vertices and d blue vertices, \0(xjk)f]V(T(Ei))\ = \I(xjk)f]V(T(Ei))\ = d.
If k is even, then Xjk is colored blue. Again by Lemma 4.5, the vertex Xjk beats
all the vertices in T(Ej) that are colored red and is beaten by all the vertices
91
in T(E,j) that are colored blue. Again it follows that \0(xjk) fi V(T(E,}))\ =
Tfl
\I(xlk)nV(T(E,))\ =
Next assume that Xji beats un. By a similar argument, we may
conclude that 10{xjk) fl V(T(Ei))\ = \I{xjk) fi V(T(Ei))\ = A.
Lemma 5.3 Let G Â£ p*(m,n) be the domination graph of a tournament T
and let T(Oi) be the subtournament on the vertex set {vn,vi2,... ,viTli} of the
odd path Oi and Tj be the subtournament on the vertex set {xj\,Xj2, ,xjSj}
of a path Rj different from, O*. If (vn,Xji) Â£ A(T), then for k odd, we have
\0{xjk) n v{T{Oi)) \ =
n,j + 1
2
m + 1
and for k even, we have \0(xjk) fl F(T(Oi))
. If (xji,vn) Â£ A(T), then for k odd, we have \0(xjk) fl V(T(Oj))\
Ti' 1
and for k even, we have \0(xjk) fl F(T(Oi)) =
2 7 1 v v v 2
Proof: Properly 2color the vertices of and Rj with colors red and blue such
that vu and Xj\ get colored red. Then T(Oi) has exactly
rii + 1
red vertices
and A blue vertices.
Assume vn beats Xj\ in T. Let Xjk Â£ V(Tj). If k is odd, then Xjk is
colored red. Since vn and Xj\ are colored red and vn beats Xji, then it follows
by Lemma 4.5 that Xjk beats all the vertices in T(Oj) that are colored blue.
Since T(Of) has exactly
Tli 1
blue vertices, \0(xjk) fl V(T(Oj))\
Tli 1
2 jnj/ xx 2
If k is even, then Xjk is colored blue. Again by Lemma 4.5, we have that Xjk
beats all the vertices in T(0,j) that are assigned the color red. Since T(0,j) has
exactly  red vertices, U{xjk) fl V (i (Oi))\ = .
92
