Citation
Domination and matrix properties in tournaments and generalized tournaments

Material Information

Title:
Domination and matrix properties in tournaments and generalized tournaments
Creator:
Stewart, Dustin J
Publication Date:
Language:
English
Physical Description:
x, 202 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Domination (Graph theory) ( lcsh )
Tournaments (Graph theory) ( lcsh )
Matrices ( lcsh )
Domination (Graph theory) ( fast )
Matrices ( fast )
Tournaments (Graph theory) ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 198-202).
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Dustin J. Stewart.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
62775256 ( OCLC )
ocm62775256
Classification:
LD1193.L622 2005d S73 ( lcc )

Full Text
DOMINATION AND MATRIX PROPERTIES IN TOURNAMENTS AND
GENERALIZED TOURNAMENTS
by
Dustin J. Stewart
B.S. Mathematics, University of the Pacific, 2001
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


This thesis for the Doctor of Philosophy
degree by
Dustin J. Stewart
has been approved
by
Ellen Gethner
Date
K. Brooks Reid


Stewart, Dustin J. (Ph.D., Applied Mathematics)
Domination and Matrix Properties in Tournaments and Generalized Tourna-
ments
Thesis directed by Professor J. Richard Lundgren
ABSTRACT
In this thesis we examine several matrix properties of tournament matrices.
In particular we look at how domination and related parameters in tournaments
affect these properties in the corresponding matrices. We begin by examin-
ing when a tournament can support an orthogonal matrix. To do so, we first
look at the necessary condition of quadrangularity in tournaments. We classify
tournaments with given properties which meet this necessary condition. We
show how domination effects quadrangularity in regular tournaments and tour-
naments with certain minimum degrees. We also determine for exactly which
orders a quadrangular tournament exists.
In chapter 3, we examine the stronger necessary condition for a digraph to
support an orthogonal matrix of strong quadrangularity. We construct a class
of tournaments which meet this condition. We also show that the 3-cycle is
the unique tournament on ten or fewer vertices which supports an orthogonal
matrix, and discuss a search conducted for a tournament matrix which supports
an orthogonal matrix. In the following chapter we look at which tournament
matrices are fully indecomposable and which are separable, as these properties
m


are related to a necessary condition for a (0, l)-matrix to support an orthogonal
matrix. We use our classification to derive a number of matrix and graph theo-
retic corollaries. As the domination graphs of tournaments play a central role in
our classification of separable tournament matrices, we classify the domination
graphs of complete paired comparison digraphs in chapter 5.
Finally, we examine the Boolean, non-negative integer and real ranks of
tournament matrices. We find new bounds for the Boolean rank using results
on dominating sets and related parameters. We determine, for the first time, a
class of tournament matrices in which the real rank is less than the Boolean rank.
We also determine a set theoretic dual to the problem of finding the Boolean row
rank of a tournament matrix, and give some results and conjectures related to
the problem of finding the minimum Boolean rank over all tournament matrices
of order n.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
IV


DEDICATION
For Melissa, for my family, and for Albion.


ACKNOWLEDGMENT
There are several people in my life that deserve thanks for bringing me to this
point. First, I want to thank my advisor, J. Richard Lundgren. Rich has made
many things possible for me in the last four years, and has taught me a great
deal about mathematics, teaching and life as an academic. I also owe many
thanks my thesis committee Rich, Brooks Reid, Stan Payne, Bill Cherowitzo
and Ellen Gethner. Each have been a great help and influence in their own way.
Thank you as well to the faculty who I had the chance to work with at UCD.
I want to thank the graduate committee and the mathematics department
for the financial support, teaching assistantships and fellowships. None of this
would have been possible without it. Thank you to Marcia Kelly, Liz Lhotka
and Jennifer Thurston. I would not have survived without them. Thanks also
to Lynn Bennethum and Bruce MacMillan for their help and advice on teaching.
My thanks to the UOP mathematics department for preparing me for grad-
uate school, especially to Sarah Merz, Coburn Ward and Vincent Panico. I also
want to thank Sarah for introducing me to graph theory and starting me off
researching in the field.
I am also thankful for my fellow graduate students who have helped me
through the last few years with teaching and research ideas, or by just being
a good distraction. For this, I am happy to thank, among others, Nate, Art,
Ryan, Kevin, Flink, Rob, Tessa, Hank, Sarah and Chris. Special thanks to my
two amazing officemates, Jenny Cowel and Dave Brown, and to Carey Jenkins
and Jeff Matsuo, helpful friends and great fishermen.
I want to thank my parents for everything they have done for me. Especially
for when they sent me to college and started this whole process.
Finally, I want to thank Melissa Cyfers for all her love and support. I could
not have asked for more.


CONTENTS
Figures ........................................................... ix
1. Introduction...................................................... 1
1.1 Background........................................................ 1
1.2 Graph and digraph basics.......................................... 4
1.3 Tournament basics................................................ 11
1.4 Domination basics ............................................... 19
1.5 Matrix basics.................................................... 23
2. Quadrangular Tournaments ........................................ 27
2.1 Definitions and background....................................... 27
2.2 Tournaments which are not strongly connected .................... 29
2.3 Tournaments with given minimum degrees........................... 34
2.4 Regular and rotational tournaments............................... 38
2.5 Known orders of quadrangular tournaments......................... 43
3. Strongly Quadrangluar Tournaments................................ 55
3.1 Definitions and background....................................... 55
3.2 A class of strongly quadrangular tournaments..................... 57
3.3 Nonexistence and searches........................................ 62
4. Fully Indecomposable Tournament Matrices......................... 69
4.1 Definitions and background ...................................... 69
4.2 Fully indecomposable matrices.................................... 72
vii


4.3 Separable matrices............................................... 74
4.4 Corollaries...................................................... 77
5. Domination Graphs of Complete Paired Comparison Digraphs .... 84
5.1 Definitions and background....................................... 84
5.2 Preliminary results.............................................. 85
5.3 Complete paired comparison digraphs with no arc weight .5 .... 90
5.4 Connected domination graphs...................................... 99
5.5 Domination graphs with no isolated vertices..................... 114
5.6 Isolated vertices in domination graphs ......................... 134
6. Ranks of Tournament Matrices ..................................... 137
6.1 Definitions and background...................................... 137
6.2 Rank and domination ............................................ 140
6.3 Boolean row rank................................................ 144
6.4 A conjecture about tournament codes............................. 152
6.5 A construction for a singular tournament matrix with full Boolean
rank............................................................ 159
Appendix
A. Extra Proofs...................................................... 184
A.l Normal tournament matrices...................................... 184
A. 2 Two new proofs of the real rank of a tournament matrix......... 185
B. C++ Code......................................................... 190
References........................................................... 198
viii


FIGURES
Figure
1.1 An example of a Markov model....................................... 3
1.2 A drawing of a graph............................................... 5
1.3 A drawing of a digraph............................................. 8
1.4 A 5-tournament.................................................... 11
1.5 An example of a spiked cycle and a caterpillar.................... 23
2.1 A Quadrangular Digraph ........................................... 28
2.2 The 2-tournament, the 3-cycle, and the transitive triple.......... 37
2.3 The four 4-tournaments with the strong 4-tournament on the far right. 45
3.1 The tree diagram for our algorithm................................ 66
4.1 A bigraph representation of M and M'.............................. 71
4.2 Different digraph representations for M and M'.................... 72
4.3 An example of a cycle factor in a digraph......................... 82
5.1 A pcd and its associated tournament............................... 92
5.2 The domination graphs of a pcd and its associated tournament . 93
5.3 NC7.............................................................. 100
5.4 The arcs with weight x........................................... 101
5.5 The chorded 4-cycle.............................................. 107
5.6 The bowtie....................................................... 107
5.7 An example of a spiked clique.................................... Ill
IX


5.8 Some spiked bicliques .................................................. 122
6.1 A directed biclique partition............................................. 138
6.2 The network in our feasible flow problem.................................. 169
x


1. Introduction
1.1 Background
The two main structures of interest in this thesis are tournaments and tour-
nament matrices. Tournaments are a famous class of digraphs which originally
arose from the model of a round robin competition in which each player plays
against every other. Since this simple beginning, tournaments have been shown
to have a great deal of interesting combinatorial structure, and the tournament
matrix has proven to have many interesting algebraic properties. In this thesis
we look at various problems which bring together these two aspects of tour-
naments and tournament matrices. In chapter 5, we will also study a related
structure, the complete paired comparison digraph (sometimes called a general-
ized tournament).
In chapters 2, 3, and 4, we study three properties which arise from the
question of orthogonal support, and how these properties effect tournaments
and tournament matrices. In chapter 6, we take a look at various matrix rank
problems in tournament matrices. We find that domination plays a role in each
of these problems. Particularly, the domination graphs of tournaments can be
applied to the problems in chapter 2, and will give us our characterization in
chapter 4. Because these play such an important role in some of these problems,
especially in chapter 4, we characterize the domination graphs of complete paired
comparison digraphs in chapter 5.
1


The first problem addressed in this thesis is that of orthogonal support. This
problem comes from an application to quantum physics and quantum comput-
ing. In physics the problem arises in modeling discrete quantum walks, and in
computing it comes from writing quantum algorithms. In both cases, one sets
up the model, much like a Markov chain, by repeatedly applying an orthogo-
nal (or unitary) transition matrix to a state vector. The state vector gives the
original state of the object we wish to model, and after a select number of mul-
tiplications by the transition matrix we return the probable outcomes for our
object. Underlying the transition matrix is a directed graph which maps out the
movements of our object from state to state. We are interested in knowing if
this underlying digraph can be a tournament. We give an example of a Markov
model below.
Suppose six school children are playing a game of catch. The digraph in
Figure 1.1 shows the children as vertices, and the probability that child i will
throw the ball to child j is given by the weight on arc (z, j). If we begin by
giving the ball to child 1, then our model has the transition matrix
/.6 .4 0 0 0 0 \
0 0 .3.7 0 0
0 0 0 0 .4.6
M ~ 1 0 0 0 0 0
1 0 0 0 0 0
\0 1 0 0 0 0/
and state vector v = (1 0 0 0 0 0)T. We then repeatedly multiply v by M to
determine possible outcomes. For example, if we wish to know the probability
child 4 will end up with the ball after 12 throws, then we simply look at the 4th
entry of M12v. For more on Markov chains, the reader is referred to [55].
2


6
Figure 1.1: An example of a Markov model
The nature of decoherence in quantum physics requires the transition matrix
in the quantum version of these models to be orthogonal. We want to know when
a tournament can be used in these models, and hence when a tournament is the
digraph underlying an orthogonal matrix. We have three necessary conditions
for a directed graph to be the digraph of an orthogonal matrix. In chapter 2
we study the first of our necessary conditions, quadrangularity. In chapter 3
we study the stronger condition of strong quadrangularity, and discuss some of
our searches for tournaments which are the digraphs of orthogonal matrices. In
chapter 4 we see that an orthogonal matrix needs to be written in a particular
way, and see exactly when a tournament matrix can be written in this way.
In chapter 4 we also characterize exactly which tournaments can be used in a
3


doubly stochastic Markov model.
In chapter 5 we look at the domination graphs of complete paired compar-
ison digraphs. This is one extension of the study of the domination graphs of
tournaments. The domination graphs of tournaments were introduced by Merz,
Fisher, Lundgren, and Reid, in [44], and have been characterized in a series of
papers (see [31], [43], [44], [45], [46]). Domination graphs have been generalized
to tournaments in which ties are allowed, and proper subdigraphs of tourna-
ments by Factor and Factor in [24] and [25]. Another generalization, called
^-domination has also been studied by McKenna, Morton and Sneddon in [41].
We give a generalization of domination graphs for the context of complete paired
comparison digraphs, and essentially characterize this class of graphs.
In chapter 6 we examine some problems involving ranks of tournament ma-
trices. We will look at relationships between the Boolean, non-negative integer,
real, term, and minimal rank of tournament matrices. We see that, as domina-
tion plays a role in the questions addressed in chapters 2, 3, and 4, it also acts
in this context by giving us lower bounds for these ranks. We answer a question
of Siewert [58], by constructing an infinite class of singular tournament matrices
with full Boolean rank. We examine a dual to the Boolean row rank of a tour-
nament matrix which is an extension of Schiittes problem, and also examine a
dual to the problem of finding the Boolean rank of a tournament matrix.
1.2 Graph and digraph basics
In this section we review the background and notation for graphs and di-
rected graphs necessary for this thesis. Recall first that a graph G is a set of
vertices V(G), together with a set E(G) of unordered pairs of vertices, called
4


edges. If G is a graph such that no edge occurs more than once, and G has no
edge of the form [u,u] for some u G V(G), then G is typically referred to as a
simple graph. In this thesis we have no need to distinguish between graphs and
simple graphs, so we shall assume that all graphs are simple. We also have no
need for infinite graphs, and so shall assume the vertex and edges sets of our
graphs are finite. We typically represent a graph pictorially by representing the
vertices with dots, and connecting two dots with a line segment if there is an edge
joining the two vertices in the graph. For example, the graph G = (V(G), E(G))
with V(G) = {1,2,3,4,5,6,7} and E(G) = {[1,2], [1,3], [3,4], [5,6]} is shown in
Figure 1.2. We now give some of the basic definitions necessary to study the
structure of graphs.
oo o
6 4o 6
o
Figure 1.2: A drawing of a graph
Let G be a graph. If [u,v] G E(G), then we say that u and v are adjacent
in G. A vertex u and edge e of G are said to be incident if e = [u, v] for some
vertex v. For a given v G V(G), we define the degree of v, d(v), to be the
number of edges incident to v. Since we are assuming our graphs are simple, we
can equivalently define the degree of v as the number of vertices adjacent to v.
To study the structure of graphs it is sometimes useful to study related
graphs, such as subgraphs and the complement of a graph. A subgraph of a
5


graph G, is a graph H with V(H) C V(G) and E(H) C E(G). Given a set
S C V(G), the subgraph induced on S, G^S], is the graph with VXGfS1]) = S',
and [it, v] G £(G'[S']) if and only if it, v G S' and [it, v] G -E'(G'). A graph H
is called an induced subgraph of G if H = G'fS'] for some S' C V(G). The
complement of a graph G is the graph G, with V(G) = V(G) and [it, v] G E(G)
if and only if [u, i>] 0 E(G).
A path between vertices it and v in a graph G (sometimes called a u,v-
path) is an alternating sequence of vertices and edges of G, beginning with u
and ending with v, such that no vertex or edge is repeated, and each vertex is
incident with the edge immediately preceding and succeeding it in the sequence.
For simplicity, we typically only list the vertices of a path. The length of a path
is defined to be the number of edges in the path. The distance between vertices
u and v is defined to be the length of a shortest u, i;-path. Also, a graph G
is said to be connected if there exists a it, v-path for all distinct it, v G V(G).
A graph G which is not connected is called disconnected, and the maximally
connected subgraphs of G are called the connected components or components
of G. A component of order 1 is referred to as an isolated vertex.
Cycles and cliques are important graph structures that come up frequently
in chapter 5. A cycle in a graph G is an alternating sequence of vertices and
edges of G, beginning and ending with the same vertex, such that no edge is
repeated, only the first vertex is repeated, and each vertex is incident to the
edge immediately preceding and succeeding it. If all the vertices and edges of G
are contained in a cycle, we call G a cycle. The length of a cycle is the number
of edges occurring in the cycle, and a cycle of length n is called an n-cycle,
6


typically denoted by Cn. If the length of a cycle is odd or even, then we refer to
the cycle as an odd cycle or even cycle respectively. A complete graph, or clique,
on n vertices, written Kn, is a graph with n vertices, such that [u, v] G E(Kn) for
all distinct u,v G V(Kn). Typically the term clique is reserved for a complete
subgraph of some graph.
Another important class of graphs which come up throughout the thesis are
the bipartite graphs. A graph B is said to be bipartite if V(B) can be partitioned
into two sets X and Y, called a bipartition, such that no two vertices of X are
adjacent and no two vertices of Y are adjacent. A well known result on bipartite
graphs, which proves useful in chapter 5, is that a graph is bipartite if and only
if it contains no odd cycles. A complete bipartite graph, or biclique, is a bipartite
graph B with bipartition X U Y so that [x, y] G E(B) for all x G X and y Gh
If |A| = r and |yj = s, then we sometimes denote the biclique on XUY by KTtS.
As with clique, the term biclique is typically reserved for a complete bipartite
subgraph of some graph. Bicliques play an important role in chapter 6 because
of their relationship with rank 1 matrices. We now turn our attention to directed
graphs.
A directed graph, or digraph, D is a set of vertices V(D), together with a set
A(D) of ordered pairs of vertices, called arcs. An orientation of a graph G is a
digraph D obtained from G by letting V(D) = V(G) and for each [u,v] G E(G),
making exactly one of (u, v) or (v, u) an arc of D. Directed graphs are typically
drawn in a manner analogous to graphs, in that each vertex is represented by a
dot, and we draw an arrow from vertex u to vertex v if (u, v) is an arc of of the
digraph. Figure 1.3 shows a drawing of the digraph D = (V(D), A(D)) where
7


V(D) = {1, 2,3,4, 5,6} and A(D) = {(2,3), (3,4), (5, 5), (4,1), (4,3), (5,6)}. We
now give some of the necessary definitions and notation to study digraphs in this
thesis.
1
O
60
Figure 1.3: A drawing of a digraph
If (u, v) G A(D), then we typically say that u beats v or that u domi-
nates v and write this as u v. We define the outset, Oo(v), of a vertex v in
D to be the set of all vertices that v dominates. That is,
0D(v) = {ue V(D) : (v,u) G A{D)}.
Similarly, the inset, Id{v), of a vertex v in D is the set of all vertices which
dominate v. So,
ID{v) = {u£V(D):{u,v)eA(D)}.
The closed outset and closed inset of a vertex v are defined by Od[v] = Od{v) U
{u} and Id[v] I(v) U {n} respectively. If S C V(D), then we define the
outset of S as the set of all vertices dominated by some vertex in S, written
Od(S). Equivalently, we can define the outset of S by Od(S) = UvesOoiv).
We denote by Od[S], the closed outset of S, defined by Od[S] Od(S)US. The
8


inset of S and closed inset of S are defined analogously as Id(S) = UvesHv)
and Id[S] = I(S) U S respectively. When the context of which digraph we are
referring to is clear we will drop the subscript.
The out-degree of a vertex v in a digraph D, written df(v), is defined to
be \Od(v)\. Similarly, the in-degree of v is dp(v) = \Io(v)\. Again, when
the context is clear, we will drop the subscript. The minimum out-degree of a
digraph D, denoted 8+(D), is defined to be 8+(D) = min{d+(u) : v £ V(D)}.
Similarly, the minimum in-degree of D is 5~(D) = min{d~(u) : v £ V(D)}. We
define the maximum out-degree and maximum in-degree of a digraph D to be the
values A+(Z)) = max{d+(t>) : v £ V(D)} and A~{D) = max{d~(v) : v £ V(D)}
respectively.
Let D be a digraph. A subdigraph of D is a digraph D' such that V(D') C
V(D) and A(D') C A(D). If S C V(D), then the subdigraph induced on S is
the digraph D' with V(D') = S and (u,v) £ A(D') if and only if u,v S and
(u, v) £ A(D). A digraph D' is called an induced subdigraph of D if there exists
some S C V(D) which induces D'.
A directed path in a digraph D is an alternating sequence of vertices and arcs
of D, beginning and ending with vertices, so that no vertex or arc is repeated,
and if (u, v) is an arc in the path, the vertex immediately preceding it must be
u and the vertex immediately succeeding it must be v. A directed path which
begins at a vertex u and ends at a vertex v is called a directed u, v-path. Similar
to the undirected case, the length of a directed path is defined to be the number
of arcs in the path. If D is a directed graph so that there is a directed u, u-path
for every distinct u,v £ V(D), then we say D is strongly connected. If D is not
9


strongly connected, then the maximal strongly connected subdigraphs of D are
called the strong components of D.
A directed cycle in a digraph D is an alternating sequence of vertices and
arcs of D which begin and end with the same vertex, repeat no vertices or edges,
and if (u, v) is an arc in the cycle, then the vertex immediately preceding it must
be u and the vertex immediately succeeding it must be v. Similar to undirected
cycles, the length of a directed cycle is the number of arcs in the cycle. A
directed cycle of length n is referred to as a directed n-cycle. Also, as before,
an n-cycle is called a directed odd cycle or directed even cycle if n is odd or even
respectively. If it is clear that we are dealing with a directed context, we will
simply refer to directed cycles and directed paths as cycles and paths.
To study the structure of graphs and digraphs, it is useful to have a concept
of isomorphism in graphs and digraphs. An isomorphism of graphs G and H
is a bijective function (j) : V(G) > V(H) such that [u, v] E E(G) if and only
if [(u), 4>{v)\ E E(H). That is, a graph isomorphism is an adjacency preserv-
ing bijection. We say that two graphs are isomorphic if there exists a graph
isomorphism between them. Similarly, we define an isomorphism of digraphs D
and D' to be a bijection 0 : V(D) V(D') such that (w, v) E A(D) if and
only if ((v)) E A(D'). That is, a digraph isomorphism is a dominance
preserving bijection. An isomorphism from a graph to itself (digraph to itself)
is called a graph automorphism (digraph automorphism). We now look at the
class of digraphs studied most in this thesis.
1.3 Tournament basics
10


In this section we review some of the basic terminology and properties of
tournaments. A tournament T is a complete asymmetric digraph. That is, for
every two distinct u,v E V(T), either (u,v) E A(T) or (v,u) both, and (v, v) £ A(T) for all v E V(T). A tournament with n vertices, is called
an n-tournament. Equivalently, some define an n-tournament as an orientation
of the complete graph Kn. An example of a 5-tournament is shown in Figure 1.4.
Figure 1.4: A 5-tournament
In studying tournament structure, we often want to look at subtournaments
and the dual of a tournament. Given a tournament T, and S C V(T), a subtour-
nament of T is the tournament T[S], with F(T[5]) = S, and (u, v) E A(T[S']) if
and only if u, v E S and (u, v) E A(T). That is, T[S] is the subdigraph induced
on S. Also, for a vertex v E V(T) or a set of vertices S, we define the subtour-
naments T v and T S to be the tournaments T[V(T) {u}] and T[V(T) S]
11


respectively. The dual of T is the tournament Tr, with V(Tr) = V(T) and
(u,v) A(Tr) if and only if (v,u) G A(T). We define the dual of a digraph in
the same way, and use the same notation.
One of the most famous results about tournaments is Landaus Theorem.
The list of out-degrees of the vertices of a tournament is called its score sequence.
In 1953 Landau characterized which lists of n positive integers could be the score
sequence of some tournament.
Theorem 1.1 (Landaus
quence of positive integers,
if and only if
Theorem) Let si, S2, ,sn be a non-decreasing se-
This list is the score sequence for some n-tournament
for 1 < k < n 1 and
The necessity in Landaus Theorem is easy to see. Any n-tournament must
have an arc between every two vertices, and hence Q) arcs. Further, every sub-
tournament of an n-tournament on k vertices will have (*) arcs. The argument
follows by counting arcs in subtournaments in this way, and by counting them
as the sum of the out-degrees of a subset of vertices. The sufficiency in Landaus
Theorem has been proved in many ways, by many people. It has been proven by
using classic combinatorial methods, using majorization of vectors, using posets,
using network flows, and even using Halls Theorem. Some of the many authors
of these proofs include Landau, Ryser, Reid, Thomassen, Fulkerson, and Bang
and Sharp. For a full proof of Landaus Theorem the reader is referred to [50].
12


Another classic theorem on tournaments involves Hamiltonian paths. Given
a digraph D, a Hamiltonian path is a path which contains every vertex of D.
By taking a path of maximum length in a tournament, one can show, via the
complete asymmetry of the tournament, that there is no vertex not on the path
and it is hence Hamiltonian. We discuss an analogous result about cycles in
strong tournaments below. We now state this theorem.
Theorem 1.2 Every tournament contains a Hamiltonian path.
In this thesis, we are often concerned with when one set in a tournament
completely dominates another. Let T be a tournament and S,S' C V(T). If
for every u G S and v G S', u > v, then we write S => S'. In the case
where S = {u} (S' = {u}), we write u => S' (S => v) rather than {u} => S'
(S => {u}). A vertex s G V(T) such that s => V(T) {s} is called a transmitter.
A vertex t V(T) such that V(T) {t} => t is called a receiver. The concept
of one set completely dominating another plays an important part in our study
of tournaments and tournament matrices, as it corresponds to large blocks of
ones in the adjacency matrix. Tournaments with transmitters and receivers also
play a part as special cases of some of our results. In particular, when studying
tournaments which are not strongly connected, tournaments with transmitters
or receivers are important special cases.
As with digraphs, we define a tournament T to be strongly connected if for
any two vertices u, v G V(T) there is a directed path in T from u to v and
another from v to u, and a strong component of a tournament to be a maximal
strongly connected subtournament. We sometimes refer to a strongly connected
13


tournament as a strong tournament. We note that a single vertex is trivially
strongly connected, and that a 2-tournament has exactly one arc, and hence
cannot be strongly connected. So, the smallest non-trivial strong component
which a tournament could have is the 3-cycle. Strong tournaments have been
characterized in terms of their score sequences by replacing the inequalities in
Landaus Theorem with strict inequalities. The following two theorems are well
known, useful results on tljp structure of tournaments.
Theorem 1.3 Let T be a strong n-tournament, and let v G V(T). Then v is
contained on a cycle of length k for k = 3,..., n.
Theorem 1.4 Let T be a tournament which is not strongly connected. Then
V(T) can be partitioned by the strong components of T, and these components
can be labeled Ti, T2,..., Tm such that Ti => Tj if and only if i < j.
The strong components T\ and Tm in the previous theorem are called the
initial and terminal strong components of T respectively. The above result has
also been stated as The condensation of a tournament is transitive. A tran-
sitive tournament is one in which for all u,v,w G V(T), if u > v and v w,
then u > w. There are several equivalencies for the definition of a transitive
tournament. The two others we will most frequently use are that the vertices
can be labeled V\,V2,... ,vn such that vl > Vj if and only if i < j, and that
0,1,2,... ,n 1 is the score sequence of T. We also note that the transitive
tournament on n vertices is unique up to isomorphism.
The condensation of a tournament T is typically defined to be the tourna-
ment T' obtained by representing each strong component of T with a vertex of
14


T', and letting u v if and only if for the corresponding strong components
Tu and Tv we have that Tu => Tv. Theorem 1.4 above, with this definition, may
also be stated as The condensation of a tournament is always a transitive tour-
nament. In this thesis we will adopt the following, more versatile definition of
condensation. Let T be a tournament, and suppose we can partition the vertices
of T as Si, S2, ) Sm such that for all i ^ j either S', =>- Sj or Sj => S,. We de-
fine the condensation of T, with respect to this partition, to be the tournament
V with V(T) = {ui, V2,. , um} with Vi Vj in T' if and only if S, => Sj in T.
In the study of tournaments, the extreme examples of many problems tend to
be transitive tournaments and regular tournaments. We discussed the transitive
tournaments above. A regular tournament is one in which every vertex has
the same out-degree. Consequently, every vertex in a regular tournament has
the same in-degree. Thus, for every regular n-tournament, n is odd and the
out-degree and in-degree of every vertex is While there are no regular n-
tournaments for n even, we do have an analogous tournament. A near regular
tournament is a tournament in which the out-degrees of any two vertices differs
by at most one. By some counting arguments, one can show that if T is a near
regular n-tournament, then n is even, exactly half of the vertices have out-degree
| and exactly half of the vertices have out-degree | 1.
Up to isomorphism, there is only one transitive n-tournament, however there
can be many non-isomorphic regular n-tournaments. To better study regular
tournaments we often turn to the class of rotational tournaments. Rotational
tournaments have a nice structure which makes them somewhat easier to work
with, and while not all regular tournaments are rotational, there are typically a
15


large number of rotational n-tournaments for a given n. This makes rotational
tournaments a nice class of regular tournaments to start with when studying
questions about regular tournaments. We give the construction for rotational
tournaments below.
Choose an odd positive integer n, and let 5 be a subset of {1 2,..., n 1}
of order such that i £ S if and only if i (mod n) is not in S. Construct a
digraph T on the vertices {0,1, 2,..., n 1} with i > j in T if and only if j i
(mod n) is in S. Since x is in S if and only if x (mod n) is not, we have that
for any two distinct i,j £ V(T) exactly one of j i (mod n) or % j (mod n)
is in S. So we have that i * j or j > i, but not both. Further, since 0 & S, T
has no arcs of the form Thus T is a tournament. We call T a rotational
tournament with symbol S.
To see that rotational tournaments are regular choose any vertex i. Then,
0(i) = {i + j (mod n) : j £ S'}, and so each vertex has the same out-degree.
Another important property of rotational tournaments is that they are vertex
transitive. A vertex transitive tournament T is one in which for every two
vertices u,v in T, there exists an automorphism of T that maps u to v. Given
a rotational tournament T with symbol S, pick i,j £ V(T), and let k = j i
(mod n). Consider the function , defined by a + k (mod n). It is easy
to see that 0 is a bijection. Further, if a > b in T, then b a (mod n) is in S,
and {a) > (&),
and

automorphism which maps i to j, and since i and j were chosen arbitrarily, T
is vertex transitive.
16


An important class of rotational tournaments which come up frequently in
this thesis are the quadratic residue tournaments. Recall from number theory
that an integer a is called a quadratic residue modulo n if there exists some
x such that a = x2 (mod n). For any given odd prime p, we know that there
are ^ quadratic residues modulo p. Further, given a prime p such that p = 3
(mod 4), we know that i is a quadratic residue if and only if i is not. (For a
proof of this, and more on quadratic residues see [49].) So, given a prime p = 3
(mod 4), the quadratic residues modulo p form a symbol for a rotational p-
tournament. We call this tournament the quadratic residue tournament of order
p, written QRp. An important, and well known property of quadratic residue
tournaments is that they are arc-transitive. An arc-transitive tournament T is
one in which for any two arcs (i,j) and (h, k) in T, there exists an automorphism
of T which maps i to h and j to k. We now state and prove this property for
completeness.
Theorem 1.5 Quadratic residue tournaments are arc-transitive.
Proof: Let p = 3 (mod 4) be a prime, and choose arc (i,j) and (h,k) in
QRp. Let a = (k h)(j z)-1 and b (hj ki)(j z)_1. Note a is a quadratic
residue since k h and j i are quadratic residues, and the set of quadratic
residues modulo p form a group under multiplication. Define the function / by
f : x ^ ax + b (mod p). Since V(QRp) = Zp is a field, / is a bijection from
V(QRp) to V{QRp). To see that / is an automorphism, pick (x, y) G A(QRp).
Then (y x) is a quadratic residue modulo p, and
f(y) f(x) ay + b- (ax + b) = ay ax = a(y x).
17


Since a and (y x) are quadratic residues, a(y x) is a quadratic residue, and
so f(x) f(y). So, / preserves dominance and is hence and automorphism.
Also,
f{i) = ai + b
= ((k h)(j z)_1)i + (hj ki)(j i)~l
= (ki hi-\- hj ki)(j i)~l
= h(j i)(j i)~l
= h,
and
fti) = aj + b
= ((& h)(j i)~1)j + (hj ki)(j i)-1
= (kj hj + hj ki)(j i)_1
= k(j i)(j i)-1
= k
Thus, QRp is arc-transitive.
The arc-transitivity of quadratic residue tournaments tells us that the tour-
nament induced on 0(u) D 0(v) is the same for any two distinct vertices u, v in
QRp. In particular, this tells us that \0(u) fl 0(u)| is the same for all distinct
u, v G V(QRp). Tournaments with this property are called doubly regular tour-
naments. That is, a tournament T is called a doubly regular tournament if for
all distinct u,v V(T), \0(u) fl 0(u)| = k, for some given k.
18


A doubly regular tournament with \0(u) D 0(v)| = k for all distinct u,v
is also a regular tournament on 4fc + 3 vertices with d+{v) = 2k + 1 for all
vertices v. Doubly regular tournaments have many nice properties. In particular,
they form extremal cases for many problems in tournaments. While it is not
certain, they also appear to be good candidates for extremal cases in some of
the problems posed in this thesis. For instance, it is our current belief that if
a tournament is going to be the digraph of an orthogonal matrix, the smallest
non-trivial example will be doubly regular. (In fact, the only known example is
the 3-cycle, which is doubly regular with k = 0.) We also believe that doubly
regular tournaments will be the optimal choices when extending tournaments to
create larger tournaments with small Boolean rank. For more on doubly regular
tournaments, the reader is referred to Reid and Brown, [10].
1.4 Domination basics
Given a digraph D, and a set S C V(D), we say that S is a dominating
set in D if OfS'] = V(D). In this section we discuss some of the background
on domination in digraphs and tournaments, and how it relates to the problems
studied in this thesis. Domination in tournaments has been studied by many
people. The original problem appears to be a problem of Schutte, in which he
asks, For a given k, what is the least n so that there exists an n-tournament
T such that for all S C V(T) with [/S'] = k, there exists a vertex v e V(T)
with v => S'? Taking the asymmetry of tournaments into account, one can
see that if there is no such vertex for a set S, then S is a dominating set. The
order of a smallest dominating set in D is called the domination number of
D, written 7(D). So, answering Schiittes problem is equivalent to finding a
19


smallest n-tournament T with 7(T) > k.
A property related to domination that we will discuss in chapter 6 is irre-
dundance. An irredundant set in a digraph D is a set S such that for all u e S,
there exists a vertex v G V(D) such that v 0[u] O(S). The size of a smallest
maximal irredundant set in a digraph D is called the lower irredundance number
of D, written ir(D). The size of a largest irredundant set is called the upper
irredundance number, written IR(D). Similarly, the size of a largest minimal
dominating set is called the upper domination number, written T(D). A recent
treatment and collection of results on domination and irredundance in tourna-
ments can be found in Hedetniemi, Hedetniemi, McRae, and Reid [34]. The
following useful result of basic bounds on 7, T, ir and IR is taken from their
paper.
Theorem 1.6 [34] For every tournament T,
(i) ir(T) < 7(T) < A+(T);
(ii) ir(T) < 7(T) < r(T) < IR(T);
(Hi) 7(T) (w) 7(T) < S~(T) + 1.
As mentioned in the previous section, doubly regular tournaments form
extremal examples for several problems, and appear to be extremal examples for
some of the problems in this thesis. This also appears to be true when looking
for tournaments with large domination numbers. For instance, the smallest
tournament with domination number 2 is the 3-cycle. The smallest tournament
20


such that every set of 2 vertices is dominated by a third, and hence the smallest
tournament with domination number 3, is QR7 (note this is the only doubly
regular 7-tournament and is hence the unique 7-tournament with domination
number 3). It can also be verified that the smallest tournament with domination
number 4 is QR\o (see [34]). Some of these examples prove quite useful when
we begin relating domination in tournaments to properties in the corresponding
tournament matrices.
One way in which we will relate domination to matrix properties, especially
in chapters 2 and 4 is by studying the structure of dominant pairs in a tourna-
ment. A dominant pair in a tournament is a dominating set of order 2. Given
a tournament T, the domination graph of T is the graph dom(T) on the same
vertices as T with [u,v] £ E(dom(T)) if and only if {u,v} form a dominant pair
in T. As mentioned, the domination graphs of tournaments were introduced by
Merz, Lundgren, Reid, and Fisher in [44], and have since been characterized in
a series of papers.
Our study of the domination graphs of tournaments comes from their rela-
tion to the competition graphs of tournaments. Given a digraph D, the com-
petition graph of D is the graph comp (ZD) on the same vertices as D with
[u, u] £ E(comp(D)) if and only if u ^ v and there exists some w £ V(D')
such that u > w and v > w. Recall from the asymmetry of tournaments, that
two vertices will dominate a tournament if and only if there does not exist a
vertex which dominates them both. This is the main idea behind the following
theorem of Merz et. al..
21


Theorem 1.7 [44] The complement of the competition graph of a tournament
is the domination graph of its dual.
If D is a digraph, and M its adjacency matrix, then for i ^ j, the 2, j entry
of MMr will be non-zero if and only if row i and row j share a common non-zero
entry. That is, the i, j entry of MMJ will be non-zero if and only if vertex i and
vertex j compete in D. So, the non-zero, off diagonal entries of the adjacency
matrix of comp(D) are in direct correspondence with those of MMr. This
relationship together with the above result is the main correspondence between
domination in tournaments and the matrix properties discussed in chapter 2.
We use Merz et. al.s characterization of the domination graphs of tourna-
ments in chapter 4, along with a characterization of separable matrices in terms
of the competition graphs of the corresponding digraphs, to characterize exactly
which tournament matrices are separable. In chapter 5 we use this characteri-
zation as a jumping off point for our characterization of the domination graphs
of complete paired comparison digraphs. We state the necessary conditions of
the characterization here, but first recall the following definitions.
Recall that a tree is a connected acyclic graph. A caterpillar is a tree such
that the removal of all pendant vertices results in a path. Each caterpillar has
a path of maximum length called a spine. A spiked cycle is a graph such that
the removal of all pendant vertices results in a cycle. If the cycle in a spiked
cycle is odd, then we call it a spiked odd cycle. Note, a spiked cycle need not
have pendants. So, cycles form a subclass of spiked cycles, and odd cycles form
a subclass of spiked odd cycles.
22


Figure 1.5: An example of a spiked cycle and a caterpillar
Theorem 1.8 [44] The domination graph of a tournament is either a caterpil-
lar or a spiked odd cycle.
The sufficient conditions for the characterization of domination graphs of
tournaments vary depending on connectedness restrictions and can be found
in [31], [43], [45], and [46]. We now turn to some necessary background on
(0, l)-matrices and matrix theory.
1.5 Matrix basics
In this section we cover some basic definitions and background on (0,1)-
matrices. First, we introduce the notation we shall use for discussing matrices
and vectors. Let M be a matrix. We denote the i,j entry of M by Mhj. We
use Mi, to represent the ith row of M and Mi to represent the ith column of M.
If v is a vector, then we let Vi denote the ith entry of the vector.
A (0,1)-matrix is a matrix whose every entry is a 0 or 1. We concern
ourselves with square (n x n) (0, l)-matrices in this thesis. Any square (0,1)-
matrix can be considered the adjacency matrix of some digraph. Let D be a
23


digraph with V(D) = {1,2,... n}. The adjacency matrix of D is the n x n
(0, l)-matrix M defined by
In chapters 2, 3, and parts of chapters 4 and 6 we are interested in the
This has also been called a non-zero pattern by some authors. The digraph D
whose adjacency matrix is the pattern of a matrix A is called the digraph of A.
If M is the pattern of a matrix A, or D the digraph of A, then we sometimes
say that M and D support A.
Just as tournaments are an important class of digraphs to study, tournament
matrices give rise to several interesting problems in the study of (0, l)-matrices.
A tournament matrix is the adjacency matrix of a tournament. By the complete
asymmetry of tournaments, one could also define a tournament matrix to be a
square (0, l)-matrix M with Os on the diagonal and Mh] = 1 if and only if
Mjti = 0. A third equivalent definition of tournament matrices is a square
(0, l)-matrix M such that M + MT = J /, where J is a matrix of all Is, and
I the identity matrix.
Some other important classes of matrices which come up are the zero ma-
trices, the class of matrices Jmx, and the permutation matrices. An mxn zero
1 \l(i,i)eA(D),
0 if (i,j) 0.4(D),
patterns of matrices. Given a matrix A, with arbitrary entries, the pattern of A
is the (0, l)-matrix M obtained from A by letting
24


matrix, Om>n, is an m x n matrix in which every entry is a 0. If m = n, we will
simply write On, or if the dimensions are clear from context, O. We will write a
vector of all zeros as 0. The mxn matrix Jm>n is an m x n matrix of ones. Again,
if m = n, we will simply write Jn, or J if the dimensions are clear from con-
text. We write a vector of all ones as 1. Given a bijection from {1,..., n} to
{1,..., n}, a permutation matrix is a matrix P with Pi,4,(1) = 1 for i = 1,..., n,
and Pij = 0 otherwise. A well known property of permutation matrices is that
left multiplying a matrix A by a permutation matrix PT will reorder the rows
of A according to the bijection corresponding to P, and right multiplying A by
P will reorder the columns according to the bijection corresponding to P.
If M is the adjacency matrix of some digraph D, and P a permutation ma-
trix, then left and right multiplying M by PT and P respectively, results in
the adjacency matrix of a digraph isomorphic to D. Left and right multiply-
ing M by permutation matrices P and Q results in a permutation equivalent
matrix. Permutation equivalent matrices do not necessarily correspond to iso-
morphic digraphs, but are important for some matrix properties. We study the
permutation equivalence of tournaments in chapter 4.
We denote the standard Euclidean inner product of two vectors x and y by
(x, y). That is, for column vectors x and y, (x, y) = xTy. We say two vectors x
and y are orthogonal if (x, y) = 0. An n x n matrix M is said to be orthogonal
if MMT MTM = I. So, if M is orthogonal, (Mi., Mj.) = 0 and (Mi, Mj) = 0
for all i ^ j, and £"=1 M?j = E1U Mh = T for anY h j-
Two less traditional matrix concepts which arise in chapter 6 are comple-
ments of matrices, and the idea of one matrix being less than another. Given a
25


(0, l)-matrix, M, we define the complement of M to be the matrix Mc, where
= 1 if and only if MitJ = 0. Given two matrices A and M, we say that
A < M if they have the same dimensions and for all i,j, AhJ < Mitj. Equiva-
lently, for vectors x and y, we say x < y if x, < y, for all i. We define these
since (0, l)-matrices and vectors tie in closely with sets when we begin dealing
with Boolean arithmetic in chapter 6. Also, for a set S and subset W of S, we
will also write the complement of W in S as Wc.
26


2. Quadrangular Tournaments
2.1 Definitions and background
Recall that an n x n matrix M is defined to be orthogonal if MMJ =
Mr M = I, where / is the n x n identity matrix. In this chapter we introduce
a basic necessary condition for a digraph to support an orthogonal matrix, and
study the tournaments which meet this condition. Our condition is derived
from combinatorial orthogonality, which originally appeared in a matrix context
in [5]. Given two n-vectors x = xn) and y (yi, y^,..., yn) with
entries from any field, we say that x and y are combinatorially orthogonal if
|{z: Xjyi 7^ 0} | 7^ 1. That is, they do not share exactly 1 non-zero entry. We say
a matrix M is combinatorially orthogonal if every two rows are combinatorially
orthogonal and every two columns are combinatorially orthogonal.
To see that this is in fact a necessary condition for a matrix to be orthog-
onal, let M be a matrix with rows and M,. which are not combinatorially
orthogonal (a similar argument holds for columns). Then Mi# and have
exactly one non-zero entry in common, and so is just the product
of these two entries and hence, not zero. As any two rows (or columns) of an
orthogonal matrix must be orthogonal, we see that combinatorial orthogonality
is a necessary condition for a matrix to be orthogonal. Further, since combi-
natorial orthogonality only concerns itself with whether an entry is non-zero or
not, combinatorial orthogonality is a necessary condition for a (0, l)-matrix to
be the pattern of an orthogonal matrix.
27


A digraph D is called quadrangular if for all distinct u, v G V(D), \0(u) n
0(d)| 7^ 1 and |I(u) D /(d)| ^ 1. If we only require the restriction on the
outsets or insets separately, we say D is out-quadrangular or in-quadrangular
respectively. Figure 2.1 shows an example of a quadrangular digraph. Note that
Figure 2.1: A Quadrangular Digraph
if A is the adjacency matrix of a digraph, and Ai% and Aj, two rows of A which
correspond to vertices u and v respectively, then (AiAj.) = \0(u) fl 0(d)|.
Similarly, the inner product of two columns is equal to the size of the intersection
of the insets of the corresponding vertices. So, D is a quadrangular digraph, if
and only if its adjacency matrix is a combinatorially orthogonal matrix. Thus,
quadrangularity is a necessary condition for a digraph to support an orthogonal
matrix.
Many of the results in this chapter show that, in certain classes of tour-
naments, there is a relationship between quadrangularity and the domination
number of the tournament or a subtournament. For example, Theorems 2.1,
2.8, and 2.19 all exhibit this relationship. We begin by examining tournaments
which are not strongly connected. We see that in this case quadrangularity of
the tournament can be reduced to the question of quadrangularity in a strong
28


subtournament, or a bound on the domination number of a subtournament. We
then look at cases where we have restrictions on the out-degrees and in-degrees
of the tournament. We finish the chapter by characterizing the orders for which
a quadrangular tournament exists.
2.2 Tournaments which are not strongly connected
Our first result of this section classifies quadrangular tournaments with a
transmitter and a receiver by a bound on the domination number of a subtour-
nament.
Theorem 2.1 Let T be a tournament on 3 or more vertices with a transmitter
s and receiver t. Then T is quadrangular if and only if both y(7 {s,t}) > 2
and 7((T {s, f})r) > 2.
Proof: Let T be a tournament with a transmitter s and receiver t. Suppose
that both 7(7'{s, t}) > 2 and 7((7 {s, t})r) > 2. Then, £'(dom(7{s, t})) =
7(dom((7 {s, f})r)) = 0. Thus the competition graphs of both 7 {s, t} and
(7 {s,f})r are complete. That is, for all x,y E V(T) {s,f} there exist
w,z E V(T) such that w^x, w^y, x-^z and y > z. Pick distinct
,uG V{T). We consider three cases.
Case 1: Suppose u, v £ {s, t}. Then, as noted before, there exist vertices
w,z E V(T {s,f}) so that z E 0(u) D 0(v) and w E I{u) Pi I(v). Also,
s E 0(u)C\0(v) and t E I(u)C\I(v). So, |0(u)nO(u)| > 2 and |/(-u)n/(u)| > 2.
Case 2: Now assume that one of u, or v is t, say u = t. Since 0(t) = 0,
0(f) n 0(v) = 0, so |0(f) n 0(v)| = 0. Also, 7(f) = V(T) {t}, so 7(f) n I(v) =
I(v). If v = s, then I(v) = 0, and |7(f) n I(v)\ 0. So, suppose v ^ s. Since
29


7(T {s, t}) > 3, Theorem 1.6 gives us that 2 < 7(T {s, t}) <5 (T {s, t}).
Thus, d~(v) > 2, and since I{v) C I(t), |/(t) fl /(w)| = d~(v) > 2 as desired.
Case 3: Now, assume that one of u, v is s, say u = s. Since I(s) = 0,I(s)C\I(v)
0, so |/(s) fl I(v)| = 0. Also, since O(s) = V(T) {s}, O(s) fl O(u) = O(v).
The case where v = t is covered in case 2, so assume / t. Since 7((T
{s, t})r) > 3, Theorem 1.6 gives us that 2 < 7((T{s, t})r) < 5~((T{s, t})r) =
5+(T {s, t}). Thus, d+(u) > 2, and since s is a transmitter, 0(v) C O(s), so
|0(s) fl 0(v)| = d+(v) > 2.
Conversely assume that T is a quadrangular tournament with both a trans-
mitter s and receiver t. If u, v 6 V(T) {s,t}, then s £ 0(u) fl 0(v),
and t £ I(u) fl I(v). So, since T is quadrangular, |O(u) fl 0(v)\ > 1 and
|I(u) fl I(v)| > 1, there must exist vertices w,z in T {s, t} such that
z £ 0(u) fl 0(v) and w £ I(u)CI I(v). Since w beats u and v they cannot be a
dominant pair in T {s, t} and since u and v beat z they cannot be a dominant
pair in (T {s,t})r. Thus, -E^don^T {s,t})) = £'(dom((T {s,t})r)) = 0.
Equivalently, 7(T {s,t}) > 2 and 7((T {s, t})r) > 2. This completes our
proof.
Prom Theorem 1.6, and Theorem 2.1 we get the following corollary which
allows for a quick check to see if a tournament with both a transmitter and a
receiver is quadrangular.
Corollary 2.2 Let T be a tournament on 3 or more vertices with a transmitter s
and receiver t. IfT is quadrangular, then 5+(T {s,t}) > 2 and 5~(T{s,t}) >
2.
30


The following results characterize quadrangular tournaments in the case
where the tournament has a transmitter or receiver, but not both, by a bound
on the domination number of a subtournament.
Theorem 2.3 Let T be a tournament with a transmitter s and no receiver.
Then T is quadrangular if and only if, 7(T s) > 2, T s is out-quadrangular,
and 8+(T s) >2.
Proof: First suppose that 7(T s) > 2, T s is out-quadrangular, and
8+(T s) >2. Pick distinct u, v G V(T). First suppose that u, v G V(T) {s}.
Since j(T s) > 2 there exists x G V(T) {s} such that x > u and x > v. So,
s,x 6 I(u)C\I(v) and so \I(u)C\I(v)\ > 2. Also, since T s is out-quadrangular,
\0(u) flO(u)| 7^ 1. Now, suppose that one of u, v is s, say u = s. Since I(s) = 0,
|/(s) fl /(r;)| = 0. Also, since 8+(T s) >2, |0(s) fl 0(v)\ = |0(n)| > 2, Thus,
T s is quadrangular as desired.
Now, assume that T is quadrangular. Since O(s) = V(T) {s}, |I(u) n
I(v)\ > 1 for all distinct u, v G V(T) {s}. Since T is quadrangular this
means we must have |I(u) fl I(v)\ > 2 for each u,v E V(T) {s}. Thus, for all
u, v V(T) {s}, there must exist some x G V(T) {s} such that x u and
x > v. So, 7(T s) > 2. Since T has no receiver, |0(u)| > 1 for all v G V(T).
Since 0(s)nO(r) = 0(v) for all v G V(T) {s}, and T is quadrangular, we must
then have that d+(v) = |0(u)| = |0(s) fl 0(v)\ > 2. Thus, 5+(T s) > 2. Now,
pick distinct u, v G V(T) {s}. Since T is quadrangular, \0(u) fl 0(v)\ ^ 1, so
T s is out-quadrangular.
If T is a tournament with a receiver and no transmitter, then it is the dual of
31


a tournament with a transmitter and no receiver. A tournament is quadrangular
if and only if its dual is, so by Theorem 2.3, T is quadrangular if and only if
7((T t)r) > 2, (T t)r is out-quadrangular and d+([T t)T) > 2. Since
(T t)r being out-quadrangular is equivalent to T t being in-quadrangular,
and S+((T t)r) = S~(T t) we get the following corollary.
Corollary 2.4 Let T be a tournament with a receiver t and no transmitter.
Then T is quadrangular if and only if^((T t)r) >2, T t is in-quadrangular,
and 5~(T t) > 2.
Theorem 1.6 together with Theorem 2.3 and Corollary 2.4 give analogous
results to Corollary 2.2. Namely that if T is a quadrangular tournament with a
transmitter s and no receiver (receiver t and no transmitter), then 6+(T s)>2
and S~(T s) > 2 (5+(T t) > 2 and 5~(T t) > 2). We finish this section by
characterizing quadrangular tournaments with no transmitter or receiver which
are not strongly connected in terms of properties of their initial and terminal
strong components.
Theorem 2.5 Let T be a tournament with no transmitter or receiver which
is not strongly connected. Then T is quadrangular if and only if the initial
strong component T\ is in-quadrangular with S~(Ti) > 2 and the terminal strong
component Tm is out-quadrangular with S+(Tm) > 2.
Proof: Let T be a tournament with no transmitter or receiver, which is
not strongly connected. Suppose that T\ is in-quadrangular with S~(Ti) > 2,
and that Tm is out-quadrangular with S+(Trn) > 2. Note that since T has no
32


transmitter or receiver, T\ and Tm must contain at least 3 vertices each. Pick
distinct u, v G V(T). We consider 5 cases.
Case 1: Suppose that u and v are in neither Ti nor Trn. Every vertex of T\
beats every vertex in T Tx and every vertex of Tm is beaten by every vertex
of T Tm. So,
|O(u) n 0(v)| > |V(Tro)| > 3 and |7(u) n 7(i>)| > |l^(Ti)| > 3.
Case 2: Suppose that both u, v G T\. Then, since T\ is in-quadrangular, |I(u) fl
I(v)| 7^ 1. Also, u and v beat every vertex in T Ti, in particular, V(Tm) C
0(u) r\0(v). Thus,
\0(u) n 0(v)\ > |V(Tm)| > 3.
Case 3: Suppose that both u, v 6 V(Tm). Then, since Tm is out-quadrangular,
10(u) n 0(v)I ^ 1. Also, II(u) n /(n)| > |y(Ti)| > 3.
Case 4 Suppose that u G V(Ti) and v g V(Ti). Since v £ V(T\) we know
that I(u) C V{Ti) C I(v) and so I(u) fl I(v) I(u). So, since S~(T\) > 2,
|I(u) n 7(v)| = |7(u)| = dr(u) > 2. Also, since u V{T\) and v $ V(Ti),
we know that 0(v) C 0(u). Thus, 0(u) f! 0(v) = 0(v). If v V(Tm), then
V(Tm) C 0(v), and so |0(u)nO(u)| > |V(Tm)| > 3. So, assume that v G V(Tm).
Then \0(u) fl 0(n)| = |0(^)| = d+(v) > 2.
Case 5: Suppose that u G V(Tm) and v £ V(Tm). Since v £ V(Tm), O(u) C
V(Tm) C 0(v), and so 0(u) fl 0(v) = 0(u). So, since S+(Tm) > 2, \0(u) fl
0{v)\ = |0(n)| > 2. Now, if v G V{T{) then as in case 4, |7(u) fl I(v)\ > 2. So,
33


assume that v V{T\). Then, every vertex in 7\ beats both u and v, and so
|J()n/()|>|V(7i)|>3.
Now, assume that T is quadrangular. Since T is quadrangular, if u,v £
V(Ti), then \I(u) fl I(v)\ ^ 1, so T\ is in-quadrangular. Also, since T is quad-
rangular, if u,v £ V(Tm) then \0(u)C\0(v)\ ^ 1, and so Tm is out-quadrangular.
Now, pick u £ V(Ti) and v £ V(Tm). Then, 0(u) D 0(v) = 0(v), and
I(u) fl I(v) = I{u). Since T has no receiver, d+(v) > 1, and so we must have
that d+(v) = |0(d)| = 10(u) nO(r)| > 2. Thus, 8+(Tm) > 2. Also, since T has
no transmitter, d~(u) > 1, and so d~{u) = \I(u)\ = \I(u) fl I(v)\ > 2. Thus,
5(Ti) > 2. These are exactly the conditions from the theorem statement, and
so the result follows.
In studying tournaments which are quadrangular, the previous results allow
us to restrict our attention to strongly connected tournaments. Beyond this,
as we will see in Chapter 4, a necessary condition for a tournament to be the
digraph of an orthogonal matrix is to be strongly connected.
2.3 Tournaments with given minimum degrees
We now look at tournaments with a given minimum out-degree or in-degree.
In the previous section we studied tournaments with minimum out-degree or
in-degree 0. In Theorem 2.8 and Corollary 2.9 we characterize quadrangular
tournaments with minimum in-degree 1 or minimum out-degree 1 respectively.
The following results show that no tournament with a vertex of out-degree or
in-degree 2 or 3 can be quadrangular. First we give some lemmas.
Lemma 2.6 Let T be a quadrangular tournament with a vertex x of out-degree
1. Suppose x > y ,then 0(y) = V(T) {x,y}
34


Proof: Suppose there exists a vertex v in V(T) {x, y} such that v > y.
Then, since 0(x) = {y}, \0(x) D 0(v)\ = |{y}| = 1. This contradicts the
quadrangularity of T.
Applying Lemma 2.6 to the dual of T we obtain the following lemma.
Lemma 2.7 Let T be a quadrangular tournament with a vertex x of in-degree
1. Suppose y > x, then I(y) = V(T) {x,y}.
Theorem 2.8 Let T be a tournament on 4 or more vertices with a vertex x of
out-degree 1, and suppose x > y. Then, T is quadrangular if and only if
1. 0(y) = V(T)-{x,y},
~f(T- {x,y}) > 2,
3. y((T {x.y})') > 2.
Proof: First, suppose that T is quadrangular. Then, by Lemma 2.6,
0(y) = V(T) {x,y}. Now, pick distinct vertices u andu in T {x,y}. Since
x G 0(u) fl 0(v) there must exist some other vertex w in T x for which
w G 0(u) fl 0(v). Since 0(y) = V(T) {x,y}, this vertex w must be in
T {x,y}. So, there exists w G V(T) {x,y} such that w G 0(u) flO(u). This
is equivalent to saying 7((T {x,y})r) > 2. Also, y G I(u) fl I(v). So, since T
is quadrangular, there must exist a vertex z in T y such that z E I (u) fl I(v).
Since O(x) = {?/}, this vertex must be in T{x, y}. So, we must also have that
7(T {x,y}) > 2. Now, if v G V(T) {x,y} then I{v) D/(m) = I(v). So, these
conditions are necessary.
35


Now assume that T is a tournament with a vertex x such that 0(x) = y,
and 0(y) = V(T)~ {x,y}, 7(T {x,y}) > 2, and 7((T (x,y})r) > 2. Pick
distinct u,v £ V(T). We show T is quadrangular using three cases.
Case 1: Suppose u, v £ V(T) {x,y}. Then, x £ 0(u) fl 0(v), and since
7((T {x, y})r) > 2, there exits w £ V(T) {x,y} such that w £ 0(u) flO(u).
Thus, 10(u) D 0(v) | > 1. Also, y £ I(u) fl I(v), and since 7(T {x, y}) > 2
there exists z £ V(T) {x,y} such that z £ I(u) fl I(v). So, |I(u) fl I(v)\ > 1.
Case 2: Suppose that u = x. Then 0(u) = {y} and since y $ 0(v),
10(u) nO(v)| = 0. Now, I(u) nl(v) I(v) {y} since u = x. By Theorem 1.6,
5~(T-{x,y}) > 7(T {x,y}) 1 > 2, and so \I(u)Dl(v)\ = \I(v) {j/}| > 2.
Case 3: Suppose that u = y. Then, I(u) = {a;} and since x £ I(v),
|/(tt)fl/(t;)| = 0. Now, 0(u) fl 0(v) = 0(v) {x} since u = y. By Theorem 1.6,
S+(T {x, y}) > 7((T{x, y})r) 1 > 2, and so |0(it)flO(u)| = \0(v){a:}| > 2.
Thus, T is quadrangular.
Applying Theorem 2.8 to the dual of T we obtain the following corollary.
Corollary 2.9 LetT be a tournament with a vertex x with in-degree 1. Suppose
y * x. Then, T is quadrangular if and only if I(y) = V(T) {x,y}, y(T
{x, y}) > 2, and 7((T {x, y})r) > 2.
Theorem 1.6 together with Theorem 2.8 and Corollary 2.9 gives us the fol-
lowing corollary.
Corollary 2.10 Let T be a quadrangular tournament with 5+(T) S~(T) = 1.
Let x and y be vertices of out-degree and in-degree 1, respectively. Then x * y,
36


0(x) = I(y) = V(T) {x, y}, 8+(T {x, y}) > 2 and 5~{T {x, y}) > 2.
Theorem 2.11 Let T be an out-quadrangular tournament and choose v £
V(T). ThenT[0(v)\ contains no vertices of out-degree 1.
Proof: Let T be an out-quadrangular tournament, and choose a vertex
v £ V(T). If a; £ Ot(v), then Ot(v) D Ot{x) = Ot[o(v)](x) and so since T is
out-quadrangular, d+[0{v)](x) = |Or[0()](a:)| = \0T(v) n 0T{x)\ ^ 1. m
Applying Theorem 2.11 to the dual of a tournament we get the following
theorem.
Theorem 2.12 Let T be an in-quadrangular tournament and choose v £ V(T).
Then T[I(v)\ contains no vertices of in-degree 1.
The only tournaments on 2 or 3 vertices are the single arc, the 3-cycle and
the transitive triple, each of which contain a vertex of out-degree 1 and a vertex
of in-degree 1. Therefore, Theorems 2.11 and 2.12 give us the following four
corollaries.
O
O
Figure 2.2: The
37


Corollary 2.13 If T is a quadrangular tournament, and v G V(T), then
d+(v) 7^ 2,3 and d~(v) ^ 2,3.
Corollary 2.14 IfT is an out-quadrangular tournament with S+(T) > 2, then
5+{T) > 4.
Corollary 2.15 IfT is an in-quadrangular tournament with S~(T) > 2, then
8~(T)> 4.
Corollary 2.16 IfT is a quadrangular tournament with 5+(T) > 2 and
6~(T) > 2, then S+(T) > 4 and 8~(T) > 4.
We now turn our attention to regular and rotational tournaments.
2.4 Regular and rotational tournaments
In this section we look at regular tournaments and rotational tournaments,
and how this affects quadrangularity. We see that regularity makes the job of
determining whether or not a tournament is quadrangular a bit easier. We give
a sufficient condition for regular tournaments to be quadrangular based on the
domination number. We also restate the problem of whether or not a rotational
tournament is quadrangular in a more number theoretic context.
Proposition 2.17 Let T be a tournament on n vertices, then T is
in-quadrangular if and only if for all distinct u,v G V(T), |0[u]U0[u]| ^ n 1.
Proof: Note that since T is a tournament I(x) = V(T) 0[x] for all
x G V(T). Since T is in-quadrangular if and only if \I(u) Pi I(v)\ ^ 1 for all
distinct u, v G V(T), we have that T is in-quadrangular if and only if for all
38


distinct u, v e V (T)
lft\l(u)nl(v)\
= |(v(r) 0\u}) n (V(T) o[v])|
= |V(T)-(0[]U0M)|
= n |0[] U 0[v}\.
Thus, T is in-quadrangular if and only if \0{u] U 0[u]| ^ n 1 for all u ^ v V(T). m
Prom this proposition, we can restate the property of quadrangularity in
tournaments as for all distinct u, v G V(T), \0(u) fl 0(w)| ^ 1 and \0{u] U
0[v]\^n-l
Theorem 2.18 A regular tournament is quadrangular if and only if it is out-
quadrangular or in-quadrangular.
Proof: Let T be a regular tournament on n = 2k + 1 vertices. Note that
for any two distinct vertices x and y in T, \0[x] nO[y]| = \0{x)C\0(y)\ +1 since
either x > y or y > x. Thus for any two distinct x, y G V (T),
|0[a;] U 0[y]| = 2k + 2 \0[x] fl 0[y}\
= n + 1 |0[x] fl 0[y\ |
= n + 1 1 |O(x) fl 0(y)|
n \0{x)PiO{y)\.
Therefore, |0[x] U 0\y\\ = n 1 if and only if |O(x) fl 0(y)\ = 1. Thus, T is
out-quadrangular if and only if it is in-quadrangular, and so it is quadrangular
if and only if out-quadrangular or in-quadrangular.
39


The previous theorem can also be taken as a corollary to the linear algebra
folk lore that regular tournament matrices are equivalent to the the class of
tournament matrices which are normal. Note, a matrix M is normal if MMJ =
MrM. Graph theoretically, this is equivalent to saying that 10(u) fl 0(v)\ =
|/(f) fl /(f)| for any two vertices u,v. A proof of this result can be found in
Appendix A.
Theorem 2.19 If T is a regular tournament with 7 (T) > 4, then T is out-
quadrangular.
Proof: Let T be a regular tournament on 2k + 1 vertices with y(T) > 4.
Assume, to the contrary ,that T is not out-quadrangular. Then there exist
distinct u, v V(T) such that 10(u) fl 0(f) | = 1. Let w be the single vertex in
0(u)n0(f), and without loss of generality assume that u > v. So, |0[f]U0[f]| =
2k since 0(u) H 0(f) = {zf} and u > v. Thus, there is only one vertex in
T {f, f} which is not dominated by u or v, call it x. Then every vertex in
T is either one of u,v,x or dominated by one of u, v,x. Hence {u, v,x} is a
dominating set of order 3 in T. This contradicts our assumption that 7(T) > 4.
Thus, T is out-quadrangular.
Applying Theorem 2.18, we get the following corollary.
Corollary 2.20 IfT is a regular tournament with 7(T) > 4, then T is quad-
rangular.
We denote by Un the rotational tournament whose symbol is{l i is odd}. In [44], Merz, Fisher, Lundgren, and Reid show that if a tournament
40


on n vertices has an n-cycle as its domination graph, then it is isomorphic to
Un. We use this fact to prove the following result, which helps us obtain our
main result on rotational tournaments.
Theorem 2.21 Let T be a rotational tournament on n 2k + 1 vertices. IfT
is not isomorphic to Un, then for all distinct u,v £ V(T), 0(u) fl 0(v) 0.
Proof: Let T be a rotational tournament with V(T) = {0,1,..., 2k}.
Assume there exist distinct vertices u, v £ V(T) such that 0(u) fl 0(v) = 0. By
the vertex transitivity of rotational tournaments, we may assume u 0. Now,
since T is regular and 0(u)C\0(v) = 0, |O[tt]UO[v]| = 2k+2 l 0 = 2k+l = n.
Thus, u and v form a dominant pair. Since T is rotational, 0(u+i)r\0(v+i) = 0
for all i. This says that {?, i -f v (mod n)} forms a dominant pair for all i. This
implies the domination graph of T is a cycle. Thus T is isomorphic to Un.
Pick n > 5. Then for 0, e V{Un), |O(0) n 0(^)| = 1. So, Un is not
quadrangular for any n > 5, and we get the following corollary.
Corollary 2.22 IfT is an n-toumament, for n > 5, which is both rotational
and quadrangular, then 0(u) fl 0(v) 0 for all u,v V{T).
Theorem 2.23 Let T be a rotational tournament on n > 5 vertices, with
V{T) = {0,1,..., n 1} and symbol S. Then, T is quadrangular if and only if
for all integers m with 1 < m < there exist distinct subsets {i,j}, {k, 1} C S
such that (i j) = (k l) = m (mod n).
Proof: Pick u ^0e V(T), and suppose S has the property stated in the
theorem. We show that 10(u) fl 0(0)| ^ 1. Then for x £ V(T) we can use the
41


vertex transitivity of T to map x to 0, and as u is arbitrarily chosen, for any
vertex y ^ x we will have \0{x) fl 0{y)\ = |O(0) n 0(u)\ ^ 1. So T will be
out-quadrangular and hence quadrangular, since T is regular. Now, if u < r-~
there exist sets {k,l} C S such that (i j) = (k l) = u (mod n). So,
i u = j (mod n) and k u = l (mod n) Thus, j, l G 0{u). Further, j, l G 0(0)
since j,l G S. Note j ^ /, for otherwise i k, contradicting {i,j} and {k,l}
being distinct sets. Thus, 10(u) fl 0(0)| >2. If u > ^ then u < ^ and
so there exist sets {k,l} C S such that (i j) = (k l) = u (mod n).
So, (j i) = (l k) = u (mod n), and the argument is the same. Thus T is
quadrangular.
Now assume that T is quadrangular. Then by Corollary 2.22, \0{u)C\0{v)\ >
1 for all distinct u, v G V(T). Thus, for all distinct u, v G V(T), we must
have that \0(u) D 0(v)\ > 2. In particular, for some m G V(T) such that
1 < m < we must have that |O(0) fl 0(m)\ > 2. Since 0(0) = S, there
must be at least 2 elements of S say j, l such that j, l G 0(m). So, there must
exist i, k G S such that i m = j (mod n) and k m = l (mod n). This makes
{i,j} and {k, 1} the sets stated in the theorem, and completes our proof.
This theorem lets us restate the existence question for quadrangular rota-
tional n-tournaments, n > 5, as the following:
For which odd integers n does there exist a set of size such that if % G S,
i (mod n) $ S and for all integers 1 < m < !Gr-, there exist distinct sets
{i, j}, {k, 1} C S such that (i j) = (k l) = m (mod n)7
The smallest such n is 11 with S = {1, 3, 4, 5, 9}. In fact, one can generalize
42


this set and verify that for n = 3 (mod 4) the set
S = jz : 1 < i < n 2, i is odd i | U j j) }
is the symbol for a quadrangular rotational tournament.
2.5 Known orders of quadrangular tournaments
In this section we determine for exactly which n there exists a quadrangular
tournament on n vertices. As we see in the proof of Theorem 2.34, the results
from sections 2.2 and 2.3 show us there are no quadrangular tournaments on
4,5,6, 7 or 8 vertices. We give constructions for quadrangular tournaments
on 9,11,12,13, and 14 vertices and a general construction for quadrangular
tournaments on 15 or more vertices. We also show that there is no quadrangular
tournament on 10 vertices in a series of results.
Before beginning, recall that up to isomorphism, there are only four 4-
tournaments. These are shown in Figure 2.3. Of these, the only tournament on
4 vertices with no vertex of out-degree 1 is a 3-cycle together with a receiver.
Similarly, the only tournament on 4 vertices with no vertex of in-degree 1 is a 3-
cycle with a transmitter. Thus, by Theorem 2.11, if a quadrangular tournament
T has a vertex v of out-degree 4, T[0(v)} must be a 3-cycle with a receiver, and
if u has in-degree 4, T[I(u)] must be a 3-cycle with a transmitter.
Theorem 2.24 There does not exist a quadrangular near regular tournament
of order 10.
Proof: Suppose T is such a tournament and pick a vertex x with d+(x) = 5.
So d~(x) = 4. Therefore I(x) must induce a subtournament comprised of a 3-
cycle, and a transmitter. Call this transmitter u. If a vertex y in 0(x) has
43


0(y) = I(x), then \0(y) D 0(w)| 1 for all w ^ u in I(x). This contradicts
T being quadrangular, so 0(y) i=- I(x) for any y E O(x). Since every vertex in
0(x) beats at most 3 vertices outside of O(x), and since T is near regular we
have that 6+(T[0(:c)]) > 1. Thus, by Theorem 2.11, we have S+(T[0(x)]) > 2.
This means that T[0(x)] must be a regular tournament on 5 vertices.
Consider the vertex it which forms the transmitter in T[I(x)]. Since u =>
I[x\ {ii}, and T is near regular, it can beat at most one vertex in O(x). If
u > 2 for any z E O(x), then 10(u) fl 0(x)| = j{j2r}| = 1 which contradicts T
being quadrangular. Thus, 2 > it for all 2 E O(x).
Since T is near regular, it has exactly 5 vertices of out-degree 5, one of which
is x. So, there can be at most 4 vertices in 0(x) with out-degree 5. Thus, there
exists some vertex in 0{x) with out-degree 4, call it v. Since x v, v beats 2
vertices in O(x) and v > u there is exactly one vertex r E I(x) {u} such that
v r. Since 0(u) = I[x] {it}, we have 10(v) n 0(it)| = |{r}| = 1. Therefore,
T is not quadrangular, and such a tournament does not exist.
The following lemmas and theorem on domination are necessary in showing
that a quadrangular 10-tournament does not exist.
Lemma 2.25 IfT is a tournament on 8 vertices with 7(T) > 3 and 7(Tr) > 3,
then T is near regular. Further, if d~(x) 3, then I(x) induces a 3-cycle, and
if d+(y) = 3, then 0(y) induces a 3-cycle.
Proof: Let T be such a tournament. By Theorem 1.6, 8~(T) > 7(T) 1 =
3 1 = 2. If T has a vertex b with 1(b) = {it, i>}, where it > v, then {it, b} forms
a dominating set of size 2. So df(x) > 3 for all x E V(T). Similarly, dfr(x) > 3
44


for all x £ V(T). Thus,
3 < dTr{x) = d£(x) = 8 1 dT(x) <7 3 = 4
for all x £ V(T). That is 3 < dff{x) < 4 for all x £ V(T), and T is near regular.
Now, pick x £ V(T) with d~{x) = 3. If I{x) induces a transitive triple with
transmitter u, then {u, x} would form a dominating set in T. Thus, I(x) must
induce a 3-cycle. By duality we have that 0(y) induces a 3-cycle for all y with
d+(y) = 3.
The 4 tournaments on 4 vertices are shown in Figure 2.3. Exactly one
of these is strongly connected. We refer to this tournament as the strong 4-
toumament, and note that it is also the only tournament on 4 vertices without
a vertex of out-degree 3 or 0.
Figure 2.3: The four 4-tournaments with the strong 4-tournament on the far
right.
Lemma 2.26 Suppose T is a tournament on 8 vertices with t(T) > 3 and
7(Tr) > 3. Then if x E V(T) with d+{x) = 4, O(x) induces the strong 4-
toumament.
Proof: By Lemma 2.25, T is near regular so pick x E V(T) with d+(x) = 4,
and let W be the subtournament induced on O(x). If there exists u £ V{W)
45


with djy(w) = 0, then since dj(u) > 3, u => I(x) and {u, x} forms a dominating
set in T. This contradicts 7(T) > 3, so no such u exists. Now assume there exists
a vertex v G V(W) with d^{v) = 3. If d^{v) = 4, then v y for some y G I{x).
So, I{v) = I[x] {y}. However, I(v) = I[x] {y} forms a transitive triple, a
contradiction to Lemma 2.25. So d^(v) 3. Now, since 5+(W) > 0, the vertices
of W v all have out-degree 1 in W. If some z G V(W) v has dj.(z) = 4,
then z => I(x) and {x, z} would form a dominating set of size 2. Therefore, all
2 G V(W) have d£(z) = 3. Since T is near regular, this implies that every vertex
of I[x\ must have out-degree 4. Further, since d^(v) = 3, O(v) C 0(x) and so
I(x) =4> v. So, each vertex of I(x) dominates x,v and another vertex of I(x).
Thus, each vertex of I(x) dominates a unique vertex of O(x) {u}. Further
each vertex of 0(x) {u} has out-degree 3 in T and so must be dominated by
a unique vertex of I(x). Label the vertices of I(x) as yi, 72, '1/3 and the vertices
of 0(x) {u} as Wi, W2, W3 so that y* > wit and Wi > yj for % ^ j. Since I(x)
and 0(x) {u} form 3-cycles we may also assume that yi > y2 ^ y3, 1/3 yi,
and w\ * w2 < w3 and W3 w\. So, 0{w\) = {w2,y2,yz} which forms a
transitive triple, a contradiction to Lemma 2.25. Hence, no such v exists and
1 < 5+{W) < A+(W) < 2 and W is the strong 4-tournament.
Theorem 2.27 Let T be a tournament on 8 vertices. Then 7(T) <2 or
7(Tr) < 2.
Proof: Suppose to the contrary that T is a tournament on 8 vertices with
l{T) > 3 and 7(Tr) > 3. By Lemma 2.25 we know that T is near regular. Let
W be the subtournament of T induced on the vertices of out-degree 4. Choose
46


x in W with d^(x) > 2. So pick x E V(T) with g?J(x) = 4 so that it dominates
at most one vertex of out-degree 4. By Lemma 2.26, 0(x) induces the strong
4-tournament. By our choice of x, at least one of the vertices with out-degree
2 in T[0(x)\ has out-degree 3 in T. Call this vertex x\. Label the vertices of
0(xi) fl O(x) as X2 and X3 so that X2 x3, and label the remaining vertex
of O(x) as xo- Note since T[0(x)] is the strong 4-tournament, we must have
x3 > xo and xq xi. Since d^(x 1) = 3, X\ must dominate exactly one vertex
in /(x), call it 2/1- Recall I(x) must induce a 3-cycle by Lemma 2.25, so we
can label the remaining vertices of I(x) as 2/2 and y3 so that 2/1 2/2 ~> 2/3
and 2/3 i 2/i- Note since 0(x 1) fl I(x) = 2/1, 2/2 i and 2/3 x\. Also, by
Lemma 2.25, 0{x\) forms a 3-cycle, so x3 2/1 and 2/1 > xi-
Now, assume to the contrary that 2/1 > xq. Then 0(2/1) = {xo, X2,2,2/2}-
Now, since 0(x3) fl O(x) = {xo}, df(x3) = 3 or else x3 => I(x) and {x,x3} is a
dominating set of size 2. So, x3 dominates exactly one of y2 or 2/3- If £3 > 2/2
then 2/3 X3 and since y3 > xi, {2/1,223} forms a dominating set of size 2. So,
assume x3 2/3 and 2/2 *" 23. Then x,y3,xy,x3 E 0(2/2), and {222,2/1} forms a
dominating set of size 2. Thus Xo 2/1-
If x3 * 2/2, then {x3,x} forms a dominating set of size 2, a contradiction.
So, 2/2 x3. If x3 -> 2/3, then 0(x3) = {2/1,2/3, 2o}- However, 2/3 - 2/1 and
xo > 2/1 so 0(x3) forms a transitive triple, a contradiction to Lemma 2.25.
Thus 2/3 > £3- Since dj.(y3) < 4 and 2/1,2,21,23 E 0(2/3), these are all the
vertices in 0(2/3). So, x0 y3.
If Xo * 2/2 then Xo => /(x) and {x, x0} is a dominating set of size 2, so
2/2 > x0. So, xQ,y3,x E 0(2/2) and 2/1,22,23 E 0(x 1), and so {2/2,21} forms a
47


dominating set of size 2. Therefore, such a tournament cannot exist.
Theorem 2.28 No 9-tournament T with 6+(T) >2 is out-quadrangular.
Proof: Assume, to the contrary, T is such a tournament. Since T is
out-quadrangular, and S+(T) > 2, by Corollary 2.14, 5+(T) > 4. Since T is a
9-tournament, this implies T must be regular. Pick a vertex x £ V(T). Then
O(x) must induce a subtournament which is a 3-cycle together with a receiver.
Call the receiver of this subtournament y. Since T is regular, d+(y) = 4. Since
I(y) = 0[x] {y}, this means 0{y) = I(x). So, 0(y) = I(x) must induce a
subtournament which is a 3-cycle together with a receiver. Call this receiver z.
Since d+(z) =4, y * z and I(x) {z} z, we have O(z) 0[x] {y}. Now,
x => 0(x) {y} and 0(x) {y} is a 3-cycle so T[0(z)\ must contain a vertex
of out-degree 1. Hence, by Theorem 2.11, T is not out-quadrangular. Thus no
such tournament exists.
Corollary 2.29 No 9-toumamentT with 6~(T) >2 is in-quadrangular.
Proof: Let T be a tournament on 9 vertices with S~(T) > 2. Then Tr is
not out-quadrangular by Theorem 2.28. Thus T is not in-quadrangular.
Corollary 2.30 No quadrangular tournament of order 10 exists.
Proof: By Corollaries 2.4 and 2.16, and by Theorems 2.1, 2.3 and 2.8, a
quadrangular tournament T must satisfy one of the following.
1. 5+(T) > 4, and hence T is near regular.
2. T has a transmitter s and receiver t such that 7(T {s,t}) > 2 and
7((r-{M}n>2.
48


3. T contains an arc (x,y) such that 0(y) = I(x) = V(T) {x,y} and
7(T {x, y}) > 2 and 7((T {x, y})r) > 2.
4. T has a transmitter s and T s is out-quadrangular with 8+(T s) >2.
5. T has a receiver t and T t is in-quadrangular with 8~(T t) >2.
Note, Theorem 2.24 implies that case 1 is impossible. If 2 or 3 were satisfied,
then there would be a tournament on 8 vertices such that it and its dual have
domination number at least 3, which contradicts Theorem 2.27. If 4 were satis-
fied, then T s would be of order 9 and out-quadrangular, a contradiction tc
Theorem 2.28. Similarly, 5 contradicts Corollary 2.29. Thus, no quadrangular
tournament on 10 vertices exists.
Theorem 2.31 There exist quadrangular tournaments of order 11,12 and 13.
Proof: Consider the quadratic residue tournament of order 11, QRn-
Recall QRn is a doubly regular tournament, so for all 1/,, v G V(QRn), \0(u) n
0(u)| = |/(it) C I{v)\ = = 2. Thus, QRn is quadrangular. Further,
this implies that for any two vertices u,v E V(QRu) there exists a vertex
which dominates both u and v, so 7(QRn) > 2. Also, since QRn is regular,
5+(Q/?n) = 5 > 2. Let W be the tournament formed by adding a transmitter
to QRn- Then by Theorem 2.3, W is quadrangular.
Now, let T be the rotational tournament on 13 vertices with symbol
S = {1,2,3, 5,6,9}. The following table gives the subsets of S which satisfy
49


Theorem 2.23. Thus, T is quadrangular.
m subsets
1 {2,1}, (3,2}
2 13,1},-|5,3}
3 15,2},]6,3}
4 16,2},19,5}
5 16,1},11,9}
6 19,3},12,9}
Theorem 2.32 There exists a quadrangular tournament of order 14.
Proof: Construct T of order 14 in the following way. Start with a set V of
14 distinct vertices. Partition V into 7 sets of order 2 labeled Vo, Vi, V2,..., V6.
Place arcs in T so that each Vj induces the 2-tournament, and Vi => Vj if and
only if j i (mod 7) is one of 1, 2,4. We show that the resulting 14-tournament,
T, is quadrangular.
Note that the condensation of T on Vo,..., V6 is just the quadratic residue
tournament on 7 vertices, QR7. Now, QR7 is doubly regular, so \0(x)nO(y) \
= 1 for all x,y G V{QR7). Thus, if u,v G V(T) such that u 6 Vj, v 6 Vj
for i 7^ j, \0(u) fl 0(v)| = 2. Further, since QR7 is regular of degree 3, if
u, v V{T) with u,v V then \0(u) fl 0(v)\ = 6. Thus, |0(it) D 0(u)| ^ 1
for all u, v 6 V(T), and so T is out-quadrangular. Now, since QR7 and the
2-tournament are isomorphic to their duals, a similar argument shows that T is
in-quadrangular and hence quadrangular.
Theorem 2.33 If n > 15, then there exists a quadrangular tournament on n
vertices.
50


Proof: Pick n > 15. Let i
integers such that a, > 5 for each z, and a* = n. Pick / regular or near
t=i
regular tournaments Ti,T2, ... ,7} such that |F(Tj)| = a* for each z. Let T' be
a tournament with V(T') = {1,2,3,.../} such that T' has no transmitter or
receiver. Construct the tournament T on n vertices as follows. Start with a
set V of n vertices, and partition V into sets Si, S2,..., Si of size aq, a2,..., a;
respectively. Place arcs in each 5, to form Tj. Now, add arcs such that S, => Sj
if and only if i > j in T'. We claim that the resulting tournament, T, is
quadrangular.
Pick u,v GV (T). We consider two possibilities. First, suppose that u,v Si
for some i. By choice of T', i * j for some j. Thus
|0(u) fl 0(v)| > IS'jl = aj > 5 > 1.
Now, suppose that u G Si and v £ Sj for i 7^ j. Since T' is a tournament either
i > j or j i. Without loss of generality, assume that i > j. Then
10(u) n0(v)| > 10(v) nSj| > > 2 > 1.
This shows that T is out-quadrangular. The proof that T is in-quadrangular is
similar. Thus, T is a quadrangular tournament of order n > 15.
Observe that if T' in the construction is strong, then T is strong. Further,
if Oj = k for all i and T' is regular, then T is regular or near regular depending
on if k is odd or even. We now characterize those n for which there exist a
quadrangular tournament of order n.
51


Theorem 2.34 There exists a quadrangular tournament of order n if and only
if n = 1,2,3,9 or n> 11.
Proof: Note that the single vertex, the single arc, and the 3-cycle are
all quadrangular. Now, recall that the smallest tournament with domination
number 3 is QR7. Further, QR7 is isomorphic to its dual, so QRj) = 3. This
fact together with Theorems 2.8 and 2.1 tell us that the smallest quadrangular
tournament, T, on n > 4 vertices with 5+(T) = 5~(T) = 0 or 5+(T) = 1 or
S~(T) 1 has order 9.
Theorem 2.3 and Corollary 2.4 together with the fact that QR7 is the small-
est tournament with domination number 3 imply that a quadrangular tourna-
ment with just a transmitter or receiver must have at least 8 vertices. However,
QR7 is the only tournament on 7 vertices with domination number 3 and since
|O(x) fl 0(y)| = |/(x) fl I(y)\ = 1 for all x ^ y G V(QR7), QR7 is neither
out-quadrangular nor in-quadrangular. So, QR7 together with a transmitter
or receiver, but not both, is not quadrangular, and hence any quadrangular
tournament with a transmitter or receiver, but not both, must have order 9 or
higher.
Corollary 2.16 states that if S+(T) > 2 and S~(T) > 2, then S+(T) > 4 and
6~(T) > 4. The smallest tournament which meets these requirements is a regular
tournament on 9 vertices. Thus, there are no quadrangular tournaments of order
4,5,6, 7 or 8. The result now follows from Corollary 2.30 and Theorems 2.31,
2.32 and 2.33.
As it turns out, not only do there exist quadrangular n-tournaments for
52


n = 9 and n > 11, but quadrangularity is a common (asymptotic) property in
tournaments. We finish the chapter with the following probabilistic result.
Theorem 2.35 Almost all tournaments are quadrangular.
Proof: Let P(n) denote the probability that a random tournament on n
vertices contains a pair of distinct vertices x and y so that \0(x) fl 0(y)\ 1.
We now give an over-count for the number of labeled tournaments on n vertices
which contain such a pair, and show P(n) > 0 as n > oo.
There are (£) ways to pick distinct vertices x and y, and the arc between
them can be oriented so that x * y or y x. There are n 2 vertices which
can play the role of z where {z} = O(x) fl 0(y). For each w 0 {x,y, zj there
are 3 ways to orient the arcs from x and y to w, namely w => {x,y}, w > x
and y > w, or w y and x w. Also, there are n 3 such w. The arcs
between all other vertices are arbitrary. So there are 2^ 2 ) ways to finish the
tournament. When orienting the remaining arcs we may double count some of
these tournaments, so all together there are at most
tournaments containing such a pair of vertices. Now, there are 2^) total labeled
53


tournaments so,
0 < P{ri) <
2(3 (n-2)3(n~3)2(V)
W)
n(n 1 )(n 2)3(n~3)2(22)
2(n22)+n_2+n-1
n(n 1 )(n 2)3n_3
22ra-3
n(n l)(n 2)3-3
22(-3)23
n(n 1 )(n 2) /3\n_3
8 U;
|n(w- l)(w 2)
(|)-3
Since this value tends to 0 as n tends to oo, it must be that P(n) > 0 as n > oo.
From duality we have that the probability that vertices x and y exists such
that \I(x) C\ I(y)\ = 1 also tends to 0 as n tends to oo. Thus, the probability
that a tournament is not quadrangular tends to 0 as n tends to oo. That is,
almost all tournaments are quadrangular.
54


3. Strongly Quadrangluar Tournaments
3.1 Definitions and background
In this chapter we look at a stronger necessary condition for a digraph to
support an orthogonal matrix. Let D be a digraph. Let S C V(D) such that
for all u £ S, there exists v £ S such that 0(u) fl O(v) ^ 0, and let S' C V(D)
such that for all u S', there exists v £ S' such that I(u) n I(v) ^ 0. We say
that D is strongly quadrangular if for all such sets S and S',
(i)
U (o(u)no(v))
u,vES
>|S|,
(ii)
U (I(u)ni(v))
u,v&S'
> m.
In [56], Severini showed that strong quadrangularity is a necessary condition for
a digraph to support an orthogonal matrix, where the entries in the matrix come
from a field of characteristic 0 (ex. the rational numbers, the real numbers or
the complex numbers). We give a proof of this result here for completeness.
Theorem 3.1 If D is the digraph of an orthogonal matrix over a field of char-
acteristic 0, then D is strongly quadrangular.
Proof: Let F be a field of characteristic 0. Let D be a digraph which
supports an orthogonal matrix U over F, and assume, to the contrary, that D is
not strongly quadrangular. So, there exists a set S C V(D) so that for all u E S,
there exists v S such that 0(u) fl 0(v) ^ 0 and | ^ ^(v))l < |'S'|,
or we can find a set S' C V(D) so that for all u £ S', there exists v 6 S' such
55


that I{u) PI I(v) ^ 0 and | (Ju ves>(Hu) ^ -f(^))| < |S'/|. We deal with the first
case, and note the second is a,similar argument. Let Q = (Ju v&s(0(u) ^ 0(v))-
Let R denote the set of rows in U which correspond to the vertices of S, and let
C denote the set of columns of U which correspond to vertices of Q. Let R! be
a set of row vectors obtained from R by restricting these vectors to the entries
which occur in C.
Pick distinct row vectors i?'# and R'Jt from R', let Ut, and U}, be the corre-
sponding rows of U in R, and let Xi and xj be the vertices in D which correspond
to C/j. and U3, respectively. Since O(xi) ft 0(xj) C Q, the only entries of Ult
and Uj. which contribute nonzero terms to ([/,.. U]t) occur in the columns of C.
So, (/?'., RjJ) {Ui Uj,) = 0. Thus, R! is a set of mutually orthogonal vectors.
However, R! is a set of vectors in This is a contradiction, because this is a
set of |S'| mutually orthogonal vectors in a vector space of dimension |Q| < \S\.
Thus, D must be strongly quadrangular.
In a field of non-zero characteristic, orthogonal vectors need not be linearly
independent, so we would not have been able to draw the above contradiction.
To emphasize this, consider the matrix
(l 1 100000\
11010000
11001000
11000100
A~ 1 1000010
11000001
10111111
\0 1111111/
Let D be the digraph whose adjacency matrix is A. Over GF(2), there is only
one matrix with pattern A, namely A. One can quickly verify that AAr = I over
56


GF(2). If S C V(D) corresponding to the first 6 rows of A, then |
0(n))| = 2 < |S|, so D is not strongly quadrangular. So, strong quadrangularity
is only a necessary condition when dealing with fields of characteristic 0. For
this reason we will only deal with fields of characteristic 0 for the rest of the
chapter.
To see that strong quadrangularity is in fact a more restrictive condition,
consider the following tournament. Let T be a tournament with V(T) =
{0,1, 2,3,4,5,6,x,y} so that {0,1, 2,3,4, 5,6} induces the tournament QR7,
x > y and 0(y) = I(x) = V(T) {x,y}. In section 2.5, we saw that T is
quadrangular. Now consider the set of vertices S = {0,1,5}. Since each of 0,1,5
beat x, we have that for all u E S, there exits v G S so that 0{u) n 0(v) ^ 0.
Also,
U (O(u)no(u))
u,v£S
= 1(0(0) n 0(1)) u (0(0) n 0(5)) u (O(i) n 0(5))]
= I{2, x} U {2, x) U {2, x}|
= 2
<\s\.
So T is not strongly quadrangular. We now construct a class of strongly quad-
rangular tournaments.
3.2 A class of strongly quadrangular tournaments
In this section we construct a class of strongly quadrangular tournaments.
The following lemma is a well known fact of tournaments. It is a corol-
lary to the fact that every n-tournament contains a transitive (Llg2(n)J + 1)-
subtournament. We prove it here for completeness.
57


Lemma 3.2 Let T be a tournament on n > 4 vertices. Then there must exist
distinct a,b e V(T) such that 0(a) D 0(b) ^ 0.
Proof: Pick a vertex a of maximum out-degree in T. As, n > 4, d+(a) > 2.
Pick a vertex b of maximum out-degree in the subtournament W induced on
0(a). As d+(a) > 2, d^(b) > 1. Thus, 10(a) D 0(6)| = d^(b) > 1.
Theorem 3.3 Pick l > 1. Let T' be a strong tournament on the vertices
{1,2,...,/}, and let Ti, T2,..., 7} be regular or near-regular tournaments of or-
der k > 5. Construct a tournament T on kl vertices as follows. Let V be a set
of kl vertices. Partition the vertices of V into l subsets Vi,..., Vi of size k and
place arcs to form copies 0/T1, T2,..., T} on Vi,..., Vi respectively. Finally, add
arcs so that V => Vj if and only if i > j in T. Then the resulting tournament,
T, is a strongly quadrangular tournament.
Proof: Pick S C V(T). Define the set
A = {Vi : 3u ^ v 6 S 3 u,v G Vi},
and define the set
B = {Vi : 3!u e 5 9 u e Vi}.
Let a = |A|, and f3 = \B\. Then, since each V has k vertices, ka + (5 > |5|.
Consider the subtournaments of T' induced on the vertices corresponding to A
and B. These are tournaments and so must contain a Hamiltonian path. So,
label the elements of A and B so that A\ =4> A2 => => Aa and Bi => B2 =$
=> Bfj. By definition of A, each A, contains at least two vertices of S. and
58


so if x,y S and x,y £ Aif for i < a 1, then Ai+i C 0(x) ft 0(y). Thus,
|^J 0(u) fi 0(v)
u,v£S
> k(a 1).
We now consider three cases depending on (3.
First assume that (3 > 2. Consider the vertices of S in B we see that if
x,y e S and x G and y £ Bi+1 then 0(y) fl Bi+1 C O(x) fl 0(y). Thus,
|O(x) fl O(y)| > and so
[J 0(u) n 0(v)
u,vES
> k(a-1)+ ^ -*(13-
1) > fc(a 1) + 2/3 2 > fc(a-l) + 0.
Now, since T' is a tournament, either A\ => B\ or B\ => Ai. If A\ B\, then
for vertices x, y £ A\ we know Bi C 0(x) C1 O(y). Since no vertex of B\ had
been previously counted, we have that
[J 0(u) fl 0(v)
u,v£S
> k(a
1) + (3 + k
ka + f3 > |*S|.
So, assume that B\ => A\. Then for the single vertex of S in Bi, u, and a
vertex v of S in A\ 0(v) C 0{u)C\ 0(v). This adds ^ vertices which were not
previously counted. Also, since T' is strong, some Ai => V3 for some V3 A.
We counted at most vertices in V3 before, and since At contains at least
two vertices x, y from S these vertices add at least vertices which were not
previously counted, so
0(u) fl 0(v)
w,t;6 S
> k(a -!) + /? + y +
k + 1
2
ka + (3 > 151.
Now assume that (3 = 1. Since T' is strong we know that Ai => V3 for some
V3 & A. So,
|^J 0(u) fl 0(v)
u,v£S
> ka.
59


Now, if 151 < ka, then we are done, so assume that l^l = ka + 1. So, for every
Ai 6 A, At C S. So by Lemma 3.2 we can find two vertices of S in A\ which
compete over a vertex of Ai, adding one more vertex to our count, and
0(u) D 0(v)
u,vGS
>ka + l = |S|.
For the last case, assume that (3 = 0. Then since T' is strong we once again
have that some At => Vj for some V3 0 A. Thus,
0(u) fl 0(v)
u,vES
> ka > |5|.
Note that the dual of T' will again be strong, and the dual of each T,
will again be regular. Thus, by appealing to duality in T we have that for all
S C V{T),
U /(u)nJ(v)
utv^S
>|5|,
and so T is a strongly quadrangular tournament.
Recall that strong quadrangularity is a necessary condition for a digraph
to support an orthogonal matrix. To emphasize that strong quadrangularity
is not sufficient, consider the strongly quadrangular tournament, T, which the
construction in the previous theorem gives on 15 vertices. For this tournament,
T\,T>2 and T3 are all regular of order 5, and T' is the 3-cycle. Note that up
to isomorphism, there is only one regular tournament on 5 vertices, so without
loss of generality, assume that Ti, T2 and T3 are the rotational tournament with
symbol {1,2}. We now show that T cannot be the digraph of an orthogonal
matrix.
60


Recall J5 is the 5x5 matrix of all ones, and O5 the 5x5 matrix of all Os.
Set
RT5
/01100\
00110
0001 1
1000 1
\11000/
Then the adjacency matrix M of T is
/ RT& J5 O5 \
M = I O5 RT5 J5 1
V J5 O5 RT5J
Now, suppose to the contrary that there exists an orthogonal matrix U whose
pattern is M. Observe from the pattern of U that the only entries of U which
contribute to (Uu Uj) for i ,5,/ = 6,.. ., 10 are in the first five rows. So,
(UuUj): - UiiUAj + 5 ,j for j = 6,. -, 10. Thus, since 0 = (f/i, C/j) for each
3 ^ 1,
77. , 1 1 1 <£> £ 1 1 f/5,1 f/5,7 l/sul/s,! 8 1/5,11/5,9 1/5,1 C/5,10
<^4,1 t/4,6 C/4,7 1/4,8 f/4,9 f/4,10
Since U8t 1 7^ 0 this gives,
f/4,1 C/5,6 1/5,7 C/5,8 I/5,9 f/5,10
t/5,1 t/4,6 U4,7 - t/4,8 f/4,9 f/4,10
So, the vectors (C/4i6, .. 11/4,10) and (1/5,6) i f/5,10) are scalar multiples of
each other. Now, note that for j = 6,..., 10, we have 0 = (f/2, Uj) =
So, by applying the same argument, we see that the vec-
tor (C/5,6, f/5,7, C/5,8, f/5,9) C/5,10) is a scalar multiple of (f/1,6, f/1,7, f/1,8, t/1,9, f/i.io)-
So, (U4,6, t/4,7, f/4,8, f/4,9, f/4,10) is a scalar multiple of (t/i,6, f/1,7, f/1,8, C/1,9, C/i,io)-
Now, from the pattern of U we see that only the 6th through lQth columns con-
tribute to (Ui,, U4,}. So, since linearly dependent vectors cannot be orthogonal,


This contradicts our assumption that U is orthogonal. So, T is not the digraph
of an orthogonal matrix.
3.3 Nonexistence and searches
The only known tournament which supports an orthogonal matrix is the
3-cycle (This is a permutation matrix, and hence itself an orthogonal matrix).
Otherwise, the problem of determining whether or not there exist tournaments
which support orthogonal matrices has proved to be quite difficult. As we have
seen, for large values of n we can almost always construct examples of tourna-
ments which meet our necessary conditions. Knowing that almost all tourna-
ments are quadrangular and having a construction for an infinite class of strongly
quadrangular tournaments, one may believe that there will exist a tournament
which supports an orthogonal matrix. However, attempting to find an orthog-
onal matrix whose digraph is a given tournament has proved to be a difficult
task. In general, aside from the 3-cycle, the existence of a tournament which
supports an orthogonal matrix is still an open problem. The following result
may lead one to believe non-existence is the answer to this problem.
Theorem 3.4 Other than the Z-cycle, there does not exist a tournament on 10
or fewer vertices which is the digraph of an orthogonal matrix.
Proof: By Theorem 2.34 there exists a quadrangular n-tournament for
n < 10 if and only if n is 1, 2, 3 or 9. Note, in the case n 1 and n = 2,
the only tournaments are the single vertex and single arc, both of whose ad-
jacency matrices have a column of zeros. Since orthogonal matrices have full
rank, these cannot support an orthogonal matrix. When n = 3, the 3-cycle is
the only quadrangular tournament. The adjacency matrix for this tournament
62


is a permutation matrix and hence orthogonal. Now consider n = 9. By The-
orem 2.28, if T is quadrangular, 5+(T) < 1. If S+(T) = 0, then Ts adjacency
matrix will have a row of zeros, and T cannot be the digraph of an orthogonal
matrix. So we must have S+(T) = 1. So by Theorem 2.8, T has an arc (x, y) with
0(y) = I(x) = V(T){x,y} and 7(T{x, ?/}) > 2. The only 7-tournament with
domination number greater than 2 is QR7, thus T {x,y} = QR7. However,
in section 3.2 we observed that this tournament is not strongly quadrangular.
Thus, other than the 3-cycle, no tournament on 10 or fewer vertices can be the
digraph of an orthogonal matrix.
If one believes existence is the answer, they could attempt to simplify the
search for an orthogonal matrix whose digraph is a tournament by looking for
weighing matrices whose patterns are tournament matrices. An (n, k)-weighing
matrix is an n x n matrix M with entries from {0,1, 1} such that MrM =
MMt = kl. That is, each row and column of M contains exactly k non-
zero entries, and any two rows and any two columns are orthogonal. One first
observes that if a tournament is to be the digraph of a weighing matrix, the
tournament will be regular. So, we can restrict our search to regular tournaments
and hence (2k + 1, A;)-weighing matrices. The following propositions give us
another restriction.
Proposition 3.5 Let T be a regular n-tournament. If T is the digraph of a
weighing matrix, then \0(u) fl 0(u)| and |I(u) D 7(u)| are even for all distinct
u,veV(T).
Proof: Assume T is the digraph of some weighing matrix M. Pick
63


u, v G V(T) and let MU,,MV. be the rows of M which correspond to u and
v respectively. Note, 0 = (Mu Mv,) = MuAMvA + MUy2MVy2 -\--------+ Mu Now, MU'iMVti 7^ 0 if and only if i G 0(u) n 0(v). Since (MU,,MV,) = 0, and
every non-zero term of is 1, we have that the number of nega-
tive terms in the sum must equal the number of positive terms. So, the number
of non-zero terms in the sum must be even. Hence, |0(u) fiO(u)| must be even.
Similarly, |I(u) fl/(u)| must be even.
Proposition 3.6 Let T be an n-tournament. IfT is the digraph of a weighing
matrix, then n = 1 or 3 (mod 8).
Proof: Assume that T is the digraph of some weighing matrix. Note, that
this implies T is a regular tournament. Now, choose u G V(T), and v e 0(u).
By Proposition 3.5, \0(u) fl 0(v)\ is even. Equivalently, d+0(u^(r) is even.
Since v was chosen from 0(u) arbitrarily, dfp^(x) is even for all x G O(u).
Thus, (^2(u)) = SxeO(u) dT[0(u)\ (x) must be even- So> 2|dr(u)(dJ(u)~1), and so
A\dj.(u)(dj^(u) 1). Since df(u) and df(u) 1 must be relatively prime, we
have that 4| dif{u) or 4| df(u) 1. Since T is a regular tournament, dff(u) =
So, 41^^ or 4|n^, and so 8|n 1 or 8|n 3. Hence n = 1 or 3 (mod 8).
The following condition is well known for (n, /c)-weighing matrices in which
n is odd. We prove it here for completeness.
Theorem 3.7 [27]// M is an (n, k) weighing matrix with n odd, then k is a
perfect square.
Proof: Let M be an (n, k)-weighing matrix, and assume n is odd. Then
det(MrM) = det(kl) = kn. Since, det(MT) = det(M) and det(MTM) =
64


det(MT) det(M), we have that det(M)2 = kn, and so det(M) = \/fc. Since n
is odd, n 2b + 1 for some b, and so det(M) = kby/k. Now, the determinant
of M is J2aesn ^i, of order n). So, since every entry of M is an integer, det(M) must be an integer
as well. Thus, kby/k E Z, and so y/k E Z. That is, A; is a perfect square.
Since a weighing matrix which has a tournament for its digraph will be a
(2k + 1, A;)-weighing matrix, the previous theorem tells us we are looking for a
(2a2 + 1, a2)-weighing matrix. By examining cases, we get Proposition 3.6 as
the following corollary to Theorem 3.7.
Corollary 3.8 LetT be a regular n-tournament. IfT is the digraph of a weigh-
ing matrix, then n = 1 or 3 (mod 8).
Putting together the fact that we are looking for a (2a2 + 1, a2)-weighing
matrix with Theorem 3.4, we see that the smallest case we can start searching
for is a (19,9)-weighing matrix. One obvious choice for a tournament to search
is QR19, since this is a regular 19 vertex tournament with the property that the
outsets of every two vertices intersect in exactly 4 vertices. With the aid of Carey
Jenkins, we constructed the following algorithm to search for a (19,9)-weighing
matrix whose digraph is QR\9. A tree diagram of the branch and bound
technique used in this algorithm is shown in Figure 3.1. In this diagram, circled
vertices represent the rows our algorithm has currently appended, and dashed
lines show paths which, by design of our algorithm, we need not search.
First construct and store all 29 = 512 possible assignments of 1 to the
65


Rows
Figure 3.1: The tree diagram for our algorithm
non-zero entries of the first row of the adjacency matrix of QRiq,
Rlfl = (0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 0).
Label these as Rij where j is a number between 0 and 511 which labels each
different assignment of Is to the vector. Next, construct all cyclic shifts of
these rows. Label each row created in this way so that Ritj is Rij shifted i 1
positions to the right. Since the adjacency matrix of QRig is circulant, this
creates all possible assignments of 1 to the non-zero positions of row i, for
i = 2,..., 19.
We attempt to build a matrix by appending rows. We begin with the first
row Ri'O above. Lemma 3.9 shows why we can leave this row fixed. For = 0,
66


compute (Rip, R2,j2)- If (#i,0) #2j2) = 0> we append R2j2 and move on to
find R3j3 which is orthogonal to Ri o and R2,j2 If not, increment j2 and repeat.
Continue adding rows in this manner. Assume we have a matrix with i mutually
orthogonal rows,
/ #1,0 \
#2,J2
\ /
Set ji+i = 0, and begin successively checking if Ri+iji+1 is orthogonal to each
previously selected row, and incrementing ji+i by 1 if not. If there is some
#+ij'i+i which is orthogonal to each of the previously selected rows, then ap-
pend it. If ji+1 reaches 512, and hence there does not exist a Ri+iJi+1 which is
orthogonal to each of the previous rows, then return to row i, increment ji, and
search for a new Rij. which is orthogonal to each of the previous i 1 rows.
At each step the algorithm is maintaining a set of mutually orthogonal rows,
so if it finds 19 rows successfully, then it has created a (19, 9)-weighing matrix
whose digraph is QR\g. Otherwise, for some k < 19, ji will reach 512 for all
2 < i < k, and we will have completely searched all possible combinations of
the first k rows without finding a set of k mutually orthogonal rows, and the
algorithm terminates showing no such matrix exists.
The C-|b code for our implementation of this algorithm can be found in
appendix B. The algorithm was implemented in parallel on the Universitys
Beowulf cluster. The search was split by giving the first 16 possible assignments
of row 2 to the first processor, the next 16 to the next processor, and so on.
After approximately 5 minutes, the algorithm terminated showing that QR\g is
not the digraph of a weighing matrix.
67


Lemma 3.9 Let M be an (n, k)-weighing matrix, and let M' be the matrix
obtained from M by multiplying any set of the rows of columns by 1. Then M'
is an (n, k)-weighing matrix.
Proof: Let S C {1,..., n}, be the indices of the columns of M multiplied
by 1 to obtain Mand 5" the indices of the rows multiplied by 1 to obtain
M'. Let Ds be the diagonal matrix whose i, i entry is 1 if i G S and 1 if i £ S.
Define Ds> to be the diagonal matrix whose i,i entry is 1 if i G S' and 1 if
i £ S'. Note since (1)(1) = 1*1 = 1, Ds and D$> are their own inverses.
Also, M' = Ds'MDs. So,
M'tM' = {DS'MDs)t (Ds'MDs)
= D]MtD], Ds'MDs
= DsMt Ds> Ds< MDs
= DSMJI MDs
= DsMtMDs
= Ds{kI)Ds
= kDsIDs
= kDsDs
= kl,
and M' is an (n, /c)-weighing matrix.
68


4. Fully Indecomposable Tournament Matrices
4.1 Definitions and background
Another combinatorial necessary condition for a matrix to be orthogonal is
that it can be written in block form
where each Ai is fully indecomposable. This is a combinatorial property, so it is
also required of a (0, l)-matrix to be the pattern of an orthogonal matrix. So,
in this chapter, we determine exactly which tournaments have adjacency matri-
ces which are fully indecomposable, and characterize the separable tournament
matrices.
Let A be an n x n matrix, n > 2. Then A is called partly decomposable
provided there exist permutation matrices P and Q such that
where O is an r x s matrix of zeros with r + s n, and B and C are square
matrices other than the zero matrix. If A cannot be permuted into this form,
then we say that A is fully indecomposable. If A has a row or column of zeros,
or we can independently permute the rows and columns of A so that
fAi O O 0\
O A20 O
O O A3 O
\0 O O ... AkJ
69


then we say that A is separable. This property has also been called totally
decomposable, by Brualdi, Harary and Miller, [11], and disconnected by Green-
berg, Lundgren, and Maybee, [29]. If a matrix is not separable, we say it is
inseparable.
If we require simultaneous row and column permutations, then we say a
BO'
matrix which can be permuted into the form ^ J is reducible, and irreducible
otherwise. If M is the adjacency matrix of a digraph D, it is a well known
result that M is irreducible if and only if D is strongly connected. However,
as mentioned in chapter 1, independent row and column permutations do not
necessarily result in the same digraph. So, it is difficult to determine just what
these properties mean in digraphs.
Since independent row and column permutations do not necessarily result
in isomorphic digraphs, when looking at a matrix property that allows for inde-
pendent row and column permutations, one typically wants to treat the matrix
as a reduced adjacency matrix of a bipartite graph. Given a bipartite graph
B with bipartition X = {aq,..., xm} and Y {yu ..., yn}, the reduced adja-
cency matrix of B is the m x n (0, l)-matrix M with Mjj = 1 if and only if
[xi,yj\ 6 E(B). By treating a (0, l)-matrix as the reduced adjacency matrix of
a bipartite graph, independent row and column permutations will result in the
reduced adjacency matrix of an isomorphic bipartite graph. For instance, con-
sider the following matrix M. By exchanging the 5th and 7th rows, and swapping
70


the 1st and 3rd and the 2nd and 5th columns we obtain the matrix M'.
M =
/ 0100000\
0001000
1000000
0010110
0000001
0000100
\0000010/
M' =
/0000100\
0001000
0010000
1100010
0000010
0100000
\0000001/
Both M and M' represent the same bipartite graph B shown in Figure 4.1. How-
ever, M and M' represent the digraphs D and D' respectively from Figure 4.2,
and clearly D and D' are not isomorphic.
oo
oo
oo
oo
Q
ooooo
Figure 4.1: A bigraph representation of M and M'
Despite this problem, we are interested in characterizing tournaments with
properties which require independent row and column permutations. So, we
study how these properties affect digraphs, and in particular, tournaments. For
fully indecomposable digraphs, we look at the matrix before the permutations,
and for separable matrices we look at competition graphs.
We obtain our characterization of separable tournament matrices by utiliz-
ing the characterization of the competition graphs of tournaments via the char-
acterization of the domination graphs of tournaments. We will also use these
71


Figure 4.2: Different digraph representations for M and M'.
characterizations to obtain some interesting corollaries about tournaments and
tournament matrices. We see exactly when a tournament matrix has a mini-
mum line cover other than the all rows or all columns cover. We characterize the
tournaments which are the digraphs of doubly-stochastic matrices, and give a
necessary condition for a tournament to be the digraph of an orthogonal matrix.
We also characterize the tournaments for which every arc is contained in a cycle
factor.
4.2 Fully indecomposable matrices
Let M be the adjacency matrix of a digraph D, and suppose M is partly
decomposable. So we can perform independent row and column permutations
to create an r x s block of zeros in M with r + s = n. By permuting the rows
and columns of M back to their original positions, we see that the block of
zeros corresponds to two sets of vertices X and Y, not necessarily disjoint, with
|X| = r and |F| = s, and there is no arc (x, y) with x X and y G Y. We
72


use this interpretation of the partly decomposable property to get the following
theorem.
Theorem 4.1 Let T be a tournament on n vertices, and let M be its adjacency
matrix. Then M is fully indecomposable if and only if T is strongly connected
and does not contain a vertex v such that T v contains a strong component of
order 1.
Proof: Suppose M is partly decomposable. So there exist sets X, Y C
V(T) so that there is no arc of T from X to Y, and |X| + |F| = n. Suppose
that \X D Y| > 2. Then there exist distinct vertices u, v £ X D Y. Since T is a
tournament either u v or v > u. Without loss of generality say u > v. This
cannot be since u G X and v G Y. Therefore \X fl Y\ < 1. We now consider
two cases based on \X fl F|.
Case 1: Suppose \X fl Y\ = 0. Then since |X| + |F| n, X and Y form a
partition of the vertices of T. Thus, since X and Y partition V (T) and no
vertex in X beats any vertex in Y, T is not strongly connected.
Case 2: Suppose \X n Y\ = 1. So X D Y = {u} and XU Y = V(T) {u} for
some u v 6 V(T). Further, since u G Y, u => X {} and since u X,
Y {u} => u. Finally, since no vertex in X beats any vertex in Y, we have
Y X {it}. Thus, T v contains a strong component of order 1, namely u.
For the converse, recall that if a tournament is not strongly connected, it can
be partitioned into m > 2 strong components Ti,T2, Tm such that T* => Tj if
and only if < j. So, if T is not strongly connected, then taking X = V(Tm) and
Y = V(Ti)CV(T2)U- -UF(Tro_i) gives X and Y so that |X| + |y| = n and there
73


is no axe from X to Y. Now, suppose T contains a vertex v so that T' T v
is not strongly connected and has a strong component, say T', of order 1. Then
take X = V(T() U V(T'+1) U U V(T^) and Y = V(T{) U U(T') U U V{T[).
Then |Aj + |T| = n and there is no arc from X to Y. m
4.3 Separable matrices
Let M be an n x n (0, l)-matrix, and let B be a bipartite graph whos
reduced adjacency matrix is M, and D a digraph whos adjacency matrix is
M. Then one can quickly verify that M being inseparable is equivalent to B
being connected. Unfortunately, there is no direct connection between M being
inseparable and a connectedness property of D. However, in [29], Greenberg,
Lundgren and Maybee showed that there is a connection between M being
inseparable and connectedness in two more graphs other than B. The row graph
of M is the graph whose vertices correspond to the rows of M, with vertices
i and j adjacent if and only if there exists some k so that M, ^ = = 1.
Similarly, the column graph of M is the graph whose vertices correspond to the
columns of M, with vertices i and j adjacent if and only if there exists some k
so that Mk i = Mkj = 1. We now state their result.
Theorem 4.2 [29] Let M be an m x n matrix such that each column and row
of M has a non-zero element. Then the following are equivalent.
1) The bipartite graph whose reduced adjacency matrix is M is connected.
2) The row graph of M is connected.
3) The column graph of M is connected.
74


Note, when M is the adjacency matrix of a digraph D, then the row graph
and column graph are equivalent to the competition graph of D and Dr respec-
tively. Thus we can restate Theorem 4.2 as follows.
Theorem 4.2 (restated) Let D be a digraph with S+(D) > 1 and 5~(D) > 1.
Then the following are equivalent.
1) The adjacency matrix of D is inseparable.
2) comp(D) is connected.
3) comp(Dr) is connected.
We can use this theorem to determine exactly which tournaments are sep-
arable, as the competition graphs of tournaments have been classified. This
classification comes from the classification of the domination graphs of tourna-
ments and the correspondence between the competition graphs and domination
graphs of tournaments in Theorems 1.7 and 1.8 due to Merz, Fisher, Lundgren,
and Reid [44].
Let G be a graph which is not connected, and G\ and G2 two connected
components of G of order m and n respectively. Then, in the complement of
G, the graph induced on V(Gi) U I^(G2) contains the complete bipartite graph
Kmtn. In particular V(Gi) and V(G) V(Gi) forms a bipartition for a spanning
biclique of the complement of G. Recall from Theorem 1.8 that the domination
graph of a tournament is either a caterpillar or spiked odd cycle. The only
biclique which can be contained in a caterpillar or spiked odd cycle is a star,
KiiS. So, since the compliment of a disconnected graph contains a spanning
75


biclique, Theorems 4.2, 1.7 and 1.8 tell us that a tournament on n vertices with
no transmitter or receiver has a separable adjacency matrix, if and only if its
dual has a domination graph which contains the star Ah^-i.
Lemma 4.3 Let T be an n-tournament. Then dom(T) contains Ah _i as a
subgraph, if and only ifT has a transmitter, orT contains an arc (x,y) so that
0(y) = I(x) = V(T) {x,y}.
Proof: Suppose the star A'i>n_i is a subgraph of dom(T), and let y be
the center of Suppose there exist distinct u, v G V(T) such that u > y
and v > y, and without loss of generality, suppose u v. Then neither y
nor v dominate u, however [y,v] is an edge in dom(T), a contradiction. Thus,
d+(y) > n 2. If d+(y) = n 1, then y is a transmitter and we are done. So
assume d+(y) = n 2 and hence d~(y) = 1. Let x be the unique vertex in I(y).
Now choose u G V(T) {x, y}. Since I(y) = {x}, we have y > u. Also, since
[y, u\ is an edge in dom(T), and x y we must have u * x. Thus, there exists
an arc (x, y) in T with 0(y) = I(x) V(T) {x,y}. So these conditions are
necessary.
For sufficiency, first suppose T has a transmitter s. Pick a vertex v other
than s in V(T). If u V(T) {s,u} then s * u, so [s,u] G £'(dom(T)). Since
v was chosen arbitrarily, the star Ki n^i is a subgraph of dom(T) with center s.
Now, assume T contains and arc (x,y) so that 0(y) = I(x) V(T) {x, y}.
Choose w G V(T) {x,y}. If z G V(T) {x, y, w}, then y > z, and w > x. So,
[y,w] G E(dom(T)) for each w G V(T) {x,y}. Further, [x,y] G £'(dom(T))
since y z for all z G V(T) {x,y}. So dom(T) contains the star ATpn-i as a
76


subgraph with center y.
By Lemma 4.3 and Theorems 4.2 and 1.7, if T is a tournament with no
transmitter or receiver, Ts adjacency matrix is separable if and only if Tr con-
tains an axe (x,y) with 0(y) = I(x) V(T) {x,y}. Note however, if Tr
contains such an arc so will T. Also, if T has a transmitter or receiver its adja-
cency matrix has a row or column of zeros, and is separable. This gives us the
following theorem.
Theorem 4.4 Let T be a tournament. Then the adjacency matrix of T is sep-
arable if and only if at least one of the following occur.
1. T has a transmitter.
2. T has a receiver.
3. There exists an arc (x,y) in T such that 0(y) = I(x) = V(T) {x,y}.
4.4 Corollaries
In this section we give some corollaries due to our characterizations and
previous results about fully indecomposable matrices. Our first result involves
line covers of tournament matrices. A line cover of a matrix, M, is a set of
rows and columns of M which contain every non-zero entry of M. The following
theorem is taken from [14].
Theorem 4.5 A matrix M has a minimum line cover other than the all rows
or all columns cover if and only if M is partly decomposable.
77


The size of a minimum line cover is called the term rank of a matrix. In
Chapter 6 we will see that an n x n tournament matrix can only have real
rank, and hence term rank, n or n 1. In [22], Doherty, Lundgren and Siewert
show that the tournaments whose adjacency matrices have term rank n 1 are
exactly those with a strong component of order 1. The following corollary shows
that not only is the class of tournament matrices with term rank n 1 highly
restricted, the class of tournaments whose adjacency matrices admit a minimum
line cover other than the all rows or all columns cover is fairly restricted.
Corollary 4.6 Let T be a tournament and M its adjacency matrix. Then M
has a minimum line cover other than the all rows or all columns cover if and
only if T is not strongly connected, or T contains a vertex v such that T v has
a strong component of order 1.
Our remaining results are concerned with when a matrix has the property
that each of its inseparable components is fully indecomposable. Note, when a
matrix contains a row or column of zeros, one of the inseparable components
will be a submatrix of zeros and, hence, not fully indecomposable. So, in the
following theorem, we may assume that our tournaments have no transmitters
or receivers.
Theorem 4.7 Let T be a tournament with S+(T) > 1, S~(T) > 1, and adja-
cency matrix M. Then each inseparable component of M is fully indecomposable
if and only if
1. T is strongly connected, and
78


2. if T contains a vertex v such that T v has a strong component of order
1, then T contains an arc (x,y) with 0(y) = I(x) = V(T) {x,y} and
T {x, y} does not contain a strong component of order 1.
Proof: If T is not strongly connected, then by Theorem 4.1, M must be
partly decomposable. Further, in this case the only way M could be separable
is for T to have a transmitter or receiver, a contradiction to our assumption
that S+(T) > 1 and S~(T) > 1. Thus 1. is necessary, and we may assume T is
strongly connected. If M is fully indecomposable we are done, so assume M is
partly decomposable. By Theorem 4.1, M is partly decomposable if and only
if T contains a vertex v such that T v has a strong component of order 1.
Suppose M is separable. Since T has no transmitter or receiver, Theorem 4.4
says T must have an arc (x, y) such that 0(y) = /(x) = V(T) {x, y}. Now,
consider the submatrix of M obtained by deleting the row and column of M
corresponding to O(x) and I(y) respectively. This matrix has the form
A =
1 1
1 M'
where M' is an (n 2) x (n 2) tournament matrix and 1 denotes a vector of
all ones. Let T' be a tournament with adjacency matrix M'. Note, A is partly
decomposable if and only if there exist sets X, Y C V(T1) with no arc from X
to Y, and |X| + |T| = n 1. Now, \X U Y\ < |V(T,)| = n 2 and since T' is a
tournament, \X fl Y\ < 1. So,
n 1 = |X| + |T| = |X U Y\ + |X D Y| < n 2 + 1 = n 1.
Thus, \Xuy| = n 2 = |V(T,,)| and \XnT| = 1, which occurs exactly when T'
has a strong component of order 1. Further, since A contains a row and column
79


of all ones, A cannot be separable. Thus, each inseparable component of M is
fully indecomposable if and only if T is strongly connected and if T contains a
vertex v such that T v has a strong component of order one, then T contains
a arc (x, y) such that 0(y) = I(x) = V(T) {x,y} and T {x,y} does not
contain a strong component of order 1.
In our next two results we look at when tournaments are the digraphs of
doubly-stochastic and orthogonal matrices. A real non-negative n x n matrix is
called doubly-stochastic if every row sum and column sum is 1. The following
theorem is taken from [14].
Theorem 4.8 A (0,1)-matrix M is the pattern of a doubly-stochastic matrix if
and only if every inseparable component of M is a fully indecomposable matrix.
This theorem together with Theorem 4.7 give us the following corollary.
Corollary 4.9 A tournament T is the digraph of a doubly-stochastic matrix if
and only if,
1. T is strongly connected, and
2. if T contains a vertex v such that T v has a strong component of order
1, then T contains an arc (x,y) with 0(y) = I(x) = V(T) {x,y} and
T {x,y} does not contain a strong component of order 1.
The following theorem is taken from the linear algebra folklore. We prove
it here for completeness.
80


Theorem 4.10 If M is an orthogonal matrix, then each inseparable component
of M is a fully indecomposable matrix.
Proof: Let M be an n x n orthogonal matrix. Note if M is separable,
then M can be written in the form
/ Ai 0 0 0 \
0 A2 0 0
0 0 A3 0
\0 0 0 Ak j
where each Ai is inseparable. Block multiplication shows that if M is orthogonal
each Ai must also be orthogonal. So, we may assume M is inseparable. Now,
suppose to the contrary that M is partly decomposable. Say M can be written
in the form
M =
AO
BC
where O is a p x q matrix of Os with p + q = n. Then,
_ fJP\ (A0\ (AtBt\ f AAT ABT \
n~ \0 Iq) ~ \BC) l 0TCT J ~ l BAT (BBT + CCT)) '
So, AAT = Ip, and since A is a square matrix, A is invertible. Then since
ABr = O, ABj9 = 0 for alii = 1.q, a contradiction to A being invertible.
Thus, M cannot be partly decomposable and is hence fully indecomposable.
Again, using Theorem 4.7 we get the following corollary.
Corollary 4.11 If a tournament T is the digraph of an orthogonal matrix, then,
1. T is strongly connected, and
81


2. if T contains a vertex v such that T v has a strong component of order
1, then T contains an arc (x,y) with 0(y) = I(x) = V(T) {x, y} and
T {x,y} does not contain a strong component of order 1.
Note, unlike the previous two corollaries, this did not give us a character-
ization. This result only gives a necessary condition. Recall, as mentioned in
Chapter 3, aside from the 3-cycle, it is unknown if a tournament can be the
digraph of an orthogonal matrix.
Our final corollary is graph theoretic. A cycle factor of a digraph D is a
spanning subdigraph of D composed of vertex disjoint cycles. For example, the
bold arcs form a cycle factor of the digraph in Figure 4.3.
Figure 4.3: An example of a cycle factor in a digraph.
A non-zero diagonal of an nxn matrix M is a set of n non-zero elements of M
no two of which occur in the same row or column. If M is the adjacency matrix
of a digraph D, then the cycle factors of D are in direct correspondence with
non-zero diagonals of M. For example, the following matrix is the adjacency
82


matrix of the digraph in Figure 4.3. The bold ones in this matrix form a non-zero
diagonal and correspond to the bold arcs in the cycle factor in Figure 4.3.
/010 1 1 0\
001011
100101
010010
001001
\1 0 0 1 0 0/
The following theorem is taken from [14].
Theorem 4.12 Let M be an n x n (0,1 )-matrix. Then every 1 of M is on a
non-zero diagonal of M if and only if each inseparable component of M is fully
indecomposable.
This theorem together with Theorem 4.7, and the correspondence between
non-zero diagonals and cycle factors give us the following corollary.
Corollary 4.13 Let T be a tournament. Then every arc ofT is contained in a
cycle factor if and only if
1. T is strongly connected, and
2. if T contains a vertex v such that T v has a strong component of order
1, then T contains an arc x > y with 0(y) = I(x) = V(T) {x,y} and
T {a:, y} does not contain a strong component of order 1.
83


5. Domination Graphs of Complete Paired Comparison Digraphs
5.1 Definitions and background
In Chapter 4 we observed how a classification of the domination graphs
of tournaments gave us quite a bit of information about tournament matrices.
A generalized tournament matrix is a non-negative matrix M so that Mitj +
Mjj = 1 for all i ^ j, and Mhi = 0 for all i. In this chapter we characterize
the domination graphs of the digraphs associated with generalized tournament
matrices, which we call complete paired comparison digraphs. A complete paired
comparison digraph, D, is a complete symmetric directed graph so that for each
arc (x,y) we associate a real number between 0 and 1, denoted wxy, such that
wyx = 1 wxy. We also refer to a complete paired comparison digraph as a pcd,
rather than the awkward cpcd.
Like the round robin competition model for tournaments, we can think
of a pcd as a model in which each vertex competes with all others, where if
x,y G V(D), wxy denotes the probability that x will beat y. Based on this we
define a concept of domination in pcds. If D is a pcd, and x,y,z £ V(D) we
say that x and y dominate z if wxz + wyz > 1. This is analogous to a dominant
pair in a tournament, when we ask the question as to which pairs of vertices
{x, y} dominate D. We say that vertices x and y form a dominant pair in a
complete paired comparison digraph D if for all z V(D) {x,y} we have
wxz + wyz > 1. A tournament can be considered a pcd with arc weights 0 or 1.
84


So, a dominant pair in a tournament is also a dominant pair in the tournament
when it is treated as a pcd.
If D is a pcd, then we define the domination graph of D, denoted dom(D),
on the same vertices of D with [x, y] an edge of dom(.D) if and only if {x, y}
is a dominant pair. By studying the domination graphs of pcds, we can get a
feel for who a dominant competitor may be in the model. In [51] Moon and
Pullman also attempt to rank competitors in this model using the eigenvalues
of generalized tournaments.
Surprisingly, there is a distinction between domination graphs of pcds in
which some competitors are equally matched (i.e., the arcs between them have
weight .5) and domination graphs of pcds having no equally matched competi-
tors. We characterize domination graphs of pcds in which wxy ^ .5 for all
x,y £ D. We also characterize domination graphs of pcds in which the domina-
tion graphs are connected graphs, and in which the domination graphs have no
isolated vertices.
5.2 Preliminary results
In this section we give some preliminary results that will be used throughout
the chapter. A key to this study is the following lemma.
Lemma 5.1 Let D be a complete paired comparison digraph. For any 2 vertex
disjoint edges in dom(D), say [r, s] and [it, u], we have that in D
Wus ^ sv WVf
Proof: Since {r, s} and {it, u} are dominant pairs in D, we know that
wvr + wur > 1, wTV + wsv > 1, wsu + wru > 1, and wvs + wus > 1. Also, by
85


the definition of a pcd, wru + wur 1, wus + wsu = 1, wsv + wvs = 1, and
Wyr + wrv = 1. Thus,
Wru 1 Wur ^ Wvr 1 Wry ^ WSy 1 Wvs and so
Wru Wus Wsv Wvr.
Recall Un is the rotational tournament on the vertices {0,1,2 ..., n 1}
with i j if and only if j i is odd modulo n. In [44], Merz et. al. show that
Un is the unique tournament which has an n-cycle as its domination graph. We
now prove a similar result for an analogous pcd. Choose 0 < p < 1. We define
the pcd f7iP on vertex set {1,2,..., n} by Wij = p if and only if j i is odd
modulo n, and wlj = 1 p otherwise.
Lemma 5.2 Ifnis odd, and Cn is an induced subgraph of the domination graph
of some complete paired comparison digraph D, then the vertices which induce
the cycle in dom(D) induce UUtP in D, for some p, 0 < p < 1.
Proof: We assume V(Cn) = {1,2,..., n} and E(Cn) = {[?, i + 1] : 1 < i <
n 1} U {[n, 1]}. Suppose that n > 5. Consider the arc (l,j), 2 < j < n 2.
Assume that j 1 is odd. Let ivy = p. Apply Lemma 5.1 to edges [n, 1] and
[iii + 1] to see that w\j = Wjn wn^+1) W(j+i)i = p Apply Lemma 5.1 to
edges [1, 2] and \j + 1 ,j + 2] to see that ?%+2)i = ^i(j+i) = 1 *%+i)i = 1 ~P-
Thus, W\(j+2) = P, and uq^+i) = 1 p. This implies that all arc weights w\j are
p when j 1 is odd and 1 p when j 1 is even, 2 < j < n. By an identical
86


argument with i in place of 1, if Wij = q for j i odd, then all arc weights wtj are
q when j is odd and 1 q when j i is even. Thus, p = wi2 = 1 w2\ = 1 q.
So, p + q = 1. Consequently, in D, = p if and only if j i is odd modulo n,
and = 1 p otherwise. Thus, V(Cn) induces UntP in D.
To complete the proof, suppose that n = 3. Then, since {1,3}, {1,2} and
{2,3} form dominant pairs, W\2 + w22 > 1, uq3 + w2$ > 1, and w2i + w2i > 1.
This means that iui2 + (l w22) > 1,1023 + (1 ^31) > 1, and t03i + ( 1 1012) > 1.
Thus,
W\2 > W22 > W31 > W\2.
So, the result follows.
Lemma 5.3 Let D be a complete paired comparison digraph with at least 4
vertices. Then, dom(D) = Kn if and only if wxy = .5 for all distinct x,y E
V(D).
Proof: Suppose dom(Zl) = Kn, and pick distinct x,y e V(D). As n > 4,
there are vertex disjoint edges [x,x'\ and [y,y'\ in dom(D). By Lemma 5.1,
wxy = wyx1 wxiyi = Wy'x. Now, apply Lemma 5.1 to edges [x,y'] and [x'y]
to see that wyx = wxx> = wx>y> = wy>y. Therefore, wxy wx>y> = wyx. But
wyx = 1 wxy, so wxy = Wyx = .5, as desired. The converse is immediate.
Note, it was shown in Lemma 5.2 that if D is a pcd with 3 vertices x, y, z so
that wxy = wyz = wzx > .5, then dom(D) = K2. So, sufficiency of Lemma 5.3
requires our pcd have 4 or more vertices.
Theorem 5.4 Let D be a complete paired comparison digraph, and S C V(D).
87


Let D' be the pcd induced on S, then the subgraph of dom(D) induced on S is a
subgraph of dom(D').
Proof: Let {x, y} be a dominant pair in D, with x,y G S. Then, for all
v G V(D) {x, y}, wxv + wyv > 1. In particular, this is true of all v G S. Thus,
{x,y} form a dominant pair in D'. This proves our result.
If D is a pcd, v G V(D), and S C V(D), then we define the set 0§(v) by
Og iv) = {a: G S : wvx > .5}.
If S = V(D), then Oy^(v) will be abbreviated as 0+(v).
Lemma 5.5 Let D be a complete paired comparison digraph, v G V{D), and
S C V(D). Then, Og(v) forms an independent set in dom(D).
Proof: Let x,y £ Og(v). Then, wxv < .5, and wyv < .5, so wxv + wyv < 1.
That is, {x, y} does not form a dominant pair.
Lemma 5.6 Let D be a pcd. There exists a pcd D' on the same vertices as D
such that dom(D') =dom(D), wxy < 1 for all x,y G V(D'), and wxy is greater
than, less than, or equal to .5 in D' if and only if it is greater than, less than,
or equal to .5 in D respectively.
Proof: If wxy < 1 for all x, y G V(D), we are done. So, assume wxy = 1
for some x, y G V(D). Let k = min{|n;ulJ .5| : u,v G V(D),wuv ^ .5}, and
set e = |. For simplicity, for the rest of this proof we will let w'xy denote the
weight of arc (x, y) in D' and wxy the weight of arc (x, y) in D. We construct
D' by setting V(D') = V(D), and for distinct u, v G V(D') assigning weights
88


to (u,v) as follows. If wuv = .5, set w'uv = .5. If wuv > .5, set w'uv = wuv e,
and if wuv < .5, set w'uv wuv + e. So, wxy < 1 for all x,y E V(D'), and w'xy
is less than, greater than, or equal to .5 if and only if wxy is. We now show
dom(Z)') =dom(D).
Pick [x,y] E E(dom(D)). So, for all 2 E V(D), wxz + wyz > 1. Choose
z E V(D). If wxz wyz .5, then w'xz + wyz = .5 + .5 = 1. If exactly one
of wxy and wyz is .5, then the other must be strictly greater than .5 or else
wxz + wyz < .5 + .5 = 1. So, w'xz + w'yz = wxz + wyz e. By our choice of e,
e < wxz + wyz 1, so wxz + wyz >1. So, assume wxz and wyz are not .5. By a
similar argument, at least one of wxz and wyz must be strictly greater than .5.
So,
{Wxz + e + wyz e, if wxz > .5,wyz < .5,
wxz-e + wyz + e, if wxz < .5, wyz > .5,
wxz + e + wyz + e, if wxz > .5, wyz > .5.
In all three cases, wxz + wyz > 1 since wxz + wyz > 1. Thus, [x,y\ E E(dom(D'))
Now choose distinct x,y E V(D') so that [x,y] & E(dom(D)). So, for some
z E V(D), wxz + wyz < 1. So either wxz < .5 or wyz < .5, or else wxz + wyz > 1.
So,

+ <
yz
( wxz + wyz + e, if wxz = .5, wyz < .5,
wxz + e + wyz, if wxz < .5, wyz = .5,
wxz + + wyz e, if wxz > .5, wyz < .5,
wxz e + wyz + e, if wxz < .5, wyz > .5,
k wxz e + wyz , if wxz < .5, wyz < .5.
In the first two cases, our choice of epsilon gives e < 1 (wxz + wyz), and
so wxz + wyz + e < 1. In the last three cases, we have wxz + wyz < 1, since
wxz + wyz < 1, and so \x,y\ $ E(dom(D)). Thus dom(D) dom(D').
The next proposition indicates why a characterization of domination graphs
of pcds is difficult. Consider the situation for tournaments. There are strict
89


requirements on a graph G so that there exist a tournament T for which dom(T)
contains G as an induced subgraph. This is not so in the context of pcds since
any graph will do as seen in the next proposition.
Proposition 5.7 Let G be a graph, then there exists a complete paired compar-
ison digraph D for which dom(D) contains G as an induced subgraph.
Proof: Let G be a graph on n vertices, and construct a pcd D in the
following way. Start with V(D) = V(G). For each x,y e V(G), let wxy = .5.
Now, for each pair {i,j} of nonadjacent distinct vertices in G, add a vertex Vij
(same as Vji) to V(D), and set wViji = wVijj = 1. Also, for each z V(G) with
[*, z] 6 E(G) or [j, z] e E(G), set wZVi. = 1. Set all other weights to .5. We now
show the construction gives the desired result.
Consider two vertices i,yG V(G). Suppose that [x,y\ 6 E{G). If [x,y\ £
dom(.D), then there is a z G V(D) so that wxz + wyz < 1. Because arc weights
are 0, .5, or 1, this implies that at least one of wxz or wyz is 0. Suppose wxz = 0;
then by construction z = vxk for some vertex k. But, since [x,y] 6 E(G), the
construction yields wyz = 1. So, wxz + wyz 1, a contradiction. Hence [x,y] is
in dom(D).
On the other hand, if [x,y] $ E(G), then using z = vxy we see that wxz +
Wyz = 0 + 0 = 0 so that {x, y} is not a dominating pair in D. That is, [x, y) ^
^(dom(D)). So, G is an induced subgraph of dom(D).
5.3 Complete paired comparison digraphs with no arc weight .5
As Proposition 5.7 shows, characterizing the domination graphs of pcds is
not an easy task. However, the problems seem to arise from equally matched
90