TOPICS ON DOMINATION GRAPHS OF
TOURNAMENTS
by
Faun C. C. Doherty
B.A., Oberlin College, 1993
M.A., 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
2000
This thesis for the Doctor of Philosophy
degree by
Faun C. C. Doherty
has been approved
by
Margaret Bf'O
ozzens
/

Marcelle Arak
Doherty, Faun C. C. (Ph.D., Applied Mathematics)
Topics on Domination Graphs of
Tournaments
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
Since 1994, domination graphs of tournaments have been the subject
of a series of four papers by Fisher, Lundgren, Merz, Reid, and sometimes
Guichard. The culmination of these papers is a complete characterization of
domination graphs of tournaments, thus the characterization of competition
graphs of tournaments which are closely related. Several new topics of research
were of interest with the completion of this characterization, including the
characterization of domination graphs of special classes of tournaments, and
the study of generalizations of domination graphs of tournaments. Two of
these topics are the focus of this dissertation.
In 1997, Cho, Lundgren, and Kim studied the domination graphs
of regular tournaments. Certain results that were used restricted their find
ings to domination graphs of regular tournaments with nontrivial components,
which they characterized. An extension of this result which includes domina
tion graphs with possible trivial components is included in this dissertation,
completing the characterization of domination graphs of regular tournaments.
Domination, competition, resource, and compliance graphs are all
graphs which can be defined on any digraph. It was found that these four
graphs are related when they are defined on tournaments. The characteriza
tion of domination graphs of tournaments leads directly to the characterization
of the other three graphs defined on tournaments. Graphs composed of the
unions or intersections of two of the four graphs above have been a topic of
interest since 1989. These are the niche, mixed pair, competitionresource, and
dominationcompliance graphs. In 1999, Bowser, Cable, and Lundgren charac
terized mixed pair, and thus niche graphs, of tournaments. Preliminary work
on dominationcompliance graphs of tournaments was done by Jimenez and
Lundgren in 1997. This dissertation contains the complete characterization
of dominationcompliance (thus competitionresource) graphs of tournaments.
A new graph is defined and characterized to aid in the characterization of
dominationcompliance graphs of tournaments. It is the p/dgraph of a tour
nament.
This abstract accurately represents the content of the candidate's thesis. I
recommend its publication.
Signed V
L J. Richard Lundgren
DEDICATION
To my parents, and to Michael, Obie, and Tycho.
ACKNOWLEDGMENTS
My great thanks and appreciation to my advisor, J. Richard Lund
gren. He had faith in my ability even when mine was wavering. It was a
pleasure to work with him, a good lesson to observe him, and an honor to be
his graduate student. Thanks also to my committee members for their their
time and advice, and especially for their support of my future plans.
I would like to thank the Mathematics Department of UCD in general
for not only allowing me the opportunity to learn to teach, but also for pro
viding the example, the support, and the freedom to do it well. It has meant a
great deal to me to be recognized by the department for my accomplishments
in this area.
Finally, I would like to thank everyone in my life who has supported
me during these years. You have all made this possible. In particular, my
parents, who have provided me with much needed perspective and constant
encouragement. And Michael, whose unconditional support has been daily,
and has never faltered. He has provided me with a life outside of mathematics
during these years, which is invaluable to me.
Faun C. C. Doherty
Denver, Colorado
to to
CONTENTS
Figures............................................................. ix
Tables............................................................. vii
1. Introduction...................................................... 1
1.1 Competition Graphs and Applications............................. 4
1.2 The Characterization of Domination Graphs....................... 8
.1 Connected Domination Graphs ................................... 9
.2 Domination Graphs with More
than One Nontrivial Component....................... 12
1.2.3 Domination Graphs of
Regular Tournaments.................................. 16
1.3 Other Graphs.................................................. 17
2. Domination Graphs of Regular Tournaments......................... 23
2.1 Introduction................................................... 23
2.2 Preliminaries.................................................. 25
2.2.1 Notation..................................................... 25
2.2.2 Structure.................................................... 26
2.3 Trivial Paths ................................................. 33
2.4 The Conditions................................................. 35
2.5 Constructions.................................................. 39
2.6 The Main Result ............................................... 47
3. Path Tournaments ................................................ 54
4. DominationCompliance Graphs..................................... 63
4.1 Introduction................................................... 63
4.2 DominationCompliance Graphs of
Tournaments with Connected
Domination Graphs.............................................. 66
4.3 DominationCompliance Graphs of
Tournaments Whose Domination Graph is
the Union of Two Nontrivial Caterpillars....................... 78
4.4 DominationCompliance Graphs of
Tournaments Whose Domination Graph is the
Union of Three Nontrivial Caterpillars......................... 84
4.5 The Family Q................................................... 90
4.6 Preliminary Results for
Larger Domination Graphs....................................... 93
5. Planarity of DominationCompliance Graphs........................ 95
vii
5.1 Introduction................................................. 95
5.2 The Structure of DominationCompliance
Graphs....................................................... 95
6. p/dGraphs of Tournaments..................................... 109
6.1 Introduction................................................ 109
6.2 Cycles...................................................... 110
6.3 Paths and Isolated Vertices................................. 115
6.4 The Main Theorem............................................ 125
6.5 Consequences of p/dGraph Characterization.................. 130
7. Summary ...................................................... 134
7.1 Characterization Results ................................... 134
7.1.1 Domination Graphs ......................................... 134
7.1.2 DominationCompliance Graphs............................... 135
7.1.3 p/dGraphs of Tournaments.................................. 137
7.2 Graph Theoretic Results on
DominationCompliance Graphs................................ 138
7.3 Open Problems............................................... 139
Appendix
A. Connecting Edges............................................. 140
B. Counterexamples to Forbidden Structures...................... 146
References....................................................... 151
CM CM CM CM CM
FIGURES
1.1 A 5tournament and its Domination Graph................. 1
1.2 A Depiction of the Research Web Originated by the Char
acterization of Domination Graphs of Tournaments. Dotted
boxes are topics covered in this dissertation....... 2
1.3 A 5tournament and its Competition Graph................ 6
1.4 A 5tournament, its Domination Graph, and its Directed
Domination Graph........................................... 10
1.5 The Tournament U5....................................... 10
1.6 ........................................................ 11
1.7 The Directed Domination Graph for a General Caterpillar. . 12
1.8 x and y are Paired by w................................. 14
1.9 x and y are Distinguished by w.......................... 15
1.10 A 5tournament and its domination, resource, compliance,
competition, mixed pair, niche, competitionresource, and
dominationcompliance graphs. Each line contains graphs
which are complements of each other.................. 19
.1 An Example of the Labeling of Paths.................... 27
.2 Properly Colored U5.................................... 29
.3 Arcs in T Between Two Properly Colored Paths........... 30
.4 Counterexample, Tb Shown............................... 34
.5 The Tournament U$...................................... 40
2.6 The Tournament too, ^3, ^4, ^5, ^6) .......... 41
3.1 If G is an Odd Spiked Cycle with One Pendant Vertex. ... 56
3.2 Example of the Decomposition of an Odd Spiked Cycle into
Paths................................................... 57
3.3 Consider Paths without their Base Vertices.............. 58
3.4 Case 1 .................................................... 59
3.5 Case 2 .................................................... 60
3.6 Case 3 .................................................... 61
3.7 Case 4 .................................................... 62
4.1 The Directed Domination Graph for a General Caterpillar. . 65
4.2 An Example of the DominationCompliance Graph of a Tour
nament Whose Domination Graph is an Odd Spiked Cycle. . 67
4.3 Tournaments in T........................................ 69
4.4 DC{T) If T 6 T.......................................... 70
4.5 A General T G Cl (excluding arcs between the 3cycle and
other pendant vertices) and DC(T)....................... 71
4.6 Two Examples of DominationCompliance Graphs Where dom(T) is
a Caterpillar.............................................. 76
4.7 One Example of a DominationCompliance Graph Where dom(T) is
Two Caterpillars........................................... 82
4.8 Example of a DominationCompliance Graph Where dom(T) is
the Union of Three Caterpillars as in Lemma 4.2. (The dot
ted arcs are in T)......................................... 86
4.9 The Four Tournaments on 4 Vertices and their Domination
Compliance Graphs.......................................... 90
5.1 Example of dcsubgraph.................................... 96
5.2 If T does not have Property F............................. 97
5.3 Connecting Edges.......................................... 99
5.4 Example if last pendant set is empty. Case 2............. 100
5.5 Example of p/d(T) ....................................... 103
5.6 Case 1 .................................................. 105
5.7 General Example of the Appropriate Placement of dcSubgraphs
Corresponding to p/d(Tb).................................. 107
6.1 Possible 3Paths in p/d(T)............................... 110
6.2 Example of Cycle if edges are all p Edges (Dotted arcs rep
resent both edges inp/d(T) and arcs in T)........... Ill
6.3 The mCycle, Theorem 6.2.4............................... 113
6.4 Example of Path and Vertex not on Path. (Dotted edges are
in p/d{T) arcs are in T).............................. 115
6.5 Example of Shortened Path Model, Dotted Arcs in T........ 119
6.6 The 4Tournament, Ti..................................... 120
6.7 The 4Tournament, T2..................................... 120
6.8 Building a Tournament with Specific p/dGraph, Starting
with a 4Tournament....................................... 127
6.9 Building a Tournament with Specific p/dG raph: k = 4, m = 2. 129
7.1 Example of dcsubgraph................................... 135
A.l Connecting Edges Between dcsubgraphs with First and Last
Pendant Sets.............................................. 141
A.2 Case One, Odd D\, Odd D2................................. 142
A.3 Case Two, Odd D\, Even D2................................ 143
A.4 Case Three, Even Di, Odd D2.............................. 144
A. 5 Case Four, Even Di, Even D2.............................. 145
B. l Example of dcsubgraphs and T& such that the addition of one
3cycle as a first pendant set eliminates one set of connecting
edges..................................................... 148
x
B.2 Example of a DominationCompliance Graph with 3 Paths
of dcSubgraphs and 2 Isolated dcSubgraphs. Connecting
edges will exist between every two dcsubgraphs joined by a
p or d edge........................................... 149
B.3 Example of dcSubgraphs and Tb such that DC(T) is Five
Isolated dcSubgraphs................................. 150
xi
1. Introduction
The work presented in this dissertation lies within the context of the
characterization of domination graphs of tournaments. A tournament is an
oriented complete graph. A dominant pair in a tournament T is a pair of
vertices x and y whose union of outsets together with {x, y} comprises the
vertex set of T. The domination graph of a tournament T is a graph on the
vertex set of T with edges between vertices which form a dominant pair.
#
Figure 1.1. A 5tournament and its Domination Graph
The interest in domination graphs of tournaments has its origins in the
study of competition graphs, which will be discussed below. The culmination
of this interest is a series of papers ([FLMR98], [FLMR95], [FLMR99], and
[FGL+a]) which answer the question: which graphs can be the domination graph
of a tournament? The characterization of domination graphs of tournaments
opened the doors to several avenues of study which are depicted in Figure 1.2.
1
Figure 1.2. A Depiction of the Research. Web Originated by the Characteri
zation of Domination Graphs of Tournaments. Dotted boxes are topics covered
in this dissertation.
J
I
2
i
The main theorem itself naturally splits into two parts: domination
graphs which are connected, and domination graphs which are not. Two main
types of connected domination graphs were classified, those called spiked odd
cycles, and those called caterpillars with triple ends. Domination graphs of
tournaments which are not connected are forests of caterpillars with certain
restrictions in some cases. An isolated vertex is considered a trivial caterpillar.
Some results used to characterize domination graphs with multiple components
were proven specifically for domination graphs with nontrivial components. It
was found that components which are isolated vertices can be problematic
because of this, and often needed to be handled separately.
After the main characterization was obtained, there was interest in
examining domination graphs of special classes of tournaments, specifically reg
ular ([CKL]) and near regular tournaments ([Jim98]). Once again, basic results
excluded isolated vertices as components of domination graphs. A characteriza
tion of domination graphs with nontrivial components of regular tournaments
was achieved. Chapter 2 extends the result for domination graphs of regular
tournaments to include possible trivial components. Chapter 3 takes a brief
look at domination graphs of a special tournament, the path tournament.
Another step in this web of research was to look at certain generaliza
tions of domination graphs of tournaments. Each of these I shall only mention
3
here, but they will be defined below. Along with domination and competition
graphs, there are resource and compliance graphs. The mixed pair graph, niche
graph, competitionresource graph, and dominationcompliance graph were each
defined as unions or intersections of some two of the four graphs above. The
problem of characterizing these graphs is compounded by their more compli
cated definition. Ultimately, however, basic results used for the characteri
zation of domination graphs of tournaments prove invaluable to characterize
these unions and intersections. Mixed pair and niche graphs were character
ized in [BCL99]. Chapters 4, 5, and 6 include a characterization of domination
compliance (thus competitionresource) graphs, as well as some graph theoretic
results about them.
As the topics addressed in this dissertation are so dependent on the
inspirational work of others, the remainder of this chapter will serve to add the
definitions, brief details, and results that provide the foundation of this work.
1.1 Competition Graphs and Applications
The origin of the study of domination graphs of tournaments lies
within the study of competition graphs. A competition graph of a digraph D
(denoted C(D)) is the graph on the vertex set of D with an edge between
vertices x and y if and only if the intersection of their outsets is nonempty,
4
that is 0{x) n 0(y) ^ 0. Put another way, there is an edge between two
vertices if they beat something in common, thus the term competition. J. E.
Cohen first studied these graphs in the 1970s ([Coh78]) in relationship to food
webs. A directed graph can be used to model a food web if vertices represent
species and an arc from x to y indicates that species x preys on species y. A
competition graph of a digraph modeling a food web is the depiction of which
species compete for food. There has been much study of competition graphs
and their generalizations since the 1980s, for example, by Brigham and Dutton
[BD83], Kim, McKee, McMorris, and Roberts [KMMR95], and Roberts and
Raychaudhuri [RR85]. Surveys on competition graphs can be found by Kim
[Kim93], and Lundgren [Lun89].
Some of the important applications of competition graphs and their
generalizations involve communication over a noisy channel, artificial intelli
gence, radio and television transmissions, certain types of codes, military com
munication, and simplification or modification of large scale computer models.
For example, if D is a symmetric digraph, possibly modeling transmissions of
radio signals, then the competition graph of D can be used to assign frequen
cies or to investigate conflict within the network. The inverse problem for
competition graphs is the following: if G is the competition graph of several
digraphs, and we know the structure of G, can we say something about the
5
structure of a representative D such that G = C(D)? This idea is useful for
the investigation of large communications networks with a fixed competition
graph. It is of interest to develop heuristics for adding links to the communica
tions network that do not create conflicts in the existing frequency assignments
(see [GLM84], [GLM89]).
#
Figure 1.3. A 5tournament and its Competition Graph
Tournaments provide a small but important subcategory of di
graphs with enough structure for interesting exploration. Tournaments them
selves are of interest in such applications as roundrobin competitions, pair
comparisons, dominance in nature (such as chicken pecking order), codes, and
majority voting with an agenda.
Studying the competition graphs of tournaments is a natural off
shoot of the general study of competition graphs, and this was introduced
by Lundgren, Merz and Rasmussen in [LMR95]. The motivating inquiry was
to determine the minimum number of edges in the competition graph of an
6
rctournament, a tournament with n vertices. Competition graphs of tourna
ments generally have many edges, thus the complement of the competition
graph provided a more accessible model for study. It was noted that given
a tournament T, if one reversed all arcs in T and then studied the comple
ment of the resulting tournament, one was studying the domination graph of
T. This relationship is not necessarily true for other digraphs. Therefore, all
results about domination graphs of tournaments correspond to results about
competition graphs of tournaments.
Domination graphs of tournaments are relatively sparse, and fairly
repetitive in their structure. Some applications of domination graphs of tourna
ments involve pair comparison experiments, and productive work assignments.
Examples of these are the following. Suppose that there are n candidates on a
short list for a job (each represented as a vertex in a tournament), and suppose
that an arc from x to y indicates that the majority of the search committee
prefers candidate x to candidate y. Unfortunately, only two candidates can be
invited for an interview due to limited funds. The search committee would like
to invite a pair of candidates x and y such that for any other candidate z, each
member of the search committee either prefers x to z or y to z. The number
of such pairs possible can be found by looking at the domination graph of the
tournament. Domination graphs can also be used in selecting teams of two
7
for demanding assignments to maximize strengths or balance strengths of the
pairs. The task of a characterization of domination graphs of tournaments was
realizable.
1.2 The Characterization of Domination Graphs
The endeavor to characterize domination graphs of tournaments be
gan in 1994 by D. C. Fisher. J. R. Lundgren, S. K. Merz and K. B. Reid.
Later, D. Guichard joined the research. Domination graphs of tournaments
were characterized in a series of papers: [FLMR98], [FLMR95], [FLMR99], and
[FGL+a]. The results of these papers involve domination graphs of tournaments
which have nontrivial components. The characterization of domination graphs
which may have trivial components occurred slightly later in [FGL+b]. My
work, excepting the chapter on regular tournaments, will also pertain only to
domination graphs with nontrivial components. I will therefore confine my
discussion of results to [FLMR98], [FLMR95], [FLMR99], and [FGL+a]. The
main theorem of this series of papers can be divided into two parts, that which
characterizes domination graphs with one component, and that which charac
terizes domination graphs with more than one component.
8
1.2.1 Connected Domination Graphs
The following result pertains to tournaments which have connected
domination graphs.
Theorem 1.2.1 ([FLMR95]) A connected graph is a domination graph of a
tournament if and only if it is an odd cycle, an odd spiked cycle, a star, or
a nonstellar caterpillar with three or more vertices pendant to one end of the
spine.
An odd cycle is a cycle with an odd number of vertices, and an odd spiked
cycle is an odd cycle with possible pendant vertices adjacent to some or all of
the cycle vertices. We refer to a caterpillar with three or more vertices pendant
to one end of the spine as a caterpillar with a triple end.
Given a specific domination graph of some tournament, there are sev
eral results which define the structure of the underlying tournament. Some of
these details are important to other results, and I will mention them here. The
directed domination graph of a tournament T (denoted D(T) ) is dom{T) with
its edges oriented as they are in T (see Figure 1.4). The following result re
stricts the possible structure of D(T) .
9
Figure 1.4. A 5tournament, its Domination Graph, and its Directed Domi
nation Graph
Proposition 1.2.2 ([FLMR.99]) Let T be a tournament. In D(T) a vertex
can have at most one inneighbor and. at most one of its outneighbors can have
outneighbors.
Let Un denote the family of tournaments with vertex set {xi,X2, ,xn}
in which X{ beats Xj if and only if j i is either even and positive, or odd
and negative. These tournaments, also called rotational tournaments, play an
important role in the structure of tournaments whose domination graph is con
nected. For example, we have the following result pertaining to domination
graphs which are spiked odd cycles. Let Cn be the cycle on n vertices.
Figure 1.5. The Tournament Us
10
Lemma 1.2.3 ([JL98]) Let T be an ntoumament where n > 3 is an odd
number. Then Cn is a subgraph of dom(T) if and only if T is isomorphic to
Un.
If dom(T) is a spiked odd cycle, we will use the following notation.
Let xi: i = 1,..., k be the cycle vertices, and let Vi represent the set of pendant
vertices adjacent to xi. Using Lemma 1.2.3 and 1.2.2, we can further describe
the arc structure of T.
Lemma 1.2.4 ([JL98]) If dom(T) is an odd spiked cycle, then Figure 1.6
gives the arc structure of T where double arrows may refer to the direction of
severals arcs.
Figure 1.6.
If dom{T) is a caterpillar, Proposition 1.2.2 gives us the following
structure for D{T) .
11
Figure 1.7. The Directed Domination Graph for a General Caterpillar.
In [FGL+a], it was found that the subtournament on the k spine
vertices must be isomorphic to Uk It is often useful to properly twocolor
dom{T) when it is made up of caterpillars. I shall use the colors black and
white for technical reasons. A further result in [FGL+a] states that if we use
the orientation as in Figure 1.7, all arcs between vertices in a caterpillar that
are not in the same pendant set are directed to the right between vertices of
different colors, and to the left between vertices of the same color. This result
is also true for domination graphs that are made up of more than one cater
pillar. The arc structures for tournaments whose domination graphs are stars
will be addressed in Chapter 4.
1.2.2 Domination Graphs with More
than One Nontrivial Component
If the domination graph of a tournament is the union of more than one
nontrivial component, then the components are all caterpillars, and we have
the following characterization.
12
Theorem 1.2.5 ([FGL+a]) If G is the union ofn > 1 nontrivial components,
then G is the domination graph of a tournament if and only if:
(1) n = 2 and either both caterpillars have a triple end or one has a triple
end and the other is K\^;
(2) n = 3 and either all three caterpillars have a triple end, or one caterpillar
is KiÂ£ and the other two have a triple end, or two caterpillars are
and the other has a triple end;
(3) n = 5 and at least one of the caterpillars has a triple end or is
(4) n = 4 or n > 6.
Once again, a great deal of arc structure in T can be deduced. An important
result is the following:
Lemma 1.2.6 ([FGL+a]) Let G be the domination graph of a tournament T
where G\, Gi, ..., Gn denote the properly colored components of G such that
each leftmost spine vertex, V{, of Gi is colored black for all i. If an arc is
directed from Vi to Vj and if u and w are vertices of Gi and Gj respectively,
then there is an arc from u to w if and only if u and w are the same color.
13
The leftmost vertex in each caterpillar is called the base vertex of that
caterpillar. The subtournament of T on all base vertices in dom(T) is denoted
Tfi. Because of the arc structure in the two results above, if the subtournament
on the base vertices is known, most of the structure of T is determined. This
leads one to three important definitions originally appearing in [FGL+a] which
are instrumental in obtaining Theorem 1.2.5. They will also prove instrumen
tal in several results in this paper. They are the following:
Definition 1.2.7 Two vertices x and y of a tournament T are paired if there
exists a third vertex w in T such that x > w and y > w or w Â¥ x and y.
Figure 1.8. x and y are Paired by w.
Definition 1.2.8 Two vertices x and y of a tournament T are distinguished if
three exists a third vertex w in T such that x^wtyoxy^wtx.
Definition 1.2.9 A tournament T is wellcovered if every pair of vertices in
T are both paired and distinguished.
14
x y X y
Figure 1.9. x and y are Distinguished by w.
The wellcovered property is particularly important, since the key to
proving parts (3) and (4) of Theorem 1.2.5 was discovering the relationship
between the existence of a wellcovered rztournament and the union of n non
trivial caterpillars being the domination graph of a tournament, as we see in
the next theorem.
Theorem 1.2.10 ([FGL+a]) If there is a wellcovered tournament on n > 4
vertices, then the union of any n nontrivial caterpillars is the domination graph
of a tournament.
Thus it was discovered that if there is a wellcovered tournament on n > 4 ver
tices, and Tb is constructed to be such a tournament, then the union of any n
nontrivial caterpillars is the domination graph of a tournament. Wellcovered
ntournaments exist for n = 4 or n > 6, but not for n = 5.
15
1.2.3 Domination Graphs of
Regular Tournaments
A tournament is called regular if every vertex has equal outdegree and
indegree. It is easy to see that an rctoumament is regular if n is odd and each
vertex has indegree and outdegree equal to H. H. Cho, S.R. Kim and J.
R. Lundgren [CKL] looked at this subset of tournaments to determine which
graphs with nontrivial components could be their domination graphs. The fol
lowing is their general result.
Theorem 1.2.11 ([CKL]) If T is a regular tournament of order at least 3,
then dom(T) is either an odd cycle or a forest of two or more paths.
Let p*{m, n) be the set of all graphs whose components consist of m
even paths (that is, paths with an even number of vertices) and n nontriv
ial odd paths. Examining the possible structure of T given that dom{T) is
in p*{m,n) led Cho et al. to the following characterization of exactly which
nontrivial paths are realizable as the domination graph of a regular tournament.
Theorem 1.2.12 ([CKL]) Let G E p*(jn, n) Then the following are true:
(i) If m = 0,1, 2,4, then G is the domination graph of a regular tournament
16
if and only if n is odd and m\n> 7.
(ii) If m = 3 or m> 5 then G is the domination graph of a regular tourna
ment if and only if n is odd.
The proof of this theorem uses results proved explicitly for domination graphs
with nontrivial components. In Chapter 2, we examine this theorem with
respect to trivial components. We will see where it is limited to nontrivial
components, why it cannot be simply extended to include trivial components,
what conditions might allow one to include trivial components, and ultimately
how to extend it to a complete characterization of the domination graphs of
regular tournaments.
1.3 Other Graphs
We have defined competition graphs and domination graphs in the
previous sections. There are two other graphs which are related to these graphs,
and together, the four graphs can be combined by union or intersection to
form still more graphs of tournaments. One is the resource graph, R(T) and
is defined to be the graph on the vertex set of T with edges between vertices
17
which are beaten by a common vertex in T. Formally,
x adj y <=> 3z E V(T) 3 z > x and z ^ y.
The other graph is the compliance graph, com(T) and is defined to be the
graph on the vertex set of T with edges between vertices which do not beat
any vertex in common in T. Formally,
x adj y <==$ Vz E V{T), z Â¥ x or z y.
Note that the domination graph and resource graph of a tournament are com
plements of each other. The same is true for the competition graph and com
pliance graph of a tournament. Since the domination graph and competition
graph of a tournament are also related, we have the following relationships,
where (*)c is the complement function, and T is the reversal of T.
com{T) = dom(T), and dom(T) = (i?(T)c).
Note that all compliance graphs are domination graphs of some tournament.
There are interesting graphs that arise as combinations of these. The
first to be investigated was the niche graph of a digraph in 1989 by Cable et
al. in [CJLS89]. The niche graph is defined on a digraph D as the graph on
the vertex set of D with an edge xy if and only if there is a vertex in D which
pairs x and y. It is also the union of the competition graph and the resource
18
T
R(T)
niche graph
competitionresource
graph
dominationcompliance
graph
Figure 1.10. A 5tournament and its domination, resource, compliance, com
petition, mixed pair, niche, competitionresource, and dominationcompliance
graphs. Each line contains graphs which are complements of each other.
19
graph of D. Other studies of niche graphs can be found in Anderson et al.
([ABCL93], and [And95]), Bowser and Cable ([BC90], [BC91]), and Fishburn
and Gehrlein ([FG92], [FG94], [FG96]). Niche graphs of tournaments were
introduced and characterized in Bowser et al., [BCL99]. We have noted that
competition graphs of tournaments have a relatively large number of edges,
thus niche graphs do as well. As in the characterization of competition graphs,
the complement of the niche graph, the mixed pair graph, has been used to find
a characterization of niche graphs. The mixed pair graph of a tournament is
the intersection of the domination and compliance graphs of a tournament. An
alternate definition is the graph on V(T) with edges between vertices which are
paired by no vertex in T. It was found that the maximum degree of a vertex in a
mixed pair graph is less than or equal to two. The following theorems summa
rize the characterization of mixed pair graphs. Let Pn be the path on n vertices.
Theorem 1.3.1 ([BCL99]) Cn is realizable as a mixed pair graph if and only
if n is odd.
Theorem 1.3.2 ([BCL99]) Pn is realizable as a mixed pair graph if and only
if n is even.
20
Theorem 1.3.3 ([BCL99]) If the mixed pair graph of T has at least two com
ponents, then it must be a forest of paths.
In particular, Bowser et al. found that the mixed pair graph of an ntournament
could not be a forest of two paths if n is even, and could not be a forest of
three paths if n is odd.
The remaining union and intersection graphs are the competition
resource graph of a tournament, C(T) n i2(T), and its complement, the
dominationcompliance graph of a tournament, dom(T) U com{T) The
competitionresource graph has been studied for digraphs in [Wan95], but only
preliminary work has been done for competitionresource graphs of tourna
ments in [JL97]. We can think of the competitionresource graph of a tourna
ment T as the graph on V(T) with edge xy if and only if T contains a vertex
which x and y beat, and a vertex which beats x and y. The domination
compliance graph has an edge xy if either no vertex beats x and y or there
is no vertex which x and y both beat. The initial work on a characteriza
tion of these two graphs focused on dominationcompliance graphs since they
have fewer edges than their complement. A characterization of domination
compliance graphs of some special classes of tournaments, such as regular and
reducible, has been achieved ([Jim98]). The completion of the characterization
21
of dominationcompliance (thus competitionresource) graphs is presented in
Chapters 4, 5, and 6. The tool of particular importance in this characteriza
tion is the characterization of domination graphs of tournaments. Also useful
is the characterization of a new graph defined on tournaments, the p/dgraph,
of which mixed pair graphs are a subset. This shall be presented in Chapter
6.
22
2. Domination Graphs of Regular Tournaments
2.1 Introduction
As mentioned in Section 1.2.3, H. H. Cho, S. R. Kim, and J. R.
Lundgren examined the domination graphs of regular tournaments. As a gen
eral result, they found that if T is a regular tournament, then dom(T) could
only be an odd cycle, or a forest of two or more paths (Theorem 1.2.11). To
complete a characterization of domination graphs of regular tournaments, it is
necessary to determine exactly which forests of paths could be the domination
graph of a regular tournament. The solution to this problem makes use of
certain theorems which are known to be true for domination graphs composed
of nontrivial components. Thus, the detailed result in [CKL], Theorem 1.2.12,
only pertains to unions of nontrivial paths. Naturally, the more general result
which includes possible isolated vertices is of interest. This chapter will present
this extended result.
In order to clearly show the strategy used in proving this extended
result, it is necessary to describe much of the process used in [CKL]. I will
begin by introducing the necessary notation and proceed by stating the results
23
which, restrict the structure of a regular tournament T if G = dom(T) is the
union of paths. In the process, we shall see which results are used that require
that G be the union of nontrivial paths. These results were important to the
solution of the problem in [CKL], and it was not at all clear that including
trivial paths would not change the main theorem. Some exploration provided
us with examples involving trivial paths that did cause problems. An example
will be shown of a tournament T that follows all restrictions obtained so that
dom(T) is the union of nontrivial paths. We will replace one odd path with a
trivial path and show why dom(T) fails to be the union of paths that we might
expect.
We shall then present conditions, which we prove that when met, re
sult in the union of paths including trivial paths being the domination graph
of a regular tournament. We must then answer the question: do there exist
tournaments that meet these conditions? We will find that the constructions
used in [CKL] do meet these conditions. This will enable us to extend the
original result to include possible trivial paths. This is the strategy to prove
sufficiency, but we will investigate some individual cases to prove the necessity
direction of the main theorem.
24
2.2 Preliminaries
2.2.1 Notation
We know that if T is a regular tournament whose domination graph
has more than one component, then dom{T) is a forest of paths. It turns out
that T has a great deal of structure that can be determined. To explore this,
we need some notation. As noted in the Introduction, p*(m, n) denotes the set
of all graphs whose components consist of m even paths and n nontrivial odd
paths. Let p(m, n) denote the set of all graphs whose components consist of
m even paths and n odd paths. Note that in p(m, n), some or all of the odd
paths could be trivial, and also note that p*(m, n) is contained in p(m, n).
Suppose that G 6 p(m, n). We have the following notation for each
subgraph of G.
Even Paths: Pi, .... Pm,
Odd Paths: Qi, ..., Qn,
Paths which may be odd or even: Ri, ..., Rp
Vertex set of Pt: {%, ui2,..., uimi},
Vertex set of Qf {vji, Vj2,..., Vjnj}
Vertices of a path that may be odd or even: {rua, wi2,..., tOiS}.
Given a tournament T on the vertex set of G, we have the following notation
for each subtournament of T.
25
Let Tb be the subtoumament of T on the vertices {tin, u21,umi,vu,
V21, ^nl}
Let Te be the subtournament of T on the vertices {uu, u2i,
Let T0 be the subtournament of T on the vertices {un, n2i, ...,uni}.
Let Tei be the subtournament of T on the vertices {jlt ui2,
Let T0j be the subtournament of T on the vertices {vji, Vji,..., VjUj}.
Please see Figure 2.1 for an example of this labeling where the boxed vertices
represent the vertices in each subtournament.
2.2.2 Structure
Cho et al. determined that if G E p*(m, n), and G = dom(T) for reg
ular T, then T has some very specific structure. The following result gives the
structure of the subtournaments on the paths. It was proven for G G p*{m, n).
but its proof holds for G G p(m, n).
Lemma 2.2.1 ([CKL]) LetG G p(m, n) be the domination graph of a regular
tournament T. Then Tei ~ Umi and T0j ~ Unj for each 1 < i < rn and each
1 < J < n.
26
Figure 2.1. An Example of the Labeling of Paths.
27
Let T be a regular tournament whose domination graph is in p(m, n).
Then Lemma 2.2.1 shows that the structures of Tei and TOJ are unique up to
isomorphism. In the rest of the paper, we assume that uimf > 'Ui(mi_1) >
> Ui2 > un > Uimi (resp. VjUj > Uj(nj_i) Â¥+ vj2 > Vji > Vjnj) is
the main cycle in Tei (resp. T0j). Let un (resp. vu) be the base vertex of Pt
(resp. Qj) for each i E {1,..., m (resp. n)}.
For the duration of this chapter, we will properly color G Â£ p(m, n)
letting the base vertices be black, and we will draw each path vertically with
the base vertex at the bottom. So Wij is black for j odd, and let be white
for j even. Since each Tei (resp. TOJ) is isomorphic to Umi (resp. Unj), this
coloring provides a simple visualization of arcs in Tei (resp. Toj). We have
that arcs within Tei (resp. TOJ) pointed upwards are between vertices of the
same color, and pointed downwards are between vertices of different colors (see
Figure 2.2).
The following is a restatement of Lemma 1.2.6 for paths which de
scribes arcs between two paths.
Lemma 2.2.2 Let G be the domination graph of a regular tournament T whose
path components Ri, R2, ..., Rp are properly colored. Let Vi be the base vertex
of Ri for each i Â£ {1,... ,p}. Then, if an arc of T is directed from v{ to Vj, and
28
between vertices of the same color
between vertices of different colors
Figure 2.2. Properly Colored U5.
if v and w are vertices of Ri and Rj, respectively, then there is an arc from v
to w if and only if v and w are of the same color.
Thus we have further structure of T, if dom(T) G p{m,n), which can be de
scribed chromatically (See Figure 2.3). Suppose that Ri and Rj are two paths
of G E p{m, n) such that the base vertex of Ri beats the base vertex of Rj.
Then if dom{T) = G, the subtournament of T on the vertices of Ri and Rj is
comprised of the following arcs:
all arcs pointed upwards are between vertices of the same color,
all arcs pointed downwards are between vertices of different colors,
all arcs from Ri to Rj are between vertices of the same color,
and all arcs from Rj to Ri are between vertices of different colors.
29
between, vertices of the same color
between vertices of different colors
Ri Rf
Figure 2.3. Arcs in T Between Two Properly Colored Paths.
If all arcs of T on the vertices of any two paths behave in this manner, we say
that T is a path tournament. Path tournaments and their domination graphs
will be further explored in Chapter 3.
The following result pertains to T being regular.
Lemma 2.2.3 ([CKL]) If G Â£ p(m,n) is the domination graph of a regular
tournament T, then n is an odd integer, and Ta is a regular tournament.
In order to show that a specific union of paths can be the domination
graph of a regular tournament, it is useful to have a result which will help in
constructing regular tournaments. It is the following:
30
Lemma 2.2.4 ([CKL]) Let T be a path tournament for G p(jn, n). Sup
pose T0 is a regular tournament and each vertex of Te beats of the vertices
of Ta in T. Then T is a regular tournament.
Given a forest of paths as a domination graph of a regular tournament
T, we have described much of the necessary structure of T. Note that Lemmas
2.2.1 and 2.2.2 give us that the structure of T is completely determined by
Te, Ta, and the arcs between Te and Ta, that is, the subtournament Tb. The
results from Fisher et al. that are useful in determining Tb are specifically for
domination graphs with nontrivial components. They are the following:
Theorem 2.2.5 ([FGL+a]) If there is a wellcovered tournament on n > 2
vertices, then the union of n nontrivial caterpillars is the domination graph of
a tournament.
Theorem 2.2.6 ([FGL+a]) If G is the union ofn > 2 nontrivial caterpillars,
none of which has a triple end or is and G is the domination graph of a
tournament T, then there is a wellcovered tournament on n vertices.
31
In the proofs of the above two theorems, Fisher et al. actually showed
that given the union G of n > 2 nontrivial caterpillars, if there is a wellcovered
tournament T* on n > 2 vertices, then there is a tournament T such that
Tf, = T* and dom(T) = G. Also, if G is a union of nontrivial caterpillars, none
of which has a triple end or is AT1;3, then there is a tournament T such that
dom(T) = G and Tb is wellcovered. The following is the important immediate
consequence of this observation.
Theorem 2.2.7 ([CKL]) Suppose G G p*(m,n). Then G is the domination
graph of a regular tournament if and only if there exists a regular path tourna
ment T for G such that Tb is wellcovered.
Let us summarize the results so far. We have that if G p* (m, n),
then m f n = 4 or is > 6 by Theorem 1.2.5. By Lemma 2.2.3 and Theorem
2.2.7, T must be a regular path tournament for G such that T& is wellcovered,
and T0 is regular. If we want to construct such a tournament which is regular,
we can let T0 be regular, let Tb be wellcovered, and let each vertex of Te beat
vertices of Ta in T. Then T is a regular path tournament, and by Theorem
2.2.7, dom(T) = G.
32
2.3 Trivial Paths
Cho et al. proved the main theorem of [CKL] for unions of nontrivial
paths by using Theorem 2.2.7 above. Now we shall address the following ques
tion:
Does Theorem 2.2.7 hold for G E p(m,n)? That is, if G E p(m,n) has trivial
paths, and if we construct a regular path tournament for G such that T& is
wellcovered, is it necessarily true that dom(T) = G, as it is if G E p*(m,n) ?
We find that the answer is no by counterexample. Suppose that we have
G E p( 1,5), and we construct a path tournament for G as specified and shown
in Figure 2.4. Then we can prove that G is not the domination graph of the
path tournament T by showing that two vertices in two different paths are a
dominant pair.
Consider the vertices u52 and ui2. We claim that they are a dominant
pair, and to prove this, we shall examine the vertices in each path.
Paths Qi, Qo, and Qz: all white vertices of Qi, Qo, and Q3 beat u52,
but U12 beats all white vertices of each of these paths. All black vertices
in these paths are beaten by u12
Path Q4: no vertex in Q4 beats either n52 or ui2.
33
I
\
I
!
Path Q$: vertex v53 beats V52, but u12 beats v53.
Path Pi: vertex uu beats u52, but ui2 beats uu.
Thus, since there must be an edge between v52 and ui2 in dom(T) dom{T) 7^
G. There are two additional conditions which, when added to T& being well
covered, will guarantee that for a regular path tournament T, dom(T) E
2.4 The Conditions
The two conditions along with the wellcovered property that are
sufficient to prove the main theorem of [CKL] for forests of paths including
isolated vertices are the following.
Condition One:
For any pair of base vertices wn and 1Uji, either an even base vertex pairs
them, or if wn beats Wj\ and wji is an even base vertex, there exists a
base vertex which wn and Wji beat; if wn beats Wji and Wji is an odd
base vertex, there exists a base vertex which beats wn and Wji.
35
Condition Two:
For any pair of base vertices wix and wjX, either an even base vertex dis
tinguishes them or if wxx beats wjX and wix is an even base vertex, there
exists a base vertex which is beaten by wxx and which beats WjX: if wn
beats Wji and wix is an odd base vertex, there exists a base vertex which
beats uin and is beaten by WjX.
The following theorem proves that with these conditions, we can construct a
regular tournament T such that G E p(m, n) is its domination graph.
Theorem 2.4.1 If there exists a TJ, on m + n vertices which is wellcovered,
Ta is regular, each vertex of Te beats odd base vertices, and which satisfies
Conditions One and Two, then the union of n odd and m even paths is the
domination graph of a regular tournament.
Proof: Let G be such a union of paths; call them Rx, Ro, ..., Rp where p = n+m.
To construct a regular tournament T having domination graph G, properly
color G with black and white so that each base vertex is black. By Lemma
2.2.1, Tei ~ Umi and TOJ ~ Unj for each 1 < i < m and 1 < j < n. Then
the vertices of TeX and T0j beat vertices below of different color, and vertices
36
above of the same color. Connect the base vertices so that the resulting n 4 m
toumament Tb satisfies the hypothesis. Lemma 2.2.2 determines the remaining
arcs. Now we must verify that all pairs of vertices except those adjacent in G
are dominated.
(1) It is easy to check that no vertex beats pairs of vertices that are adja
cent in G.
(2) Consider two vertices v and w in the same path of different colors, but
not adjacent in G. Let w be below v. Then there exists a vertex
adjacent to w and above w. Thus, u beats both v and w.
(3) Consider two vertices v and w in the same path FU, of the same color.
Since Ta is regular, if n > 3, there exists a base vertex which beats wn
and a base vertex beaten by Wn in T, thus one of these base vertices
will beat v and w. If n = 1, then by Theorem 1.2.5, m = 3 or m > 5.
Note that all vertices of Te beat since n 1. If Ri is an odd path
and v and w are both black, then all vertices of Te dominate them. If v
and w are white, then the top vertex of Ri dominates them. Suppose
that Ri is an even path. Since Tb is wellcovered, un and n are paired
by an even base vertex. Depending on the color of v and w, either this
even base vertex beats both or the odd base vertex beats both.
(4) Consider two vertices v and w in different paths, say Ri and Rj, and
37
of the same color. If there exists an even base vertex Uk 1 which pairs
wn and wji, then depending on the direction of the arc between u^i
and wn and the color of v and w, either all black vertices of beat
v and w in T or all white vertices do. Suppose that there is no even
base vertex which pairs wn and wji. Without loss of generality, let wn
beat wji. Suppose Wji is an even base vertex. Then by Condition One,
there exists wti which is beaten by wn and Wji If v and w are white,
then wti dominates them. If v and w are black, then the top vertex of
Rj dominates them since it is white. Now suppose that w3i is an odd
base vertex. Then by Condition One, there exists a wt\ which beats
Wii and w3i. If v and w are black, wa dominates them. If v and w are
white, then the top vertex of Rj dominates them since it is black.
(5) Consider two vertices v and w in different paths, say R4 and Rj, and
of different colors. If there exists an even base vertex Uk 1 which distin
guishes wn and w31, then depending on the direction of the arc between
Uki and Wn in T, and the colors of v and w, either all black vertices of
Rk dominate v and w or all white vertices do. Suppose that there is
no even base vertex which distinguishes wn and Wji Without loss of
generality, let wn beat w3i. Suppose that wn is an even base vertex.
Then by Condition Two, there exists a base vertex wti which is beaten
38
by wn and beats Wj\. If v is white and w is black, then wti dominates
both. If v is black and w is white, then the top vertex of Ri dominates
both. Suppose that Wn is an odd base vertex. Then by Condition
Two, there exists a base vertex wti which beats ra;i and is beaten by
Wj\. If v is black and w is white, wti dominates both. If v is white and
w is black, then the top vertex of Ri dominates both.
Thus, all pairs of vertices except those adjacent in G are dominated, and the
union of n odd and m even paths is the domination graph of a regular tourna
ment.
Thus the addition of Conditions One and Two guarantee that the
union of n odd and m even paths is the domination graph of a regular tourna
ment.
2.5 Constructions
Now we must prove that there exist regular path tournaments whose
subtournament on their base vertices is both wellcovered, and satisfies Con
ditions One and Two. Cho et al. has proven that if G E p*(m,n), then there
exists a wellcovered T& such that Ta is regular and the vertices of Te beat
vertices in T0. We shall use the fact that such a exists, and prove that a
39
defined in such a way satisfies Conditions One and Two. There are a couple
of constructions that must be explicitly defined, since these general properties
are not enough to demonstrate that the conditions are met.
It is useful to note that a wellcovered tournament on 6 or greater
vertices can always be constructed. It is known that on 5 or more vertices,
there is a tournament such that every arc is in a 3cycle. To construct a
(k 4 l)tournament that is wellcovered, start with a /ctournament such that
every arc is in a 3cycle, and add the (k + l)st vertex so that it beats every
other vertex. Then each pair of vertices is both paired and distinguished.
Figure 2.5. The Tournament U5
We will need a regular wellcovered tournament. For all odd n, let
Un denote the tournament on vertices {aq,..., xn} in which Xi beats Xj it j i
is positive even and i 7^ 1, j 7^ n, or j i is negative odd but not equal to 1,
or j i = 1 or j i 1 n (see Figure 2.5). This is Un with the main cycle
reversed. It is shown in [CKL] that for n >7, Un is regular, wellcovered, and
dom{Un) consists of isolated vertices.
40
I
Figure 2.6. The Tournament T[3i3](u;i, wo, w3, w4, w5, w6)
1
41
We also need the following special tournaments which are wellcovered.
Let T[3t3](wi,W2,W3,w,w5,w6) be defined as follows: wi w3 > w2 > Wi,
y W5 wq y Wi, wi  {1^4, u;5}, w2 > {w5.u;6}, w3 > {u;4,u;6},
wq wi, Wi  w2, and w5 > W3. (See Figure 2.6).
Let T[4>3](u)i, w2, ... W7) be the following: let the subtournament on {toi,..., we}
be T[3)3]. Let w~ f {u/i,... u;5} and w$ * W7. It can be checked that both of
these tournaments are wellcovered.
Now suppose that G E p(m,n) for some specific cases of m and n.
We will proceed to construct a regular path tournament T for G such that Tb
is wellcovered, T0 is regular, and the vertices of Te beat ^44. vertices of T0. We
will find later that our constructions also satisfy Conditions One and Two.
1. Suppose that G E p(2,n). We must have that n is odd by Lemma
2.2.3, and n > 5 by Theorem 1.2.5. Let Ta ~ Un and Te be tin > U21.
Define Tb as follows: let uu > Vji only when j is odd, and let u2i > Vji
only when j = 2, or j is odd but not equal to 1.
2. Suppose that G E p(4, n). Then n >3 and is odd. Suppose that n = 3.
Then let Tb be T[4j3](uu, u2i, ^31, Uu, ^21, ^31, u41). Suppose that n > 5.
Let Te be the subtournament of T[4i3](uu, u2i, U31, Un, U21, ^31, u4i) on
the vertices {tin, u2i, U31, zt41}. Let Ta ~ Un. Define Tb as follows: let
U31 > Vj\ only when j is odd, and for each i = 1, 2,4, let un > vji
42
only when j = 2 or j > 3 is odd.
3. Suppose that G E p(m, 5). Then m > 2. Suppose that m = 3. The
let Te be the cycle uu > U21 U31 * uu. Let T0 ~ Â£/5. Define T& as
follows: uu > uy! only for j odd, and {u21, u3].} > u7i when j = 2. 3
or 5. Suppose that m = 5. Then let the subtournament T* of T on
{uu, U21,W31,U42, nii, U21, U31} be T,[43](nu,U2i)'si; nn, U21,^31,U41) i11
Tfj. Let u5i beat all vertices except i?u. Let Ta ~ U5. Define XJ, as
follows: let {1131, n5i} > u_,i only when j is odd, and for each i = 1,2,
and 4, let un > vji only when j = 2,3 or 5. Suppose that m > 6.
Construct Te to be wellcovered by letting Uu > u21 n3i > uu, and
let the subtournament on all other vertices except um 1 be such that
every arc is in a 3cycle. Then let um 1 beat all %, i = 1,..., m 1.
Let Tc ~ C/5. Define T\j, as follows: let {un,iimi} > Vji only when j is
odd. For i = 2,..., m 1, let un vji only when y = 2, 3 or 5.
We need the following Lemma.
Lemma 2.5.1 In a regular tournament every arc is contained in a 3cycle.
Proof: Suppose that T is a regular tournament on n vertices, and suppose that
arc xy is not contained in a 3cycle. Then the inset of x and the outset of y
are disjoint to avoid a 3cycle. Since T is regular, the cardinality of the insets
43
and outsets of each, vertex is 2^i. So we have that I{x) i 0(y) + x + y\ =
4 2=1 + 2 = 77. + 1, a contradiction to the number of vertices being n.
Now we may prove that if there is a regular path tournament with
Tb wellcovered, Ta regular, and vertices of Te beating 2I vertices of T0, then
there is a regular path tournament that satisfies Conditions One and Two.
Theorem 2.5.2 If G p*(m,n) is the domination graph of a regular tourna
ment T, then there exists a Tb that is wellcovered and satisfies Condition One
and Condition Two.
Proof: We have noted that if G G p*(m,n), Cho et al. proved that there is
a path tournament for G such that Tb is wellcovered, T0 is regular and the
vertices of Te beat 2i vertices in Ta. Note that n > 1 and n is odd since
T is regular. Given these specifications, we shall verify that Conditions One
and Two are satisfied. Where the specifications are not adequate, we shall
refer to the constructions above. First, we shall verify that Condition One is
satisfied. Suppose that we have base vertices wn and Wji in G. Without loss
of generality, let uia beat Wji in T. Suppose that Wji is an even base vertex.
Suppose that wn is also an even base vertex. Then since each even base vertex
beats odd base vertices, two even base vertices must beat one odd base
44
vertex in common. Suppose that wn is an odd base vertex. Then Wji beats
odd base vertices, none equal to wu, and Wn beats 2=1 odd base vertices,
thus there exists one odd base vertex that they both beat. Suppose now that
Wji is an odd base vertex. Suppose also that wu is an odd base vertex. If
T0 ~ Un for n > 7, any pair of odd base vertices is beaten by some odd base
vertex. If T0 is a 3cycle, then since Tb is wellcovered, there exists an even
base vertex which pairs any two odd base vertices. If n = 5, let the odd base
vertices be uu, u2i, u3i, u4i, u5].. By constructions given in 1., 2., and 3., there
exists an even base vertex which beats uu, v3i and v5i and an even base vertex
which beats u21, u31 and v5i. Note that Ta ~ Un, so the only pairs of odd base
vertices not dominated by a vertex in Un are v4i] u4i ,u2i; v2i ,^51; and u3i,
Vn. By construction, an even base vertex pairs each of these.
Suppose that wn is an even base vertex. If there exists an odd base
vertex which beats wn and Wji, we are done. Suppose there is no such odd
base vertex. Let A be the set of 2^ odd base vertices which beat Wji and
let B be the set of 2^ odd base vertices which beat wu. By our assumption,
AnB = 0. Since Ta is regular, Wji beats the set {Ta A}. Since wn beats
odd base vertices including Wj\, wn must beat the set {Ta B}. Note that
{Ta A} n {T0 B} = 0, thus no odd base vertex pairs wn and Wji. Since
Tb is wellcovered, there exists an even base vertex which pairs wn and Wj\.
45
Thus, Condition One is satisfied.
To check Condition Two, let wn beat Wji. Suppose wn is an even
base vertex. Note from above that every two even base vertices beat at least
one odd base vertex in common. Suppose that wn and Wj\ beat all odd
base vertices in common. Then an odd base vertex cannot distinguish wn and
Wji, which means that an even base vertex does. Suppose wn and w3i do not
beat all odd base vertices in common. Then there exists an odd base vertex
which is beaten by wn and which beats Wji. Suppose that Wji is an odd base
vertex. If there exists a base vertex which beats Wji and is beaten by wn, we
are done. Suppose there is no such vertex. Let A be the set of odd base
vertices which beat Wji and let B be the set of odd base vertices excluding
Wji which are beaten by wn By assumption, An B = 0. Since wji beats IL^
odd base vertices, Wji must beat the set {T0 A}. By a similar argument, wn
is beaten by the set {T0 B}. Since {T0 A} n {T0 B} = 0, there is no odd
base vertex which distinguishes wn and Wji, thus there is an even base vertex
which distinguishes wn and Wj\. Now suppose that wn is an odd base vertex.
Suppose that wji is also an odd base vertex. Since Ta is regular, every arc of
Ta is in a 3cycle by Lemma 2.5.1, so there exists an odd base vertex which
beats wn and is beaten by Wj\. Suppose that wji is an even base vertex. Since
wn is beaten by odd base vertices, and Wji beats odd base vertices,
46
there exists an odd base vertex which beats wn and is beaten by wj\. Thus.
Condition Two is satisfied.
2.6 The Main Result
Cho et al. [CKL] showed the following result, also given as Theorem
1.2.12.
Theorem 2.6.1 Let G E p*{m.n) Then the following are true:
(i) If m = 0,1, 2,4, then G is the domination graph of a regular tournament
if and only if n is odd and m + n > 7.
(ii) If m = 3 or m > 5 then G is the domination graph of a regular tourna
ment if and only if n is odd.
We may now expand this result to include graphs which have trivial paths. We
have seen the strategy to prove sufficiency in the previous sections. Necessity
must be shown case by case.
Lemma 2.6.2 G E p(0, 3) is not the domination graph of a regular tourna
ment if one of the odd paths is an isolated vertex.
47
Proof: Since Ta is regular, Ta is a 3cycle. Without loss of generality, let the
cycle be labeled Vu > v2i * > nu and let Q1 = uu be an isolated vertex.
Then uu and vzi are a dominant pair since Un beats black vertices of Q2 and
white vertices of Qz while u31 beats white vertices of Q2 and black vertices of
Qz
Lemma 2.6.3 G Â£ p(0,5) is not the domination graph of a regular tourna
ment if one of the odd paths is an isolated vertex.
Proof: Since Ta is regular, Ta ~ U5. Let the vertices be labeled as in figure
2.5. Without loss of generality, let Q1 = un be an isolated vertex. Then the
top black vertex of Qz and t>u are a dominant pair since the top black vertex
of Qz beats all black vertices in Q4 and Q5, and all white vertices in Q2 and
Qz while Vu beats the black vertices in Q2 and Qz and the white vertices in
Qa and Q5.
Lemma 2.6.4 G E p( 1,1) is not the domination graph of a regular tourna
ment if the odd path is an isolated vertex.
Proof: Note that uu and Un are a dominant pair since uu beats all white
vertices of Pi and uu beats all black vertices of Pi
48
Lemma 2.6.5 G E p( 1, 3) is not the domination graph of a regular tourna
ment if one of the odd paths is an isolated vertex.
Proof: Since T0 is regular, Ta is a 3cycLe. Let the cycle be labeled as in Lemma
2.6.2, and let Qi = be an isolated vertex. Suppose that beats Un If
ttu beats v2i, then nu and v3i are a dominant pair since un beats all black
vertices in Qo and all white vertices in Pi and Qz while v2i beats the black
vertices in Qz and Pl and the white vertices in Qz If uu does not beat v2u
then un beats n31 and it is easy to verify that t/n and the top black vertex of
Qz are a dominant pair. Suppose that does not beat t?u. Then it can be
verified that the top black vertex of Qz and are a dominant pair
Lemma 2.6.6 G E p(l, 5) is not the domination graph of a regular tourna
ment if one of the odd paths is an isolated vertex.
Proof: Note that T0 ~ Us, and use the vertex labeling as in Figure 2.5. With
out loss of generality, let Qi = be an isolated vertex. Note the following
cases. If Un beats u31 but does not beat then the top black vertex of Qz
and Vn are a dominant pair (note that the top black vertex of Q3 beats all
black vertices of Q4 and Q5, and all white vertices of Pi, Qz and Qz while
beats all black vertices of Pi, Qz and Qz and all white vertices of Q4 and Q5).
If Un beats v3i but does not beat uu, then if tiu beats U41, it is easy to show
49
that the top black vertex of Q4 and v2i are a dominant pair, and if uu does
not beat u41, then and u4i are a dominant pair. If uu does not beat u3i and
does beat uu, then n41 and the top black vertex of Q3 are a dominant pair. If
uLi does not beat uU) then and the top black vertex of Q4 are a dominant
pair.
Lemma 2.6.7 G E p(2,1) is not the domination graph of a regular tourna
ment if the odd path is an isolated vertex.
Proof: Without loss of generality, let beat n21. Note that and uu are a
dominant pair since un beats all white vertices of Pi and P2, while Uu beats
all black vertices of P4 and P2.
Lemma 2.6.8 G E p(2, 3) is not the domination graph of a regular tourna
ment ifT0 contains an isolated vertex.
Proof: Without loss of generality, let uu beat u21 Since T0 is regular, let
Vn > V21 > vzi > Vu. Also, let Vn be an isolated vertex. Suppose that
and U21 both beat uu. Then if uu beats V21 and u21 beats u3i., we have that
v2i and the top black vertex of Q3 are a dominant pair since u2i beats all black
vertices in Q2, Q3, and P2 and all white vertices in Pi, while the top black
vertex of Q3 beats all black vertices in Qi and P1,and all white vertices of
50
Q3 and P2. If uu and u2i both beat u2i, then is it easy to check that n2i and
u31 are a dominant pair. If un and u2\ both beat u31, then v2i and the top
black vertex of Q3 are a dominant pair. Now suppose that Un beats both nu
and v.21 Then uLi and u31 are a dominant pair. Suppose uu beats un and
vn beats u21. If u21 beats ua, then un and the top black vertex of Q2 are a
dominant pair. If u3i beats uu instead, then Vu and the top white vertex of
Pi are a dominant pair. Suppose U21 beats un and Un beats i!U. If v3i beats
U21, then uu and U31 are a dominant pair. If not, and i/2i beats U21, then uu
and u2i are a dominant pair.
Lemma 2.6.9 G p(4,1) is not the domination graph of a regular tourna
ment if the odd path is an isolated vertex.
Proof: Suppose that Te has a vertex un with outdegree 0 in Te. Then the
top white vertex of P, and the isolated vertex t?u are a dominant pair since
Un beats all white vertices in Tj and the top white vertex of Pi beats all black
vertices in Tb. Suppose that Te has a vertex u3i with outdegree 3 in Te. Then
Uji and un are a dominant pair since uu beats all white vertices of Tb and Uji
beats all black. If Te has no vertex of outdegree 0 or 3, then Te must have
score sequence (1,1,2,2). Without loss of generality, let uu and u21 be the
vertices of outdegree 2 in Te. Note that if Un does not beat u31 and u4i, then
51
u2i must. So suppose that u21 beats u3l and u4x. Without loss of generality,
let it31 beat u4i. Then u3i and the top white vertex of P2 are a dominant pair
since u34 beats all black vertices in P3 and P4, and all white vertices in Pi and
P2 while the top white vertex of P2 beats all black vertices in Pi and P2 and
all white vertices in P3 and P4.
We can now prove the main result.
Theorem 2.6.10 Let G 6 p(m, n) be a nontrivial graph. Then the following
are true:
(i) Ifm = 0,1,2,4, then G is the domination graph of a regular tournament
if and only if n is odd and m + n> 7.
(ii) If m = 3 or m > 5 then G is the domination graph of a regular tourna
ment if and only if n is odd.
Proof: To prove sufficiency, note that by the result of Cho et al., Theorem
2.6.1, if G E p*(m,n) then the conclusion follows. By Theorem 2.5.2, each
G 6 p*(m,n) which is the domination graph of a regular tournament has TJ,
which is wellcovered and satisfies Conditions One and Two. By Theorem 2.4.1,
since there exists such a T& for each G G p*(m, n) which is the domination graph
52
of a regular tournament, then the union of n odd and m even paths as above
is also the domination graph of a regular tournament. Necessity is proven by
applying Lemmas 2.6.2 2.6.9 above.
53
3. Path Tournaments
Recall that we defined a structure called a path tournament above.
We shall restrict the paths to be nontrivial, and restate the definition here.
Definition 3.0.11 Suppose that G is the union of n nontrivial paths, Pt, for
i = 1,2,.. n, n > 1, where P* has S{ vertices. Suppose that we construct a
tournament T such that G is a subgraph of dom{T) in the following way: Let
Ti be the induced subtournament on the vertices of Pi and let Tt ~ USi. The
arcs of T are determined in the following manner. Let Vi denote the bottom
vertex of each path P*. Properly color each path with black and white letting
each Vi be black. Then if an arc is directed from a vertex Xi in a path Pt to a
vertex Xj in path Py, and Xi is the same color as rcy, then all vertices of T will
beat vertices of Ty of the same color, and vertices of 7} will beat vertices of Ti
of different colors. The resulting tournament is called a path tournament.
If the domination graph of such a path tournament is known to be
connected, we can see that it cannot be a star or a caterpillar with a triple
54
end. This is because a union of nontrivial paths cannot be a subgraph of either
a caterpillar with a triple end, or a star. By 1.2.5, the domination graph of
a path tournament with nontrivial paths which is connected must be a spiked
odd cycle. In this chapter, we determine a class of spiked odd cycles that
are the domination graphs of path tournaments. This class has only one re
quirement. They are spiked odd cycles with only one pendant vertex per cycle
vertex. We shall determine if the criterion for path tournaments above is met
when it is assumed that the domination graph of the tournament is one of
these special spiked odd cycles. We shall verify that the subtoumament Ti
induced on each path Pi is isomorphic to USi. We shall also verify the above
arc structure between Ti s. That is, for any i and j, if there exists an arc
from black Xi to white Xj, then all black vertices in Ti beat all black vertices
in Tj\ all white vertices in T* beat all white vertices in T,; all black vertices
in Tj beat all white vertices in Ti; and all white vertices in 7} beat all black
vertices in 7"i. Similarly, if there exists an arc from a black vertex X{ to a
white vertex Xj, then all black vertices in Ti beat all white vertices in 7}; all
white vertices in Ti beat all black vertices in Tj; all black vertices in Tj beat all
black vertices in Ti; and all white vertices in 7} beat all white vertices in Ti.
These conditions meet the criterion for a tournament to be a path tournament.
55
I
I
}
i
i
i
i
t
i
i
i
!
Figure 3.1. If G is an Odd Spiked Cycle with One Pendant Vertex.
Theorem 3.0.12 rj G is a spiked. odd cycle with at most one pendant vertex
for each cycle vertex, then G is the domination graph of a path tournament.
Proof: Let G be a spiked odd cycle with at most one pendant vertex for each
cycle vertex. There are two cases to consider. For each case, we will determine
the paths Pt and we will let T{ denote the induced subtournament on the
vertices of P{. Suppose that G is a spiked odd cycle with n + 1 vertices and
only one pendant vertex. Let the vertex with the pendant be Xi, and let xx and
its pendant be denoted P2. Let the remaining vertices be Px. Properly color
each path as in Figure 3.1. Note that by Lemma 1.2.4, the subtournament on
the cycle vertices is isomorphic to Un, n the number of cycle vertices. Therefore,
Ti ~ Un1 We shall look at the coloring of these paths keeping in mind the
structure of Un to check other arcs. Note that the white vertex of T2 beats
all white vertices of Tx. By the same reason, the black vertices of Ti beat the
i
I
56
white vertex in T2. Using the arc structure from Lemma 1.2.4, we see that the
pendant vertex beats all black vertices in 7\, and all white vertices of 7\ beat
the pendant vertex (black in T2). This is the structure of a path tournament.
Figure 3.2. Example of the Decomposition of an Odd Spiked Cycle into
Paths.
Now suppose that G is an odd spiked cycle with k > 1 pendant
vertices. Separate the vertices of G into paths in the following manner. Choose
a pendant vertex, say vk, and follow the cycle against the direction of the arcs
to the next pendant vertex, say Include in Pk the vertex vk and the cycle
vertices up to, and not including, the next cycle vertex with a pendant vertex.
Repeat this process until there is one path for each pendant vertex. Properly
color the resulting paths as shown in Figure 3.2. Note that each of the base
vertices of a path is a pendant vertex in G. All others above the base vertices
form the cycle in G. Thus the induced subtournaments on vertices above base
57
vertices axe isomorphic to Uk for k equal to the number of vertices.
Now we will consider arcs between vertices in the same path. Let ui
be the base vertex of 7*. As noted, T{ is isomorphic to Uk for the k vertices
in Ti Vi. Consider Vi noting that it is a pendant vertex. Using Lemma 1.2.4,
and the coloring of the paths, we can see that in Ti, Vi beats all black vertices
above it in Pi, and all white vertices in Ti beat ut. This is consistent with
T ~ Uk+1 Thus the induced subtournament on each path is isomorphic to Uk
for k the number of vertices in the path.
Figure 3.3. Consider Paths without their Base Vertices.
To examine arcs between vertices in different paths, it is useful first
to consider the paths without their base vertices. When the arcs between all
other vertices are established, we shall then include the base vertices. Without
loss of generality, let i > j. Consider the connecting arc between Pt and Pj,
that is, the arc from Xi to Xj where xt is the white vertex in P, adjacent to vi:
and Xj is the top vertex of Py. There are two possibilities, either X, > xj or
58
Xj Xi. Suppose that X{ f Xj.
Figure 3.4. Case 1
Case 1 Suppose that both vertices are white. If we try to place the
vertices of the z'th and jth paths into the structure of Um we find that
we should position the vertices of the jth path above the vertices of the
zth path to have Xi > xj. Thus, all vertices in Ti V{ beat the same
color vertices in Tj vj, and all vertices in Tj vj beat vertices of a
different color in T{ Vi. Specifically, we have
(1) White vertices of Tj > black vertices of T{ v{.
(2) Black vertices of Tj Vj white vertices of T{.
(3) White vertices of Ti > white vertices of Tj.
(4) Black vertices of Ti Vi y black vertices of Tj Vj.
Now consider this case including Vi and Vj noting that they are pendant
vertices, and use Lemma 1.2.4. Since xt beats all white vertices of 7},
59
then all white vertices of Tj beat vi: and * Vj. Since all black vertices
of Tj Vj beat xt, then v{ beats all black vertices 7} Vj. Similarly, all
black vertices of Ti beat Vj and Vj beats all white vertices of T{.
Figure 3.5. Case 2
Case 2 Suppose that Xj is black. By the structure of Un, we should
position the vertices of the ith path above the vertices of the jth path.
Thus, vertices of Tj Vj beat vertices of Ti u, of the same color, and
vertices of Ti Vi beat vertices of Tj Vj of different colors. Consider
this case with the pendant vertices Vi and Vj. By Lemma 1.2.4, since
white vertices of Tj beat r,, then V{ beats all white vertices in Tj. Since
Xi beats all black vertices in Tj Vj: the black vertices in Tj Vj beat
Vi. Similarly, Vj beats the black vertices of Ti Vi and the white vertices
of Ti beat Vj. This also implies that Vj >
Now suppose that Xj > r,.
Ccise 3 Suppose that both vertices are white. Note that since i < j,
j 7^ i + 1. By the structure of Un, the vertices of the ith path should
x
60
*i 9 9
1 1
Figure 3.6. Case 3
be above the vertices of the jth path. Thus, all vertices of Ty Vj
beat vertices of Ty vi of the same color, and all vertices of Ty Vi
beat vertices of Ty Vj of different colors. Consider this case with the
pendant vertices uy and vj. Since the white vertices of 7} beat xy, we
have beats the white vertices of 7}, and Vj > vi. Since xi beats the
black vertices of Ty uy, the black vertices in Ty Vj beat V{. Similarly,
Vj beats all black vertices of Ty, and the white vertices of Ty beat Vj.
Case 4 Suppose that Xj is black. Then by the structure of Un, the
vertices of the jth path should be above vertices of the ith. path. Thus,
vertices of Ty uy beat vertices of Ty of different colors, and the
vertices of 7} Vi beat vertices of Ty Vj of the same color. Consider
this case with the pendant vertices Vi and Vj. Since the black vertices of
Ty Vj beat X{, we have ut beats the black vertices of 7} Vj. Since Xi
beats the white vertices of Ty, the white vertices of T, beat Vi Similarly,
Vj beats the white vertices of Ty, uy > ny, and the black vertices of Ty
61
Figure 3.7. Case 4
beat vj.
In each case, the arc structure described follows the definition of arcs in a path
tournament, thus G is the domination graph of a path tournament.
62
4. DominationCompliance Graphs
4.1 Introduction
Recall that the definition of a dominationcompliance graph of a tour
nament T is a graph on the vertex set of T with edges wherever there are
edges in either dom(T) or com(T) Edges in dom(T) are between vertices
which when considered together, beat all other vertices. Edges in com(T) are
between vertices that do not beat any vertex in common. So we see that edges
in dom{T) may also be in com(T) To determine exactly what domination
compliance graphs might look like, it is useful to first consider a specific dom
ination graph. If we have dom(T) then we can use what we know about the
structure of the arcs in T to determine edges in com(T) We have seen several
results that can be used in this way. It is interesting to note that the structure
given in these results is sufficient to determine all edges in com(T) thus all
edges in DC(T) In addition to determining edges of DC(T) we shall look
at certain graph theoretic aspects of these graphs, such as chromatic number,
clique size, and planarity.
63
Dominationcompliance graphs are examined in two parts. This chap
ter comprises the first part, and is about dominationcompliance graphs of
tournaments whose domination graph is made up of a relatively small number
of nontrivial components (one, two, or three). The second part is Chapter
5, and pertains to dominationcompliance graphs of tournaments whose dom
ination graph is made up of more than three components. This division is
necessary, since domination graphs with less than four components have spe
cific structural considerations, such as triple ends, which can require case by
case examination.
The results that we shall use to determine which edges are in com(T) given
a specific type of domination graph are the following. Recall that if dom(T) is
a spiked odd cycle, Lemma 1.2.4 gives us the following structure for T between
cycle vertices remand pendant sets of vertices, Vf.
X;  Xj
If dom(T) is a caterpillar, we have the general structure of D(T) (Figure 4.1)
from Proposition 1.2.2. Additional results show that if we two color this cater
pillar, we have that arcs pointing to the right are between vertices of different
colors, and arcs pointing to the left are between vertices of the same color. We
64
will also use Lemma 1.2.6 where arcs in T between caterpillars of dom(T) are
described.
/Y7\ 7TA
Figure 4.1. The Directed Domination Graph for a General Caterpillar.
The following lemma is the result of initial work on domination
compliance graphs, and appears in [JL97]. Let d$(x) denote the outdegree
in the subtournament on the vertices of set S of vertex x.
Lemma 4.1.1 ([JL97]) Let T be a tournament whose domination graph is an
odd spiked cycle without isolated vertices. The following are the only possible
edges in com(T) :
i) Let v E Vi. Then [xi,v] E com(T) iff dy.(v)=0.
ii) Let v E Vi and w E Vj. Then [v,w\ E com(T) iff j = i + 1 mod(k) and
d+(w) = 0.
Hi) [xi:Xj] E com(T) iff j = i + 1 mod{k) and Vi 0.
iv) Let v E Vi. Then [u, xf\ E com(T) iff j = i + 2 mod(k) and Kk = 0
65
We begin this chapter with an examination of the chromatic num
ber and planarity of these graphs, and continue by looking at domination
compliance graphs of tournaments with other connected domination graphs.
4.2 DominationCompliance Graphs of
Tournaments with Connected
Domination Graphs
An examination of examples of dominationcompliance graphs whose
domination graph is an odd spiked cycle indicates that they must be planar
and are 3colorable. There are two types of edges appearing in com(T) that
are not in dom{T) These are edges between neighboring pendant vertices, and
edges between a pendant vertex and a cycle vertex if they have a pendantless
cycle vertex between them.
Theorem 4.2.1 Let T be a tournament whose domination graph is an odd
spiked cycle without isolated vertices. Then the chromatic number of DC (T) is
three.
Proof: Note that the chromatic number of domifl) is three. Also, one may
color dom(T) with only one vertex having the third color (say black). The
edges [a;x, u], v 6 V* and [xf, a;t+1] are in dom(T) The possible edges that we
66
Figure 4.2. An Example of the DominationCompliance Graph of a Tourna
ment Whose Domination Graph is an Odd Spiked Cycle.
I
i
67
will add to dom(T) to form DC(T) are [v,Xj\, where v Â£ Vj and i ^ j; and
[l?, w\, where v Â£ Vi} w Â£ Vj and i ^ j.
Consider DC(T) Suppose that there is an edge \v,Xj], where v Â£ Vi
and i ^ j in DC(T) Then j = i 2 mod{k) and Vi+x = 0. Color Xj black.
Properly color the remaining vertices with two colors where Vj and have
different colors. This will be a proper 3coloring of DC{T) .
Now suppose there is no edge [u, Xj] in DC(T) where v Â£ V and i ^ j.
Then either T = Uk and DC(T) is the cycle Ck, which is 3colorable, or each
Xi has pendant vertices in DC(T) Assume the latter, and suppose that there
exists a Vj such that no v Â£ V has dy.{v) = 0. Let X{ be colored black and prop
erly 2color the remaining vertices such that Vj and K+i or Vj_i are different
colors, and and Xii are different colors. This will be a proper 3coloring
of DC(T) Suppose that every Vj has a vertex v such that dy.(v) = 0. Then
let any one xt be black and let Vi+i be black. Properly 2color the remaining
vertices so that Vj and V^i are different colors. This is a proper 3coloring of
DC(T) m
By results in [JL98], if the domination graph of a tournament is a
star, then there are two general structures for T. The first is shown in Figure
4.3 where arcs between pendant vertices are arbitrary. Note that V is the set
68
of pendant vertices to x. Let the family of tournaments with this structure
be r. The second family of tournaments with staxs as domination graphs are
tournaments with one transmitter, or a vertex which beats all others. Let this
family be A.
y x
Figure 4.3. Tournaments in F
Theorem. 4.2.2 If T Â£ T, then DC(T) is as in Figure 44
Proof: Note that dom(T) is a star with the vertex x at its center. There are no
edges in com(T) between vertices of V since they all beat vertex y. Also, each
vertex of V is in a compliant pair with y since they beat nothing in common.
If Te A, we have the following useful description of DC(T) .
Theorem 4.2.3 If T Â£ A and T' is the subtoumament on the pendant vertices
of T, then DC(T) = dom(T) U com(T') .
Proof: Note that if the edge uv Â£ E{dom{T) ), then uv Â£ E(DC(T) ). Suppose
that uv Â£ E(com(T ') ). Then for any z Â£ T ', either 2 > u or z > v. Thus,
69
y
X
uv G E{com{T) ), which implies uv G E{DC{T) ).
Now let uv E{DC{T) ). If u or u is the vertex x, then uv G
i?(dom(T) ). So assume u and v are in T '. Since u and v are not a dom
inant pair in T. uv G E(com(T) ), thus uv G Â£'(com(T ') ).
Using these theorems, we have the following result about chromatic number.
Corollary 4.2.4 If T is a tournament whose domination graph is a star, then
x(DC{T)) < 4.
Proof: If T G r, then DC{T) is 3colorable. Suppose that T G A. Note that
com(T ') is an odd spiked cycle or a forest of caterpillars. Since DC(fÂ£) =
dom(T) U com(T ') we have that ;\;(.DC(T) ) < 4, and achieves four exactly
when com(T ') is an oddspiked cycle with or without isolated vertices.
70
There is one subset of tournaments in A whose dominationcompliance
graph contains a 4clique. We shall see that this is the only family of tourna
ments with this characteristic. These tournaments are stars with the following
structure (see Figure 4.5).
Definition 4.2.5 Q is the set of tournaments that have one transmitter, and
at least one 3cycle among the remaining vertices with the following property:
no two vertices of the 3cycle beat a vertex in common. The other arcs are
arbitrary.
Figure 4.5. A General Tsfl (excluding arcs between the 3cycle and other
pendant vertices) and DC(T) .
Theorem 4.2.6 Let T be a tournament whose domination graph has nontrivial
T
DC(T)
components. Then DC(T) contains a 4clique if and only if T E Q.
71
We shall defer the proof of this theorem until the end of the chapter, since it
requires some knowledge of the structure of dominationcompliance graphs of
tournaments whose domination graph is a caterpillar, or a union of caterpillars.
Note that each of the dominationcompliance graphs of tournaments whose
domination graph is a star is planar.
The remaining connected domination graphs are single caterpillars.
We will assume that these are nontrivial, and we will use the fact that tourna
ments whose domination graphs are stars have been handled above. Thus, a
caterpillar in this section must have at least two spine vertices. By results in
[FLMR99], a caterpillar is the domination graph of a tournament if and only if
it has a triple end. Let xi, ...,Xk be the spine vertices, and Vi the pendant set
adjacent to x^. Any pendant set except 14 can be empty, and 14 must contain
at least three vertices. We shall 2color D(T) letting xi be black. Then by
results in [JL98], all arcs of T not within a pendant set are oriented to the
right between vertices of different colors, and to the left between vertices of
the same color. Also, arcs within clusters are arbitrary, except for those in 14
The subtournament on 14 can have no transmitter. Dominationcompliance
graphs where dom(T) is a caterpillar as defined above are characterized by the
following lemma.
72
Lemma 4.2.7 Let T be a tournament whose domination graph is a caterpillar.
The following are the only possible edges in com(T) :
i) Spine & Spine: [xj, xy] E com(T) iff j = i + 1 and Vi = 0.
ii) Spine & its Pendant: Let v E V.. Then [xz, u] E com(T) iff (v) = 0.
Hi] Pendant & Pendant: Let v E Vi, w E Vj. Then [w, tu] E com(T) iff j =
i + 1 and dfr.(w) =0 or i = 1, j = n, and n is odd.
iv) Spine & Other Pendant: Letv E V, i ^ j. Then [xj,v\ E com(T) iff j =
l, i = n, and n is even; j = 2, i = n, n is odd and Vi = 0; j 7^ 1 or 2,
j = i + 2 and K'+i = 0
Proof: Let T be a tournament whose domination graph is a caterpillar.
Properly 2color T. Note that there is no edge between vertices in one pendant
set Vi in com(T) since two vertices in Vi beat any Xj which beats Xj.
i) Spine Sc Spine: Suppose that j = i + 1 and V{ = 0. Since x{ and
Xj are adjacent in dom(T) they have different colors in a proper 2
coloring of dom{T) Therefore in T, Xi beats all vertices that Xj does
not in each direction with the exception of those in Vi, which both
beat. So since Vi = 0, [:Xi,Xj] E com(T) Suppose [xi,xf\ E com(T) .
Note that if x, and Xj are the same color then they beat the same spine
vertices to the left or right of both. If there are no spine vertices to
the left or right of both, then Xj and Xj are end vertices and both beat
73
Vn, which is nonempty since it is the triple end. So suppose that X{
and Xj have different colors and i < j. If j ^ i + 1 then both Xi and
Xj beat Xi+i. So j = i 41. But note that both and xj beat VI, so
since [xi, xj] E cora(T) Vi = 0.
ii) Spine 8c its Pendant: Let v E V{. Then and v have different
colors, so Xi beats all vertices v does not in each direction in T. If
dy_(v) = 0, v does not beat any vertex in common with xi: so [x{, u] E
com(T) If dy.(v) 0, both Xi and v beat a common vertex in T, so
[x{, u] Â£ com(T) .
iii) Pendant 8c Pendant: Suppose j = i 4 1, v 6 V* w G Vj, and
dy.(w) = 0. By the structure given in Figure 1.7 and that in this
figure, every arc to the right is between vertices with different colors,
and to the left between vertices with the same colors, we see that v and
w do not beat a common vertex in T unless both beat a vertex in Vj,
which is impossible by assumption. Thus [u, iu] Â£ com(T) Suppose
[u, w] G com(T) and i < j. If v and w have the same color, then by the
argument of i), they both beat X\ or Vn in T unless i = 1 and j = n, n
is odd, and dy^v) =0. If v and w have different colors but j # i + 1,
then both beat xji in T, a contradiction. Thus, j = i + 1. Note that
v beats all vertices in Vj so both v and w beat the same vertex unless
74
d^.(w) = 0.
iv) Spine &: Other Pendant: Suppose j = 1, v E Ku and n is even.
Then Xj and v have the same color and beat nothing in common in T,
so [xj,v] E com(T) Suppose j 2, v E Vn and n is odd. Then Xj
and v only beat vertices of V[ in common in T, so if V[ = 0, [xv] E
com(T) Now suppose j ^ 1 or 2, and j = i f 2. Then Xj and v have
different colors and only beat the vertices of Vi+i in common in T. So
if K'+i = 0, ^ com(T) Suppose that [xj,v] E com(T) v E K
If Xj and v have the same color, then they beat a common vertex in T
unless they are on the ends of the caterpillar (j = 1, i = n or j = n,
i = 1) or j = 2, i = n and V[ = 0. Note that if i = 1 and j = n, both
beat Vn in T. Also, if i = 2 and j = n, both beat Xi in T. Thus if xj
and v have the same color, j = 1 and i = n or j = 2 i = n and Vj. = 0.
Suppose that Xj and v are of different colors. If j ^ i + 2, and j > i,
then xj and v beat rI+2 in T. If j ^ i+2 and j < i, then both beat
in T. Thus, j = i+2. Note that Xj and v beat K+i unless Vi+i =0.
Figure 4.6 shows examples of dominationcompliance graphs charac
terized by the above lemma. They are all planar. Note that if one 2colors the
domination graph of T, all edges within the caterpillar, or between vertices not
75
j
!
i
i
Figure 4.6. Two Examples of DominationCompliance Graphs Where
dom(T) is a Caterpillar.
I

I
1
76
l
both at the ends of the caterpillar, are between vertices of different colors. We
call edges between vertices at the ends of the caterpillar end edges. Observe
that edges in DC(T) but not in dom{T) are between pendant and pendant
vertices (part iii)) or spine and other pendant vertices (part iv)) only.
Theorem 4.2.8 Let T be a tournament whose domination graph is a caterpil
lar. Then x(DC(T)) < 3.
Proof: Properly 2color dom(T) with black and white letting be black.
The edges in com(T) which are not in dom(T) and are between vertices of
different colors will not affect the proper 2coloring. The only possible edges
in com(T) that are between vertices of the same color are end edges:
[v, zu], v Â£ Vi, w Â£ Vn, n odd, and dy^v) = 0.
[ri, v\, v Â£ Vn, n even.
[xo, u], v Â£ Vn, n odd.
So suppose that n is odd. If Vi ^ 0 and there is a v Â£ Vi such that dy^v) 0,
then for w Â£ Vn, [u,io] Â£ com(T) A proper 3coloring of DC(T) is achieved
by coloring all vertices of VJ. the third color. Now if there is no such v Â£ Vi,
we may 2color DC(T) If V\ = 0, and if v Â£ Vn, then [x2, v] Â£ com(T) A
proper 3coloring of DC(T) is achieved if we color x^ the third color. Suppose
that n is even. Then if v Â£ Vn, then [a;i,u] Â£ com(T) A proper 3coloring of
77
DC(T) is achieved if we color Xi the third color.
4.3 DominationCompliance Graphs of
Tournaments Whose Domination Graph is
the Union of Two Nontrivial Caterpillars
For two nontrivial caterpillars, we shall use the following notation.
Let xu, i = 1, 2,..., n be the spine vertices of caterpillar one (C\), and let x2i,
i = 1, 2,..., m be the spine vertices of caterpillar two {C2). Let Ky denote the
set of pendant vertices in caterpillar i (=1, 2) adjacent to vertex Without
loss of generality, we will always let rru beat x2\. Recall from Theorem 1.2.5
that if dom(T) is the union of two nontrivial caterpillars, then they must both
have triple ends. These triple ends are adjacent to Xin and x2m. We will
consider Kij a caterpillar with a triple end if j > 3 and it is not explicitly
stated otherwise.
Most of the arc structure of T can be determined using Lemma 1.2.6.
In particular, if we 2color the two caterpillars so that xu and x2i are black,
and place Ci above C2, then all of the arcs directed downwards between the
two caterpillars are between vertices of the same color, and all arcs directed
78
upwards are between vertices of different colors. The arcs within each cater
pillar are as in Section 4.2. We may now characterize all edges in com(T) .
Lemma 4.3.1 Let T be a tournament whose domination graph is made up of
the union of two nontrivial caterpillars. The following are the only edges in
com(T) .
1. Edges in each caterpillar: all edges in Lemma 4.2.7 except the end edges.
2. Edges between the two caterpillars:
i) Spine & Pendant: Let v E Vij. Then [xm,v] E com(T) iff one of the
following occurs:
a. k = l, l = 1, i = 2, j = m, and m is odd
b. k = 1, l 2, i = 2, j = m, Vn 0, and m is even
c. k 2, l = 1, i = 1, j n, and n is even.
ii) Pendant & Pendant: Letv E Vij, w E 14;. Then [v, w] E com(T) iff one
of the following occurs:
a. i = j = 1, k = 2, l = m, dy^v) = 0 and m is even
b. i = 1, j = n, k = 2, l = 1, dy2l(w) = 0, and n and m are odd.
Proof: Let T be as stated and 2color the caterpillars as specified above. Note
that all edges from Lemma 4.2.7 in each individual caterpillar that are between
vertices of different colors exist in the two caterpillar case. The edges between
79
vertices of the same color (the end edges) no longer exist since vertices of the
same color in one caterpillar beat the same color set of vertices in the second
caterpillar. Now consider edges between the two caterpillars. Note that there
are no edges of the form [rcn, x2j] between spine vertices since each caterpillar
has a triple end. If xu and x2j are both black, then in T, xu must beat no
white vertex in C\, which is impossible. If xu and x2j are both white, then in
T, xu must beat no black vertex in C\, which is impossible. If ilt and x2j have
different colors, the same conclusions hold if one examines the vertex x2y.
i) Spine & Pendant: Suppose that m is odd. Then note that if v E T4m,
then [iu,d] E com(T) since in beats all white vertices of Ci in T and
all black vertices of C2 in T, while v beats all white vertices of C2 in
T and all black vertices of Ci in T. If n is even and v E Vln, then
[x2i,v\ E com(T) since x21 beats white vertices of both C\ and C2 in
T while v beats all black vertices in T. Suppose that m is even. Note
that X\2 beats all black vertices except in of C\ in T plus all vertices
of Vn and the white vertices of C2. The vertices in V2m beat the black
vertices except x2m of C2 and the white vertices of C\ in T. Thus, if
Vn = 0 and v E V2m, then [x2\,v\ E com(T) Suppose that v E V2j,
and [rci,, v] E com(T) If v and xu have the same color, i 7^ 1, 2, and
j 7^ m, then both v and beat Vin or xu+1 in T. If v and xu have
80
different colors, then they both beat Vim or x2m in T. Thus, i = 1 or
2 and j = m. If m is even, in and v beat the black vertices of C2 in
T. If m is odd, Xu and v beat the white vertices of C2 in. T. Suppose
that v E Vi j and [x2{, u] E com(T) If i ^ 1, j 7^ n, and v and x2i are
the same color, then they both beat either xln or Vln in T. If x2i and v
have different colors, then they both beat V2m or x2m in T. Thus, i 1
and j = n. If n is odd, 2:21 and V2n beat all white vertices of C2 in T.
The conclusion follows.
ii) Pendant Pendant: Note that all vertices of Vu beat all black ver
tices of C\ except for Xu in T, and all white vertices of C2 in T. If m
is even, all vertices of V2m beat the black vertices of C2 and the white
vertices of C\ in T. Thus, if there is a v E Vu such that dyn(v) = 0
and if w E V2rn, then [u,u;] E com(T) Note that all vertices of V2i
beat the black vertices of Ci and C2 except x2\ in T. If n is odd, the
vertices of uln beat all white vertices of CL and C2 in T. Thus, if there
is a v E V2X such that dy^ (v) = 0 and if w E Vln, then [v, w] E com(T) .
Suppose that [u, w] E com(T) v E Vu and w E V2j where i ^ 1 or
n and j ^ 1 or m. Then if v and w have the same color, they both
beat x2i (if black) in T, or x22 (if white) in T. If v and w have different
colors, then they both beat either rn or Â£12 in T. Thus i = 1 or n and
81
j = 1 or m. Note if i = 1 and j = 1 both v and w beat the blacks
of Ci in T. If i = n and j = m, then v and w both beat all blacks or
whites of Ci in T if they are of the same color, and all blacks or whites
of C2 in T if they are of different colors. So i = 1 and j = m or i = n
and j = 1. Note that if m is odd or n is even, v and w beat all blacks
of Ci in T. If m is even, the vertices of V2m beat the vertices of V'u
and if n is odd, the vertices of Vin beat the vertices of V2i. Thus, the
conclusion follows.
Figure 4.7. One Example of a DominationCompliance Graph Where
dom(T) is Two Caterpillars.
Note that end edges are not present in DC(T) We shall call edges
between two caterpillars connecting edges. These between edges may be
82
considered a set of connecting edges if a pendant set with more than one
vertex comprises an endpoint. This will not affect questions of planarity, and
a connecting set of edges will be drawn and referred to as a single edge for sim
plicity. If one properly 2colors the domination graph, then connecting edges
can be between vertices of the same color in this coloring.
Theorem 4.3.2 Let T be a tournament whose domination graph is the union
of two nontrivial caterpillars. Then x(DC(T) )< 3.
Proof: Properly color dom(T) with black and white, letting in and Â£21 be
black. The edges in com(T) which are not in dom{T) but are between ver
tices of different color will not affect the proper coloring. The only edges in
com(T) that are between vertices of the same color are connecting edges: [u, w\
where v Â£ Vln and w Â£ V2l and n is odd; and [x2i,n] where v Â£ V\n and n
is even. Note that no dominationcompliance graph will have both types of
edges. If n is odd, color the vertices of V21 the third color, retaining the proper
2coloring. This will give a proper 3coloring. If V21 = 0, then DC(T) is 2
colorable. If n is even, color x2i the third color retaining the 2coloring. This
will give a proper 3coloring.
83
4.4 DominationCompliance Graphs of
Tournaments Whose Domination Graph is the
Union of Three Nontrivial Caterpillars
We shall use the same notation as in Section 4.3 letting Ci have n
spine vertices, Ci have m spine vertices, and C3 have p spine vertices. The arc
structure in T between any of the two caterpillars is the same as in Section
4.3, and the arc structure of T within each caterpillar is the same as in Section
4.2. From results in [FGL+a], we have the following three possibilities for
tournaments with domination graphs made up of three nontrivial caterpillars:
1. Ci, C2, and C3 all have triple ends and none is ivii3. Then in T, we
have 2:11 y X21 ^ Â£31 ^ xn.
2. Ci has a triple end, C2 and C3 are K^. Then in T, in > X31,
xn + x2i, and 2:21 > ^31
3. Ci is Kitz, C2 and C3 are not, but have triple ends. Then in T, X21 >
Xn, x2i ) 2:31, and x3i > xu.
It is convenient to handle each of these cases separately.
Lemma 4.4.1 Let T be a tournament whose domination graph is made up of
three nontrivial caterpillars each with a triple end and none Kx,z Then the
only edges in com(T) are the following:
84
1. Edges in each caterpillar: All edges in Lemma 42.7 except the end edges.
2. Edges connecting caterpillars:
i.) Spine & Pendant: Let v Â£ Vki Then [xij,v] Â£ com(T) iff this edge
is one of the following:
a. [x2i, w] if v Â£ Vin and n is even
b. [x22,v\ if v Â£ Vln, n odd, and V21 = 0
c. [x3i,u] if v Â£ V2m and nz is even
d. [xz2,v] if v Â£ V2m, 771 odd, and V31 = 0
e. [rru,*;] if v Â£ V3p and p is even
f. [xi2,v] if v Â£ V3p, p odd, and Vu = 0.
ii.) Pendant & Pendant: Let v Â£ Vij and w Â£ V^. Then [v,w\ Â£
com(T) iff this edge is one of the following:
a. [y, w] where v Â£ Vin, w Â£ V21, dy^w) = 0 and n is odd
b. [y, w] where v Â£ Vzm, w Â£ V31, dy3l(w) = 0 and m is odd
c. [y, 7y] where v Â£ V3p, w Â£ Vu, dy^iw) = 0, and p is odd.
Proof: Note that the edges within each caterpillar in com(T) must be
the same edges as in the single caterpillar case (Lemma 4.2.7) without the end
edges. Two color dom(T) with black and white, letting xn be black. As noted,
we have rcn. X21 * x3i $ rrn in T. If there was a connecting edge between
two caterpillars in com(T) it could not be between vertices of different colors,
85
I
since two vertices of different colors would beat the same color set of vertices
in the third caterpillar. The above list of edges are all of the edges in the two
i
i
j caterpillar case between vertices of the same color. Since the vertices listed are
i
 of the same color, they beat disjoint sets of vertices in T, thus these edges are

 in cora(T) .
Figure 4.8. Example of a DominationCompliance Graph Where dom{T) is
the Union of Three Caterpillars as in Lemma 4.2. (The dotted arcs are in T).
Lemma 4.4.2 Let T be a tournament whose domination graph is made up of
three caterpillars, C\ with a triple end, Co and C$ being K\tz Then the only
edges in com(T) are the following:
1. Edges in each caterpillar: All edges in Lemma f.2.7 except the end edges.
2. Edges connecting caterpillars:
i.) Spine & Pendant: Let v E Vkj Then [xij,v] E com(T) iff this edge
is one of the following:
86
i
a. [xu,u], v G V2Tn
b. [x2l,v\, v G V3p
c. [0:31, u], v G Vin, and n is even.
ii.) Pendant & Pendant: Let v G Vij, and w G V^i Then \v,vj\ G
com(T) iff this edge is [v.w], v G V31, w G V\n, dy3l(v) = 0, and n
is odd.
Proof: Note as in the previous lemma, edges within caterpillars are
the same as in the single caterpillar case (Lemma 4.2.7) without the end edges.
Two color dom{T) letting xn be black. As noted above, we have a:L1 > x2i,
X31, and X21 > x3i in T. We see by the same logic as the previous lemma that
connecting edges between C\ and C2 and between C2 and C3 must be between
vertices of different colors and between C\ and C3, they must be between ver
tices of the same color. The edges listed are exactly those edges from the two
caterpillar case.
Lemma 4.4.3 Let T be a tournament whose domination graph is made up of
three caterpillars, C\ being Ki<3, and C2 and C3 having triple ends. Then the
only edges in com(T) are the following:
1. Edges in each caterpillar: All edges in Lemma 42.7 except the end edges.
2. Edges connecting caterpillars:
87
i.) Spine & Pendant: Let v E 14;. Then [xij,v] E com(T) iff this edge
is one of the following:
a. [xn,u], v E V2m and m is even
b. [x2i,v], v E Vzp and p is odd
c. [x22, v]> v Vzpt V21 = 0, and p is even
d. [x31,u], v E Vin.
ii.J Pendant & Pendant: Letv E Vij, w E 14;. Then [v,w\ E com(T) iff this
edge is one of the following:
a. [*;, w], v E V2i, w E V3p, dy2i(v) = 0, and p is even
b. [v,w\, v E Vn, w E V2m, dy^iv) = 0, and m is odd.
Proof: As in the previous two lemmas, edges within each caterpillar
are the same as in the single caterpillar case (Lemma 4.2.7) without end edges.
Two color dom(T) letting x,x be black. We know that x2i * in, x31 and
X31 Xu in T. Thus the connecting edges in com(T) between Ci and C2 must
be between vertices of the same color, while connecting edges between C\ and
Cz, and C2 and C3 are between vertices of different colors. The edges listed
are exactly the edges between two caterpillars with these properties.
As with the one and two caterpillar cases, we can always 3color
DC(T) if dom{T) is made up of three caterpillars.
88
Theorem. 4.4.4 Let T be a tournament whose domination graph is the union
of three nontrivial caterpillars. Then x{DC(T) ) < 3.
Proof: Properly 2color dom(T) with black and white, letting Xu be black. The
edges in com(T) which are between vertices of different colors will not affect
the 2coloring.
Case 1: If dom(T) is as in Lemma 4.4.1, the only edges in com(T) be
tween vertices of the same color are connecting edges. Note from Lemma
4.3.1 that there is only one set of possible connecting edges between any
two caterpillars. If one colors every vertex of each triple end (ie, Vln,
V2m, and V^p) the third color, then DC{T) is properly 3colored. If n,
m, and p are odd and there is no vertex with outdegree 0 in any of the
triple ends, then DC(T) is 2colorable.
Case 2: If dom{T) is as in Lemma 4.4.2, then the only edges between
vertices of the same color in com(T) are [x31,u], v E V\n, n even, and
[u, to], v E V^x, w E Vin. If one colors the vertices of Vin the third color,
then DC(T) is properly 3colored. Note that if n is odd and there is no
vertex with outdegree 0 in V2i, then DC(T) is 2colorable.
Case 3: If dom(T) is as in Lemma 4.4.3, the only edges between vertices
of the same color in com(T) are [rrn, u], v E Vi m with m even, and [u, to],
89
