
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00005831/00001
Material Information
 Title:
 Arctraceable tournaments
 Creator:
 Busch, Arthur H
 Publication Date:
 2005
 Language:
 English
 Physical Description:
 viii, 85 leaves : ; 28 cm
Subjects
 Subjects / Keywords:
 Tournaments (Graph theory) ( lcsh )
Hamiltonian graph theory ( lcsh ) Directed graphs ( lcsh ) Directed graphs ( fast ) Hamiltonian graph theory ( fast ) Tournaments (Graph theory) ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Bibliography:
 Includes bibliographical references (leaves 8285).
 Statement of Responsibility:
 by Arthur H. Busch.
Record Information
 Source Institution:
 University of Florida
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 62866048 ( OCLC )
ocm62866048
 Classification:
 LD1193.L622 2005d B87 ( lcc )

Downloads 
This item has the following downloads:

Full Text 
ARCTRACEABLE TOURNAMENTS
by
Arthur H. Busch
Bachelor of Arts, University of Washington, 1997
A thesis submitted to the
University of Colorado at Denver
in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Applied Mathematics
2005
This thesis for the Doctor of Philosophy
degree by
Arthur H. Busch
has been approved
K.B. Reid
Ellen Gethner
21 April X)OS
Date
Busch, Arthur H. (Ph.D., Applied Mathematics)
Arctraceable Tournaments
Thesis directed by Professor Michael S. Jacobson
ABSTRACT
A tournament T is arctraceable when each arc of the tournament is a part
of a hamiltonian path. We characterize arctraceable upset tournaments and
show that this property is independent of the number of hamiltonian paths in
such tournaments. We show that nonarctraceable tournaments have a specific
structure, and give several sufficient conditions for strong tournaments to be arc
traceable, including Diraclike minimum degree conditions, Orelike conditions,
and irregularity conditions. In each case, we show that the result is best possible.
Next, we give some extremal results for arctraceable tournaments, bounding the
number of arcs in a tournament that are not part of any hamiltonian path, and
finding the minimum number of vertices in a fcarcstrong tournament that is
not arctraceable. Finally, we also consider the arctraceable property in two
other classes of digraphs, semicomplete digraphs and local tournaments, both
of which share many properties with tournaments.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication. /)
Signedl
IV
DEDICATION
I would like to dedicate this dissertation to my parents. Their encouragement
and support has been unwavering, and their patience almost unlimited.
ACKNOWLEDGMENT
First and foremost, I would like to thank my advisor, Mike Jacobson. I would
like to think that my frequent interruptions of his work were usually a welcome
distraction, but they were certainly a distraction. I am grateful for the time he
has spent with me on this thesis and on other projects that have collectively
made me a much better mathematician. In addition, I want to thank both Rich
Lundgren and to Bill Cherowitzo, who encouraged and mentored me early in my
graduate studies and knew long before I did that my education would culminate
in a Ph.D. Bill, in particular, deserves credit for trying his best to turn me into
a geometer. Ultimately unsuccessful, I learned a great deal in the process.
CONTENTS
Figures .............................................................. viii
1. Introduction and background ........................................ 1
1.1 Prologue............................................................ 1
1.2 Background.......................................................... 3
2. Paths and cycles in tournaments.................................... 14
2.1 Cycles in tournaments.............................................. 14
2.2 Paths in tournaments............................................... 17
3. Upset tournaments.................................................. 21
3.1 Arctraceable upset tournaments ................................... 23
3.2 Counting Hamiltonian Paths in Upset Tournaments.................... 28
4. Arctraceability in all strong tournaments......................... 39
4.1 Observations on arctraceability in tournaments.................... 39
4.2 The structure of nonarctraceable tournaments..................... 45
4.3 Applications of the structure results.............................. 51
4.4 Extremal results related to arctraceable tournaments.............. 55
5. Related problems................................................... 67
5.1 Semicomplete digraphs.............................................. 67
5.2 Round digraphs..................................................... 71
5.3 Locally semicomplete digraphs...................................... 77
5.4 Other Generalizations ............................................. 80
References.............................................................. 82
vii
FIGURES
Figure
1.1 A digraph and two subdigraphs, one induced............................ 4
1.2 A hamiltonian digraph................................................. 6
1.3 A tournament with eight vertices...................................... 9
1.4 A simplified representation of a tournament.......................... 13
2.1 A strong tournament that is not arcpancyclic........................ 16
2.2 The two families of arc3cyclic tournaments that are not arcpancyclic. 16
2.3 A hamiltonian digraph that is not arctraceable...................... 18
3.1 An 11tournament with 10 nontraceable arcs.......................... 26
3.2 Two 8tournaments.................................................... 34
4.1 An arctraceable tournament.......................................... 47
4.2 A tournament with nontraceable arc xy and two arcdisjoint paths from
y to x.............................................................. 60
5.1 Two nonarctraceable strong semicomplete digraphs................... 70
5.2 A round local tournament with cycles of length two................... 72
5.3 A strong nonarctraceable round digraph............................. 76
1. Introduction and background
1.1 Prologue
Questions relating to paths and cycles in graphs and digraphs have been
studied extensively from a variety of perspectives. One of the most popular
questions in undirected graphs relates to determining the class of graphs that
contain a hamiltonian path or cycle. This basic question has been generalized
and specialized in many ways which has led to a number of deep and interesting
results (for a survey of such results, see [15]).
Our particular interest is a property of digraphs we call arctraceable; an
arctraceable digraph is one in which every arc is part of a path that includes
every vertex, i.e., a hamiltonian path. This question seems more difficult than
the related question for undirected graphs, studied by Balihska, Zwierzyhski,
Gargano and Quintas ([2], [3] and [4]). As a result, we investigate arctraceability
in the subclass of digraphs known as tournaments. Tournaments have additional
structure that, in many cases, can be shown to guarantee arctraceability. We use
this additional structure to investigate tournaments that are not arctraceable.
In the next section, we provide some brief background material with an
emphasis on terminology and classical results related to digraphs and tourna
ments. In Chapter 2, we review some more recent results specifically relating
to paths and cycles in digraphs and tournaments, and we develop a necessary
condition for a digraph to be arctraceable. This necessary condition is used to
show that the study of arctraceable tournaments can be restricted to studying
arctraceable strong tournaments.
1
Initially, we consider the question in the context of a subclass of strong
tournaments known as upset tournaments, and in Chapter 3, we give a charac
terization of arctraceable upset tournaments. We use this characterization to
produce examples of tournaments that have many arcs that are not part of any
hamiltonian path (such arcs will be called nontraceable). We also develop some
techniques to demonstrate that arctraceability is independent of the number of
hamiltonian paths in upset tournaments. In other words, arctraceability in a
tournament is not merely a consequence of having many hamiltonian paths.
In Chapter 4, we broaden the investigation of arctraceability to all strong
tournaments. We begin with some simple observations about sufficient condi
tions for a strong tournament to be arctraceable. From these basic observa
tions, we then develop some necessary conditions for a strong tournament to be
nonarctraceable. These conditions, in turn, yield many new and improved suf
ficient conditions for arctraceable tournaments, and a structure that we use to
construct minimal nonarctraceable tournaments with many arcdisjoint paths
between every pair of vertices. We also use the structure of nonarctraceable
tournaments to determine the maximal number of nontraceable arcs in a strong
ntournament.
In Chapter 5, we briefly consider arctraceability for digraphs in general. We
investigate arctraceability in two classes of digraphs that include tournametns,
semicomplete digraphs and local tournaments. We also briefly consider some
questions closely related to arctraceability in tournaments and these super
classes of tournaments. The structure developed in Chapter 4 features promi
nently in these questions, and we give examples that show how related structures
2
occur in these contexts. These related questions suggest several directions for
future research.
1.2 Background
We begin with some of the fundamental results related to directed graphs
in general and tournaments in particular. We assume the reader is familiar with
the study of undirected graphs and suggest [10] as both a general resource and
for more detailed background on the following results for digraphs and [33] as a
resource for more information on tournaments.
A digraph D = (V, A) consists of a set V called vertices and a collection A
of ordered pairs of elements from V called arcs. Just as in the case of undirected
graphs the order of D is the number of vertices in V and the size of a digraph is
the number of arcs in A. Typically, the study of digraphs is restricted to those
digraphs in which vv Â£ A for every v Â£ V and there is at most one copy of each
of the remaining ordered pairs. Such a digraph is called strict, and when D is a
strict digraph, the collection of arcs is more commonly referred to as a set. Strict
digraphs are in a sense analogous to simple undirected graphs; graphs with no
loops and at most one edge joining each pair of vertices. Unless specifically
stated otherwise, we will assume that all digraphs are strict. For convenience,
we often simply write uv to represent the arc (u,v), and we will say that u
dominates v and write u v when (u,v) is an arc of D A subdigraph of a
digraph D = (U, A) is a digraph D' = (S, T) where both S QV and T C A. For
a set S C V, we define the induced subdigraph D[S] as the digraph with vertex
set S and arc set T = {(u,v) \ (u,v) Â£ A and u,v Â£ S'}. In other words, the
arcs of an induced subdigraph include all arcs that join two vertices in S. In
3
i
a b c
g
a b c
Figure 1.1: A digraph and two subdigraphs, one induced.
Figure 1.1, we show an example of a strict digraph along with two subdigraphs.
The subdigraph on the right is induced, while the subdigraph on the left is not;
it includes the vertices c and d but not the arc from c to d.
The outneighborhood of a vertex v is the set {u \ vu G A} and is denoted
N+(v) or N+(v) when the context is clear. Similarly, N (v) = {u \ uv G
A}. The outdegree (d+(u)) and indegree (d~(v)) are defined as A+(u) and
/V_(u), respectively. Similar to graphs, we then let h+ (
degree (indegree) and A+ (A) be the largest outdegree (indegree) among all
the vertices of D. Additionally, we set 5 = min(h+, h~) and A0 = max(A+, A).
When we are working with more than one digraph, we will use the notation
8(D), for example, to clarify the digraph to which we are referring.
A path in a digraph is a sequence of distinct vertices viv2 ... Vk such that
Viii+i G A for each i, 1 < i < k. If, in addition, v^Vi e A, then the sequence is a
!
4
cycle. The order of a path or cycle is the number of vertices in the sequence, and
the length is the number of arcs. Thus, a path of length l has order l 1, while
a cycle of length l also has order l. Note, just as for graphs, any consecutive
subsequence of the vertices of a path or cycle is also a path. Conversely, we
will frequently want to combine two or more paths into larger paths. If P =
V1V2 .. Vk and Q = U1U2 Um are vertex disjoint paths, and VkU\ Â£ A, then
we will denote the combined path v\... VkUi... um simply as PQ. A digraph D
which contains no cycles is called acyclic.
Of particular interest is a path or cycle containing all the vertices of D, i.e.
a hamiltonian path or cycle. Just as for graphs, a digraph containing a hamil
tonian cycle will be called hamiltonian and a digraph containing a hamiltonian
path will be called traceable (of course, every hamiltonian digraph is traceable
but not conversely). Figure 1.2 shows a digraph that is hamiltonian, with a
hamiltonian cycle highlighted by dashed arcs.
For undirected graphs, hamiltonian paths and cycles have been studied ex
tensively. Two classic, early results are due to Dirac and Ore.
Theorem A (Dirac [11]). If G is a simple graph with at least three vertices
and 5(G) > ^ then G is hamiltonian.
Theorem B (Ore [30]). Let G be a simple graph. If d(u) + d(v) > n for every
pair of distinct nonadjacent vertices u and v, then G is hamiltonian.
We note that for strict digraphs, an analogue of Theorem A was given by
GhouilaHouri.
Theorem C (GhoilaHouri [13]). If D is a strict digraph with 5 > then
D is hamiltonian.
5
Figure 1.2: A hamiltonian digraph
Similarly, Theorem B has been generalized to strict digraphs by Woodall
[43]. Meyniel improved both of these results with the following:
Theorem D (Meyniel [26]). If D is a strongly connected strict digraph and
d+(u) + d~(u) + d+(v) + d~{y) > 2n 1 for every pair of vertices u and v such
that neither uv A(D) nor vu Â£ A(D), then D is hamiltonian.
A digraph is strongly connected or simply strong when for every pair of
distinct vertices u and v there exists both a path from u to v and a path from v
to u. Note, a single vertex digraph is always strong. As such, for any digraph D,
each vertex is contained in a strongly connected induced subdigraph of D. When
such a strong induced subdigraph is maximal, it is called a strong component of
D, and it is easy to see that these strong components must, in fact, partition
V. We then define a new digraph D*, called the condensation of D by letting
V(D*) be the set of strong components of D and A{D*) = {DiDj  uv Â£ A for
some u E Di,v E Dj with i ^ j}. Again, it is easy to see that D* is an acyclic
digraph. For more information about the condensation of a digraph, see [36].
6
In a strong digraph D, if the induced subdigraph D[S] is not strongly con
nected for some S C V, then V \ S is called a cutset of D. When D[S] is
strong for all sets S with Sj > \V\ (d 1), we say that D is dconnected and
we define k(D) to be the smallest d such that D is dconnected. Analogously,
if D' = (V, T) is not strongly connected for some T C A, then A \ T is called
an arc cutset, and we define k'(D) as the smallest k such that D' = (V,T)
is not strong for some T C A with \T\ = A k. We then we say that D is
karcconnected or karcstrong whenever k < k'(D). The digraph in Figure 1.2
is 2arcstrong; both the solid arcs and the dashed arcs form hamiltonian cycles,
so removing any single arc still leaves a path between any two vertices. Note,
this digraph is not 2connected, however, since removing the vertex x leaves no
path from u to v.
When two distinct nonadjacent vertices x and y are specified, an x,y
separatingset is a set S of vertices such that every path from x to y contains
at least one vertex of S. Similarly, an x, yseparatingset of arcs is a set T of
arcs such that every path from x to y contains at least one arc of T (in this
case, we need not require that x and y be nonadjacent). In both cases, it is
easy to see that when there exist m paths from x to y that are internally vertex
disjoint (arcdisjoint) then the set S (T) must contain at least one vertex (arc)
from each path. The converse also holds in both cases, a result referred to as
Mengers Theorem. Mengers Theorem is stated in a wide variety of ways, both
for graphs and digraphs. We give two variations here.
Theorem E (Menger [25]). Let D be a digraph and let x and y be distinct
nonadjacent vertices of D. The number of internally vertex disjoint paths from
7
x to y equals the size of the smallest x,yseparating set. Similarly, for any
distinct (possibly adjacent) vertices x and y, the number of arcdisjoint paths
from x to y equals the size of the smallest x, yseparating set of arcs.
Our main focus will be on a special class of digraphs called tournaments.
A tournament is a directed graph D such that for any two distinct vertices u
and v, either uv Â£ A(D) or vu Â£ A(D) but not both. Typically, a tourna
ment is denoted by T rather than D, and we will say T is an ntournament
when IV(T)! = n. It is often helpful to think of an ntournament as an orien
tation of the complete graph Kn. From this perspective, it is immediate that
a tournament has no selfloops or cycles of length two. It is also clear that
A(T) \E(Kn) \ = Q) and that N~(v) and N+(v) partition the set V(jT)\{u}
regardless of our choice of v. This also shows that d+(v) + d~(v) = n 1 for
every vertex v. In accordance with the name tournament, we will often refer
to d+(v) as the score of the vertex v. We illustrate an 8tournament in Figure
1.3. Clearly, drawing even relatively small tournaments is impractical due to
the large number of arcs.
It is also apparent, by considering the tournament as an orientation of a
complete graph, that any induced subdigraph of an ntournament is also a tour
nament. We simply refer to such an induced subdigraph as a subtournament,
and for the set U C V(T) we denote the subtournament on the set U by T[U}.
When U = V(T)\S for some subset S, we simply write T S instead of TjV\Â£].
If S = {u}, then we will abbreviate notation further and refer to T {?;} as Tv.
For any two subsets A and B of V(T), there are exactly A5 arcs between
these two sets. When uv is an arc of T for every u Â£ A and v Â£ B, we will
8
Figure 1.3: A tournament with eight vertices.
say A dominates B. Note, just as the tournament as a whole can be viewed as
an orientation of the complete graph, the arcs between the sets A and B can
be viewed as an orientation of the complete bipartite graph K\a\,\b\ When A
dominates B then this orientation is such that the arcs between A and B always
originate in A and terminate in B.
In addition to the traditional measures of in and outdegrees in a tourna
ment such as 5+,<5_ and 5, we also measure the irregularity of a tournament,
denoted i(T) and defined as maxey d+(v) d~(v). From this definition, we
see that i(T) 0 if and only if every vertex has equal in and outdegree and
all of these values must then be exactly (and hence, n must be odd). Such
a tournament is called regular. When n is even, i(T) > 1 and in the case of
equality, the vertices have outdegree either  or  1. Such tournaments are
called nearregular or almostregular.
Proposition 1.1. i(T) = n 1 25
Proof. If d+(v) d~(v)\ > n 1 25 for some v V, then we must have either
9
d+{v) d (u) > n 1 28 or d (v) d+(v) > n 1 25. Substituting in
d (v) < 8 or d+(v) < 8, a contradiction. Thus, i(T) < n 1 28. To
complete the proof, note that
max d+(u) d~(v) \ > max(A+ 8~, 5+ A)
vV
For any tournament T = (V, A), we can order the vertices vi,v2, ,vn in
such a way that d+(vi) < d+(vj) for every i < j. If we let d+(vi) = sl for
1 < i < n, this ordering gives a nondecreasing sequence S = Si, s^, S3,..., sn
of length n. This sequence is called the score sequence of the tournament T. It
is clear that Si = A = (") since each arc is counted exactly once in the
sequence. Also, the subset 14 = {ui, u2,..., Vk} induces a subtournament for
each k < n, so we also must have 5^i=i si ^ A(T[I4]) = (Â£) for each k < n.
Landau [23] showed that these necessary conditions are also sufficient. Thus,
any nondecreasing sequence S = si, S2,..., sn such that
d+(v) ( d (v) for n 1 into both equations and simplifying, we obtain either
> max ^(n 1 8~) 8~, 8+ (n 1 5+) j
> max(n 1 28~, n 1 28+)
> n 1 2 min(Â£, 8+)
>n 1 25.
10
and
is the score sequence for some tournament T.
A tournament is transitive if A{T) induces a transitive (and hence acyclic)
relation on the set V(T). Furthermore, since A(T) is antisymmetric and every
pair of vertices is joined by an arc, every pair of vertices is comparable under this
transitive relation and thus gives a total ordering of the set V(T). If V(T) =
{vi,..., vn}, with the subscripts corresponding to this order, then ViVj Â£ A(T) if
and only if i > j and hence d+(v= i 1 (or, of course, v{Vj Â£ A(T) if and only
if i < j, in which case d~(vi) = i 1; we generally prefer the former ordering).
It is well known (c.f. [36]) that a tournament is transitive if and only if it is
acyclic.
Note, if a tournament T is strongly connected, the condensation digraph T*
consists of a single vertex, which is trivially transitive. If T is not strongly con
nected, then because T is an orientation of the complete graph, the underlying
graph of T* is also complete, and so T* is also a tournament. Furthermore, T*
is by definition acyclic, and hence T* is a transitive tournament.
If T = (V,A), for any B C A, we can form a new tournament V by
reversing the arcs of B. More specifically, let B {uv \ vu Â£ B}, then
T' = (V, (A \ B) U B). Two special cases are of particular interest. First, when
B = A, we will call T' the reversal of T and denote this tournament T. Note,
paths and cycles in T are also paths and cycles in T. The second special case
is when the T' obtained is a transitive tournament, and in this case we can use
the transitive ordering of V(T') on V(T) as well. Using this ordering, in which
11
V{Vj is an arc of T' whenever i > j, B is precisely the set or arcs ViVj in T such
that i < j and the arcs of B are sometimes referred to as the upset arcs of the
tournament. Using this idea, we develop a simplified way to draw a tournament.
We place the vertices in a linear order, and make the arc from u to v implicit
if u comes after v in this ordering. In other words, we only draw the arcs of B.
Figure 1.4 uses this technique to represent the same tournament shown in Figure
1.3. In all subsequent figures, we will use this technique to drawn tournaments
as well as similar digraphs. In some cases, we may also draw a small number
of the nonupset arcs when these arcs are of particular interest (to highlight
nontraceable arcs, for example). Note, each ordering of V(T) determines a set
of upset arcs B and if we choose the ordering badly, the set B can be large,
which minimizes the advantage of drawing only the upset arcs. We will avoid
such orderings. Further simplifying our figures, we will use a similar technique
for the condensation of tournaments that are not strong; we will represent the
nontrivial components of the tournament with large circles or ellipses, often
without specifying the internal structure of these strong components. Further
more, using a toptobottom or lefttoright ordering of these components, we
need not draw in any arcs at all as the condensation is a transitive tournament.
Finally, we will sometimes wish to illustrate most of the arcs of a tournament,
but leave the direction of one or more arcs unspecified. We will indicate such
unspecified arcs with a dashed line.
When V(T) has some ordering such that the set B = {viVj \ i < j} is
the arc set of a path U from v\ to rn, T is called an upset tournament and
the path U is called the upset path of T. Since reversing the arcs of any path
12
Figure 1.4: A simplified representation of a tournament
leaves the degrees of the interior vertices unchanged, d^(v{) = d^,(vi) = i 1
for each i,2 < i < n 1. Similarly, dj.(vi) = d^,(vi) + 1 = 0 + 1 = 1 and
dx(vn) = d^,(vn) 1 = n 1 1 = n 2. Thus, an upset tournament has
score sequence 1,1, 2,..., n 3,n 2, n 2. Brualdi and Li [9] showed the
converse of this result is also true; that any tournament with this sore sequence
is an upset tournament. The tournament in Figures 1.3 and 1.4 is an example
of an upset tournament. These two figures also show the advantage of using our
simplified representation in the case of upset tournaments; it is easy to see that
the tournament in Figure 1.4 is an upset tournament, but this is far from clear
by looking at the same tournament in Figure 1.3 with all the arcs drawn.
Upset tournaments form a very natural subclass of tournaments, because
they are very nearly hereditary. While it is not true that every subtournament
of an upset tournament is itself an upset tournament, it turns out that every
nontrivial strong component of such a subtournament is an upset tournament.
In particular, every strong subtournament of an upset tournament is an upset
tournament.
13
2. Paths and cycles in tournaments
The study of hamiltonian paths and cycles in tournaments began with the
very early result of Redei.
Theorem F (Redei [32]). Every tournament is traceable.
Similarly, strong tournaments were shown to be hamiltonian independently
by Foulks and by Harary and Moser (this is also implied by Theorem D).
Theorem G (Foulkes [12] and Harary and Moser [18]). Every strong
tournament is hamiltonian.
As a result, the investigation of hamiltonian paths and cycles in tournaments
focuses on stronger conditions than the existence of at least one hamiltonian path
or cycle. We survey a few of these stronger conditions, beginning with results
for cycles in tournaments, and then turning our attention to paths.
2.1 Cycles in tournaments
One of the first results generalizing hamiltonicity in tournaments is due to
Moon. He showed that every strongly connected tournament has a property he
called vertexpancyclic.
Theorem H (Moon [29]). IfT is a strong tournament, and v is any vertex
ofT, then v is in a cycle of length k for 3 < k < n.
We note that a similar property does not hold for the arcs of a strong tourna
ment. Consider the tournament with six vertices shown in Figure 2.1. Reversing
14
the arc a from the bottom vertex to the top vertex gives a tournament T' with
two strong components, each of order three. Any cycle of this tournament that
does not use the arc a is also a cycle of T' and hence has order at most three.
Since no cycle can contain both a and either of the other upset arcs shown, these
upset arcs can not be on any cycle of length four or more.
A natural question arises; what conditions on a tournament guarantee that
every arc is on a cycle of all possible lengths? We will call tournaments in
which every arc is contained in a cycle of length exactly k arckcyclic, and if a
tournament is arcAcyclic for each possible A, (in other words, for 3 < k < n),
then the tournament is called arcpancyclic. In the special case where k = n,
we will say a tournament is archamiltonian rather than arcncyclic. Alspach
[1] initially showed that every regular tournament is arcpancyclic. Jakobsen
[21] studied nearregular tournaments and found that while not necessarily arc
pancyclic, for n > 8, such tournaments are arcAcyclic for each A, 4 < k <
n. In 1980, Thomassen [38] showed that every 3connected tournament is arc
pancyclic and that there are infinitely many 2connected tournaments that are
not archamiltonian (and hence, not arcpancyclic). Thomassen was also able
to give a sufficient condition for almost arcpancyclic tournaments based on
irregularity.
Theorem I. Thomassen [38] IfT is an ntournament with i(T) < then T
is k arccyclic for 4 < k < n
As regular and nearregular tournament have irregularity zero and one, re
spectively, this result implies (along with the simple observation that for regular
tournaments, each arc is in a cycle of length three) the results of both Alspach
15
Figure 2.1: A strong tournament that is not arcpancyclic
Figure 2.2: The two families of arc3cyclic tournaments that are not arc
pancyclic.
and Jakobsen.
For k = 3, Moon [27] was able to show that nearly all tournaments are
arc3cyclic. This last result was then used by Tian, Wu and Zhang to aid in
characterizing arcpancyclic tournaments. They showed the following:
Theorem J (Tian, Wu and Zhang [41]). An arc3cyclic tournament is
arcpancyclic unless it belongs to one of the families D$ or Dg shown in Figure
2.2.
Prom this result, one can deduce the above results of Thomassen, and hence
also of Jakobsen and Alspach.
16
2.2 Paths in tournaments
Properties related to similar generalizations of traceability in tournaments
are not as well studied. The work of Redei [32] showed that not only does every
tournament have a hamiltonian path, but that every tournament has an odd
number of such paths. Further, it is a simple exercise (cf. [36]) to demonstrate
that a tournament has a unique hamiltonian path if and only if it is acyclic
(or equivalently, is transitive). The number of distinct hamiltonian paths in
a tournament has been studied, and it has been shown by Moon [28] that for
strong tournaments, the number of such paths grows exponentially with n. For
nonstrong tournaments, the number of distinct hamiltonian paths is simply the
product of the number of hamiltonian paths in each strong component.
The question of which arcs in a digraph can be extended to a hamiltonian
path was first suggested by Balihska, Gargano and Quintas [2] in a paper analyz
ing the analogous concept in undirected graphs. We use the term arctraceable to
describe digraphs with this property. In this undirected context, it was shown
that every hamiltonian graph is edgetraceable (called totallytraceable in [2],
[3] and [4]). Since hamiltonian graphs are extensively studied, this gives a
great deal of information about edgetraceable graphs. In the directed case,
examples abound which show that hamiltonicity is not sufficient to guarantee
arctraceability. One such example is shown in Figure 2.3.
The lack of a well known sufficient condition for a digraph to be arctraceable
would seem to make the problem significantly more difficult than in the undi
rected case. Apart from some very special cases mentioned in [2], we note the
following necessary condition.
17
Figure 2.3: A hamiltonian digraph that is not arctraceable.
Theorem 2.1. If D is an arctraceable digraph, then D*, the condensation of
D is a path.
Proof Let D be an arctraceable digraph. Assume D has m strong components
and let D* be the condensation of D. If D is traceable, D* must also be traceable.
So, it suffices to show that when D is arctraceable, then D* is an oriented tree,
as the only traceable oriented tree is a path. We establish this by showing that
the underlying graph of D* is acyclic.
Since D* is acyclic, it contains some vertex of indegree 0. Label such a
vertex v\. Now D* {u*} is also acyclic, and so this subgraph also has at least
one vertex of indegree 0. Choose such a vertex and label it v^. Proceeding
inductively, we can label all the vertices of D* as v\, v%,..., v*m such that vp has
indegree 0 in D* {ui,... ,up_i}. Thus, for any p > q, v*v* A(D*). This
well known ordering is known as a topological sorting by Golumbic [14] and an
acyclic ordering by BangJensen and Gutin [6]. We use this same ordering for
the strong components of D: D\,..., Dm so that v* corresponds to component
A.
Now, assume that C is a cycle of the underlying graph of D*. Choose the
18
smallest index i such that v* is on C, and let v* and be the neighbors of v*
on this cycle. By the minimality of i we have i < j and i < k, and without loss
of generality we can assume that j < k. Since v*v%. E E(C), the acyclic ordering
requires that we must have v*vl E A(D*). This in turn requires that there are
distinct vertices x and y in Di and Dk respectively such that xy E A(D). Now
choose any vertex 2 in Dj.
Since D is arctraceable, xy is on some hamiltonian path of D, and 2 must
precede x or follow y on such a path, and so there must be either a path in
D from 2 to x or a path in D from y to 2. But clearly, any such path must
contain an arc uv where u E Dp and v E Dq with p > q. This requires that
x*x* E A(D*), a contradiction. Hence, the underlying graph of D* must be
acyclic.
Unfortunately, this necessary condition gives no information about strong
digraphs, as the condensation of such a digraph is an isolated vertex, which is
trivially a path.
Recently, Reid [34] began to study arctraceable tournaments. Attempting
to find conditions that are necessary and sufficient for a tournament to be arc
traceable and several related questions is the primary focus of this dissertation.
The necessary condition given above, along with the observation made ear
lier that the condensation of a tournament is a transitive tournament implies
the following corollary.
Corollary 2.2. If a tournament T is arctraceable, then T has at most two
strong components.
19
As noted above, our necessary condition for digraphs gives no information
about which strong tournaments are arctraceable. However, we can use the
hamiltonicity of strong tournaments to observe that the analysis of arctraceable
tournaments reduces to the study of arctraceable strong tournaments.
Corollary 2.3. A tournament T with two strong components is arctraceable
if and only if the subtournaments induced by the strong components are arc
traceable.
Proof. Let T\ and T2 be the subtournaments induced by the strong components
of T, and let every vertex of Xi dominate each vertex in T2. Now, every hamil
tonian path of T must be of the form PiP2, with Pi a hamiltonian path of X for
i 1,2. So, if Ti is not arctraceable for i = 1 or i = 2, then there is some arc
that is not part of any hamiltonian path of T.
Conversely, if both Ti and T2 are arctraceable, then each arc within these
subtournaments is also traceable in T. To conclude that T is arctraceable, we
must show that the remaining arcs are also traceable. Each of these arcs is of
the form xy with x E V{T\) and y E C(T2). We use the hamiltonicity of each
of these subtournaments to construct a hamiltonian path P\ of T\ that ends at
x and a hamiltonian path P2 of T2 that begins at y. Consequently, PiP2 is a
hamiltonian path of T containing xy, completing the proof.
Thus, if we are able to obtain even partial results in the case of strong
tournaments, these results will have simple extensions to all tournaments.
20
3. Upset tournaments
We begin by studying the class of upset tournaments. As noted in Chapter 1,
these are precisely the set of tournaments obtained from transitive tournaments
by reversing the arcs of any single path from the source (i.e., vertex of indegree
zero) to the sink (i.e. vertex of outdegree zero). This reversed path is referred
to as the upset path. Reversing the arcs of a path leaves the scores of the vertices
on the interior of the path unchanged, and the initial and terminal vertices of the
path have their scores decreased and increased by one respectively. If we begin
with a transitive ntournament, this yields a tournament with score sequence
(1,1, 2, 3,..., n 3, n 2, n 2).
We note that an identical argument indicates that reversing any path from
a vertex of outdegree one to a vertex of indegree one in an upset tournament T
yields a transitive tournament. This would seem to indicate that the upset path
of an upset tournament may not be unique. To see that the upset path is never
unique, let u and u' be the vertices of an upset tournament with outdegree
one and let v and v' be vertices with indegree one. Without loss of generality,
assume that u dominates u' and v dominates v'. Thus, any path that originates
at u must begin with the arc uu', and any path that terminates at v' must end
with the arc vv'. So, if U is an upset path of the tournament that originates
at u, then U u is a path from u' to a vertex of indegree one and this shorter
path is also an upset path. Similarly, if U terminates at v', then U v' is an
upset path that terminates at v. On the other hand, if U is an upset path that
21
originates at u', then u cannot be a vertex of U since u is not the terminal vertex
of U and the only vertex that can follow u on a path is u'. In this case, uU is
also an upset path of the tournament, and dually if U is an upset path ending
at v, then Uv' is also an upset path.
To address the above ambiguity we can require that our upset path U contain
the arcs uu' and vv' or, alternately, we can forbid the inclusion of these arcs.
The former approach is used in [31] and [24], among others. In general, we prefer
the latter approach; we require that U be as short as possible. However, if there
is a hamiltonian path from a vertex of outdegree one to a vertex of indegree
one, it is often convenient to choose this hamiltonian path as U.
We present a result of Brualdi and Li [9] showing that upset tournaments are
characterized by their score sequence. Their proof uses the adjacency matrices
of upset tournaments. To illustrate the powerful inductive nature of this class
of tournaments, we present an alternate proof.
Theorem 3.1 (Brualdi and Li [9]). Let n > 4. An ntournament T is an
upset tournament if and only if the score sequence of T is (1,1, 2,3,..., n
3, n 2, n 2).
Proof. Necessity follows by the argument above; that the reversal of the arcs of
a path of the transitive tournament from source to sink leaves the scores of the
vertices on the interior of the path unchanged, decreases the score of the source
by 1 and increases the score of the sink by 1. This produces a tournament with
the desired score sequence.
For sufficiency, we use induction. For n = 4, the tournament with score
sequence (1,1,2,2) is unique and it is easily seen that this is an upset tourna
22
ment. For n > 4, let T be a ntournament with the given score sequence, let u
and v be the vertices of T with score 1, and assume that uv Â£ A. Consider the
tournament T' = T u. Clearly, the score of every vertex x in T' is one less than
the score of x in T, apart from u, whose score is unchanged. Thus, the score
sequence of the (n l)tournament T' is (1,1, 2, 3,..., n 4, n 3, n 3). By
the induction hypothesis, T' is an upset tournament. Let U be an upset path
of T'. The first vertex of U has outdegree 1 in V. If v is on the path I/, then
we consider the subpath U' that begins at v and ends at the terminal vertex of
U. Reversing this path in either T' or T leaves a transitive tournament, and
hence U' is an upset path of both T' and T. If v is not on the path U, then the
only neighbor of the initial vertex of U is clearly the second vertex of this path.
Hence, v dominates the initial vertex of U. As a result, we can form the path
U' = vU, and just as before, this path JJ' is an upset path of both T' and T.
3.1 Arctraceable upset tournaments
We now address the question of arctraceability in upset tournaments. Ini
tially, we characterize which arcs of an upset tournament lie on a hamiltonian
path.
Theorem 3.2. Let T denote an upset tournament on n > 6 vertices with upset
path U. If V is labeled V = {zq,... ,vn}, so that ViVj Â£ A if and only if either
i < j or v^j is an arc of U, then the arc vrvs of T is nontraceable if and only
if all of the following hold:
Both vr E V(U) and vs V(U).
vrvs is not an arc of the upset path.
23
For each vertex Vk 6 V(U) with r < k < s, neither Vki nor Vk+1 are
vertices of the upset path.
Proof. Let vrvs be an arc of T that is on no hamiltonian path. First, we show
that both vr and vs are vertices of the upset path. This follows from the ob
servation that T Vi is an upset tournament for any Vi not on the upset path.
Since upset tournaments are strong, this tournament has a hamiltonian cycle
and consequently, a hamiltonian path beginning or ending at any specified ver
tex. So if vr is not on the upset path, we can choose a hamiltonian path H
of T vr that begins at the vertex vs. Now, vrH is a hamiltonian path of T
containing the arc vrvs, a contradiction. Similarly, if vs is not on the upset path,
we choose H, a hamiltonian path of T vs that ends at the vertex vr and Hvs
is a hamiltonian path containing vrvs. As no such path exists, vs Â£ V(U).
Next, we show that vrvs is not an arc of the upset path. This follows
from the observation that T V(U) is a transitive tournament whose source is
dominated by V\ in T. If H is the unique hamiltonian path of T V(U), UH
is a hamiltonian path of T containing the arc vrvs. As no such path exists, vrvs
can not be an arc of the upset path. Thus, r < s and for at least one k such
that r < k < s, Vk V{U).
Now, we show that for each vertex Vk G V(U) where r < k < s, neither
nor Vk+\ is on the upset path. Suppose that for some such k, Vk~i is on
the upset path, so VkVki is an arc of U. Then, both T\ = T[{vi,..., Wfc_i}]
and T2 = T[{vk,..., vn}\ are upset tournaments and hence strong. We can then
choose a hamiltonian path H\ of T\ that ends at vr and a hamiltonian path H2
of T2 that begins at the vertex vs. But then H\H2 is then a hamiltonian path of
24
T containing vrvs, a contradiction. Similarly, if vk+i is on the upset path then
by the same argument with T\ T[{vi,... wfc}] and Ti = T[{vk+i, ,n}],
vrvs is on a hamiltonian path. So, neither vki nor vk+i are on the upset path.
For the converse, suppose that vrvs is an arc of T, where both vr Â£ V(U)
and vs Â£ V(U), vrvs is not an arc of the upset path, and that for each vk on the
upset path U between vr and vs, neither vki nor vk+i are on the upset path.
Let Q be a longest path of T that contains the arc vrvs, and let U[vs, vr] be the
subpath of U beginning at vs and ending at vT.
First, note that Q can not contain U[v3,vr] as a subpath, since vs follows
vr on this path but vr follows vs on Q. So we can choose an upset arc vqvp of
U[vs,vr] that is not part of the path Q. Note, by assumption p + 1 ^ q, and
every path from vp+\ to vr must contain the arc vqvp. Since Q does not contain
this arc, vp+\ does not precede ty on Q. Similarly, every path from vs to vp+i
must include the arc vqvp, and hence vp+\ does not follow vs on Q. But vr and
vs are consecutive on Q, and so vp+i is not on the path Q. Thus, Q is not a
hamiltonian path, and since the length of Q is maximal, no hamiltonian path
containing vrvs exists.
The above result completely characterizes arctraceable upset tournaments
with six or more vertices.
Corollary 3.3. An upset tournament T on n > 6 vertices is arctraceable if
and only if for every vertex vk on the interior of the upset path, either vki or
vk+i is also on the upset path.
Proof. If T is a tournament satisfying the given condition, then Theorem 3.2
25
Figure 3.1: An 11tournament with 10 nontraceable arcs
implies that there is no arc that is nontraceable, i.e. T is arctraceable. For
the converse, assume there is some Vk on the upset path with neither Vk~\ nor
Ufc+i on the upset path. Let vt and v3 be the vertices immediately preceding and
succeeding vk on U, respectively. Then, by Theorem 3.2 VjV% is on no hamiltonian
path.
The above results fail for n 5 vertices, as the upset tournament obtained
from reversing the unique hamiltonian path of the transitive tournament on
five vertices is not arctraceable, despite satisfying the conditions of Corollary
3.3. This is a consequence of the fact that this tournament is isomorphic to the
upset tournament with an upset path of length with middle vertex of score 2,
and this tournament does not meet the criteria indicated in the corollary. In
fact, there are only two nonisomorphic upset tournaments on five vertices. The
other is obtained by reversing the single arc from source to sink in a transitive
tournament, and this tournament is easily seen to be arctraceable.
Next, we describe an upset tournament with many nontraceable arcs, and
prove that this example is maximal.
Theorem 3.4. IfT is an upset tournament with n > 5 vertices, n odd, and the
upset path ofT is vnvn2Vn~4 v$V\, then exactly n2~^n+3 = \ Q) 3^i8~1'1 arcs
of T are not on a hamiltonian path.
26
Proof. By Theorem 3.2, the arcs of T on no hamiltonian path are of the form
^i+(2fc+2) for i dd, 1 < i < n 4 and 1 < k < _ i. Thus, for a fixed
i = 2j +1, there are exactly ~ 1 = 1 = '< j nontraceable arcs
starting at vertex Vi. Summing all possible values of j, we obtain
n 5
Â£(
3=0
n
 4n + 3
nontraceable arcs in T.
Figure 3.1 shows a tournament of order 11 with the structure described
above. We now show that this family of examples has the maximal number of
nontraceable arcs among all upset ntournaments.
Theorem 3.5. An upset ntournament T, n > 5, has at most
n2 4n + 3 1 /n\ 3(n 1)
8 4 V2) 8
nontraceable arcs.
Proof. We prove the result by induction on n. For n = 5, it is easy to verify
that any upset tournament on five vertices not having the structure indicated in
Theorem 3.4 is arctraceable, and that the upset tournament with this structure
has 5~g5+" = 1 arc that is not on any hamiltonian path.
Next, assume the result for upset tournaments with fewer than n > 5 ver
tices. Let i be the vertex that immediately precedes the vertex Vi on the upset
path. As observed earlier, T\ = T[vi,..., vn] is an upset tournament, and so by
the induction hypothesis, there are at most
(n i + l)2 4(n i + 1) + 3 n2 4n + 3 ^ 2n 4 (i 1)
_ = Â§ V ~ ) Â§
27
nontraceable arcs in T\. By applying Theorem 3.2 twice, once for necessity
in T\ and again for sufficiency in T, we note that each of these arcs is also
nontraceable in T.
All that remains is to count the nontraceable arcs of T that are not arcs
of T\. Clearly, no arc incident with the vertices u2,... ,Vi1 is nontraceable
so any nontraceable arc of T that is not an arc of T\ is incident with v\.
Additionally, if i 2, then by Theorem 3.2, every arc incident with v\ is also
on a hamiltonian path. In this case, the Theorem follows by observing that
(i l) 2n~4~b~1) = 2r^5 > o as n > 5. So, we may assume that i > 3. In this
case, as n > 5 it follows that
(n i + l)2 4(n i + 1) + 3 ^ (n 2)2 4(n 2) + 3 n2 8n + 15
8 8 8 '
Thus, we must show that at most 4n^12 = arcs incident with v\ are
nontraceable. Let j be the largest index such that the arc v\Vj is nontraceable.
As a consequence of Theorem 3.2, at most of the vertices iq, Vj are on
the upset path of T and V{ is one of these vertices. Since ViV\ is part of the
upset path, and thus is part of a hamiltonian path, this implies that at most
l < arcg incident with the vertex v\ are not a part of any hamiltonian
path, and the result follows.
3.2 Counting Hamiltonian Paths in Upset Tournaments
To conclude this section, we consider the connection between arctraceability
and the number of distinct hamiltonian paths in upset tournaments. We note
a result by Moon [28] that gives a lower bound for the number of hamiltonian
paths in strong tournaments.
28
Theorem K (Moon [28]). An strong tournament on n vertices has at least
6*1 (,639)(1.565n) distinct hamiltonian paths.
It is natural to expect that, in general, arctraceable upset tournaments have
more hamiltonian paths than nonarctraceable upset tournaments. However,
we shall now show that this is not always the case.
We observe again that for any vertex v in an upset tournament T, T v
is also an upset tournament if v is not the interior of some upset path. If v
is on the interior of some upset path, then it is a cut vertex and the first and
last strong components of T v are upset tournaments with the remaining
strong components all trivial (consisting of single vertices). Combined with the
observation that the number of hamiltonian paths in a tournament T is the
product of the number of hamiltonian paths of the strong components of T,
this suggests that we can find the number of hamiltonian paths of an upset
tournament recursively.
In particular, we next consider two simple techniques that will show that
it suffices to count the number of hamiltonian paths of any upset tournament
in which no three consecutive vertices lie on the upset path. Let px denote the
number of distinct hamiltonian paths of the tournament T.
Theorem 3.6. IfT is an upset ntournament and Vj is a vertex on the upset
path such that neither Vj_\ nor Vj+\ are on the upset path, then then px =
PT[vi,Vj]PT[vj,vn]
Proof. Let H be the set of hamiltonian paths of T, and let TCi and 7d2 be the sets
of hamiltonian paths of T[vi,..., vf\ and T[vj,..., u], respectively. We show a
bijection between PL and 7i\ x 7d2
29
Let H be a hamiltonian path of T. We define the sequence of vertices
Si by deleting each vertex of H with index greater than j. We claim that
S\ is a hamiltonian path of T[vi,... ,Vj]. Assume otherwise and let vs and vt
be consecutive in Si with vs /> vt. Since S is a path, vs and vt can not be
consecutive on H, and so there must exist a vertex vr between vs and vt on H
with r > j. But since T is an upset tournament every path from vr to vt must
include the vertex Vj, and since Vj was not deleted from Si, we conclude that
t j and so s < t. Since vsvt is not an arc of T, vtvs must be an upset arc.
Since vs precedes vt on H, this arc is not part of H. It follows that this arc is
included on every path from Vji to vs in T as well as on every path from vt to
Vj1. Thus, we conclude that Vj_\ does not precede vs or succeed vt on H. Since
H is a hamiltonian path, this vertex must lie between vs and vt on this path,
contradicting the fact that these vertices are consecutive in Si. Consequently, Si
must be a hamiltonian path of T[vi,..., Vj}. Similarly, the sequence S2 obtained
by deleting the vertices of H with index less than j is a hamiltonian path of
T[vj,...,vn].
On the other hand, let P\VjQi and P^VjQ^ be hamiltonian paths of T[v 1,..., Vj]
and T[vj,..., vn\, respectively. Then H = P1P2VQ1Q2 is a hamiltonian path of
T.
Our next result is a similar result that applies to tournaments in which two
consecutive vertices may be on the upset path.
Theorem 3.7. Let T be an upset tournament, and let vi+\vl be an arc of the
upset path of T, where vi+2 and Vi\ are not vertices of the upset path. Then
30
the number of hamiltonian paths of T is 2ab cd where a is b is
c is pt[vi+2,...,vn] and d
Proof. The proof is similar to the proof of Theorem 3.6. Begin with P\ViQ\
and P2Vi+iQ2, hamiltonian paths of T[v\,... ,V{] and T[vi+i,...,vn], respec
tively. Now, define two sequences of vertices Hi = PiP2^i+\ViQiQ2 and
H2 = P\ViQiP2Vi+\Q2 Clearly, Hi is a hamiltonian path and H2 is as well
provided that either Qi ^ 0 or P2 ^ 0. Now if Qi 0, then Pi must be a
hamiltonian path of T[v 1,..., Uj_i] and if P2 = 0 then Q2 is a hamiltonian path
of T[vi+2,..., un]. Thus the number of distinct hamiltonian paths of T is at least
ab + (ab cd) = 2ab cd where a, b, c and d are defined as in the Theorem.
For the reverse inequality, let H be a hamiltonian path of T. First, assume
that Vi+iVi is an arc of H. Then let H = Pvi+iViQ and let Pi and Qi be
the vertices of P and Q, respectively, with index less than i. We claim that
P\V%Qi is hamiltonian path of T[v 1,... ,vf\. Assume otherwise. Then, there are
consecutive vertices vs and vt in the sequence PiViQi such that vt dominates vs.
This requires that vi+i must succeed vs and precede vt on H, and thus t = i.
Since n* dominates only one vertex in T[v 1,... ,vt], this vertex must be vs, and
since r/;_i is not on the upset path s < i 1. As above, the arc vtvs is on every
path from vt to t>i_i as well as every path from to vs. Since this arc is not
included in H, 1 must precede vt and succeed vs. This contradicts our choice
of vs and vt as consecutive vertices of Piv^Qi, so this sequence of vertices forms
a hamiltonian path of T[v 1,... ,fj]. Similarly, P2Vi+iQ2 is a hamiltonian path
of T[vi+i,..., vn] where P2 = P \ Pi and Q2 = Q\Qi Thus, there are at most
ab hamiltonian paths of T that contain the arc vi+iVi.
31
Now, assume that vi+\Vi is not an arc of H. Then H is also a hamiltonian
path of the tournament T' obtained by reversing this arc. T' has two strong
components, T\vi,..., vf\ and T\vl+1,..., un] and so any hamiltonian path of T'
must have the form PQ where P is a hamiltonian path of T[v\,..., vf\ and Q is
a hamiltonian path of T[vi+1,..., vn]. So H has this form and since H is also a
hamiltonian path of T, we cannot have both P ending at vx and Q beginning at
vi+\. Clearly, there are ab ways of choosing an arbitrary P and Q, and there are
cd ways of choosing such that both P ends at vx and Q begins at vx+i. Thus,
there are at most ab cd hamiltonian paths of T that do not contain the arc
Vi+iVi.
Next, we count the hamiltonian paths of an upset tournament with an upset
path of length one. This, combined with the previous two results, permits a
recursive technique that can be used to determine the number of hamiltonian
paths of any upset tournament in which no three consecutive vertices are on the
upset path.
Theorem 3.8. The upset tournament on n vertices with a single upset arc has
2"~2 + 1 hamiltonian paths.
Proof. Let T be an upset ntournament with the single upset arc vnv\.
First, we consider hamiltonian paths that do not use the upset arc. Each
such path is also a hamiltonian path of the transitive tournament obtained by
reversing this upset arc. Since the transitive tournament has a unique hamilto
nian path, we conclude that there is a unique hamiltonian path of T not using
the arc vnv\.
32
Now, we consider hamiltonian paths using the upset arc of T. Let S\ be the
set of vertices preceding vn on such a hamiltonian path. We note that Si is a
subset of S = {u2,f3,... Conversely, let Si be any subset of S and let
S2 = S \ Si. Since T[Si] and T[S2] are both transitive tournaments, and vn is
dominated by Si and v\ dominates S2, there is a unique hamiltonian path of T
containing the arc vnv\ where Si is the set of vertices preceding vn. Thus, there
is a bijection between subsets of S and hamiltonian paths of T containing the arc
vnv\ and consequently, it follows that there are exactly 2^ = 2n_2 hamiltonian
paths containing the arc vnv\ and 2~2 + 1 hamiltonian paths in total.
Corollary 3.9. If T is an upset tournament on n vertices with an upset path
of length 2, then T has at least 2n~3 + 2^ + 1 hamiltonian paths, with equality
if and only if n is odd and the upset path is vnvnivx.
Proof. Let Vj be the middle vertex of the upset path. Then by Theorem 3.6,
Pt = PT[v1,...,vj]Pr[vj,...,vn} Furthermore, by Theorem 3.8 pT[v 1,...,^] = 2J_2 + 1
and PT[vj,...,vn] = 2n~j~1 + 1. Thus pT = 2"3 + 2j~2 + 2n~j~l + 1. The proof is
complete by noting that the function f(x) = 2X~2+2n~l~x has a global minimum
at x =
We note, as a consequence of this corollary, the number of hamiltonian paths
in upset ntournaments with upset paths of length two grows exponentially with
n at a faster rate than the lower bound given by Theorem K. Specifically,
 2n < px < \ 2 for n > 5. Additionally, we note that for n > 5, upset
tournaments with upset paths of length two are necessarily nonarctraceable
by Corollary 3.3.
33
i
Figure 3.2: Two 8tournaments
We can now use the above results to show that the first 8tournament shown
in Figure 3.2 has precisely 2(5) (5) 1 = 49 hamiltonian paths and by Corollary
3.3 is arctraceable. Similarly, the second 8tournament shown in Figure 3.2 is
nonarctraceable and yet has 3(17) = 51 hamiltonian paths.
The above results also permit us to count the number of hamiltonian paths of
every upset tournament on seven or fewer vertices, with one exception. The only
exception is the upset tournament on seven vertices with upset path vjv^v^vi,
which is isomorphic to the upset tournament with upset path vjv^v^v^vi. For
this case, we will show that this tournament has 31 distinct hamiltonian paths.
Table 3.1 lists all upset tournaments of order three through seven, the number of
distinct hamiltonian paths, and whether the tournament is arctraceable or not
according to Corollary 3.3. From the data, we conclude that the tournaments in
Figure 3.2 are minimal with respect to the number of vertices. In other words,
if T is an arctraceable upset ntournament with k hamiltonian paths, and V
is a nonarctraceable upset ntournament with k! > k hamiltonian paths, then
n > 8.
We now consider the family of upset ntournaments with upset paths of
length n. 1. In other words, the tournaments obtained by reversing the arcs in
34
Table 3.1: All upset tournaments of order three through seven.
the unique hamiltonian path of a transitive ntournament. We show that the the
number of hamiltonian paths of such an ntournament satisfies the tribonacci
recurrence for n > 3 and use this recurrence to obtain asymptotic results for
the number of hamiltonian paths in such tournaments. For convenience, in
the remainder of this chapter we will use the notation T; to refer to the upset
tournament with ivertices with an upset path of length i 1. We will then
denote the number of hamiltonian paths of 7] as p*.
In the following proof, we require some new notation. We will say that a
path P is vdeletable when v is on the path P, and either v is the initial vertex
of P or the vertex immediately preceding v dominates the vertex immediately
following v. Conversely, v can be inserted into P if v is not on P and there
are consecutive vertices x and y on P such that x > v and v > y. If the
35
terminal vertex of P dominates v, then we will say that v can be appended onto
P. Dually, if the initial vertex of P is dominated by v, then we will say that v
can be prepended onto P.
Theorem 3.10. pn = pn1 + Pn2 +Pn3 for n > 3.
Proof. Let Si be the set of hamiltonian paths of Tj. We establish the result by
showing a bijection between Sn and Sni U Sn_2 U Sn_3.
Initially, we partition the set Sn into two parts; S^i, the hamiltonian paths
ending at vn and Sn,2, those ending at any vertex other than vn. We further
subdivide each Sny, let Un>\ be the set of all hamiltonian paths of SH:i that are
vni deletable and let Un^ be the set of all hamiltonian paths of Sn^ that are
vn deletable. Finally, let Wn^ = Sn^ \ Un^ for i = {1, 2}.
We now construct the desired bijection in three parts. First, we note that
there is a bijection between Â£/n,2 and
Un<2, we obtain a hamiltonian path of Tn_ 1 and since N+(vn) = vn can
be inserted into or prepended onto a hamiltonian path of Tn_ 1 in a unique way.
Since no path of Un^ ends at vn, vn is interior on every path of {/i2 and thus
two hamiltonian paths of Un,2 are distinct if and only if they can be obtained in
this way from distinct hamiltonian paths of Tn_ 1.
Next, we observe a bijection between Un
and wn_i from a hamiltonian path of C/n>i, we obtain a hamiltonian path of
Tn2, and as in the previous case, vn\ can be inserted into the interior of each
hamiltonian path of Tn_2 in a unique way. Furthermore, we can append vn to
the end of each of these paths, thus obtaining hamiltonian paths of [/nj. Just
as above, two paths of Un% 1 are distinct if and only if they can be obtained in
36
We first
i
this way from distinct paths of Tn_2.
The last part of our bijection is between Wn2 and Sn3.
show that each path P of Wnj must end with the subpath vn^vnivn2vn.
Since a path P of Wn^ does not end at un_1; and N+(vn_i) = {w_2}, P must
include the arc u_iun_2. Furthermore, because P is not vn\ deletable, the
vertex immediately preceding vni must be dominated by un_2, and so must be
a vertex in A^+(u_2) = {u_3,un}. As P ends at vn by definition, this vertex
must be un_3 and the vertex immediately following un_2 must be vn. the terminal
vertex of P.
Similarly, we show that each path P of Wi2 must end with the subpath
vn2VnVni Since P does not end at vn and N+(vn) = {u_i}, it contains the
arc vnvn\ and since P is not vn deletable, the vertex immediately preceding
vn on P must be in the set N+(vn1) = {un_2}. Further, since this is the only
vertex dominated by un_i, un_i must be the terminal vertex of P. Thus, for
any path of Wnj U VFn>2 the first n 3 vertices form a hamiltonian path of T_3.
Conversely, any hamiltonian path H of Tn_3 can be extended to a hamiltonian
path of Tn by appending the path un_iun_2un if H ends at u_3, or appending
the path un_2uu_i if H does not end at un_3.
Next, we note that pi = p2 = 1 and Â£>3 = 3, and this defines the sequence
A000213 in the database maintained by Sloane [37] (offset by one). Note that
by Corollary 3.3, Ti is not arctraceable for all i > 6. Also, Â£>7 = 31, completing
our table of the number of distinct hamiltonian paths for all upset tournaments
with between three and seven vertices.
i
37
The tribonacci recurrence shares many similarities with the better known
Fibonacci recurrence. In particular, just as the ratio of Fibonacci numbers
approaches the positive real root of x2 x 1, the ratio of consecutive numbers
in a sequence satisfying the tribonacci recurrence approaches the positive (and
only) real root of x3 x2 x 1 [22].
Corollary 3.11. The number of hamiltonian paths of an upset ntournament
with upset path of length n 1 approaches an as n approaches infinity, where a
is the real root of x3 x2 x 1 (approximately 1.8329/
Thus, it is clear that the tournaments in Figure 3.2 are not isolated examples;
in fact, there exist infinitely many such examples. For n > 15, the nonarc
traceable upset tournament T with upset path vnv^ni^vi has more distinct
hamiltonian paths than the arctraceable upset tournament T' with upset path
vnvn_i... v\, and pt Pt> grows exponentially with n.
38
4. Arctraceability in all strong tournaments
In this chapter we turn our attention to arctraceability in all strong tour
naments. We require very different techniques than were used for upset tourna
ments, and we will fall just short of a characterization of arctraceable strong
tournaments. However, we will develop a specific structure that is shared by all
nonarctraceable strong tournaments, and we will use this structure to obtain
many sufficient conditions for strong tournaments to be arctraceable and to
yield some extremal results for nonarctraceable tournaments.
4.1 Observations on arctraceability in tournaments
We recall that in a hamiltonian digraph D, then for any v Â£ V{D), D has
a hamiltonian path that begins at v and also a hamiltonian path that ends at
v. Since every strong tournament is hamiltonian, we observe that nontraceable
arcs of a tournament must join two cut vertices.
Proposition 4.1. IfT is a strong tournament and v is not a cutvertex ofT,
then every arc incident with v is on a hamiltonian path.
This gives us our first sufficient condition for arctraceable tournaments; if
T has no cut vertices, then T has no nontraceable arcs.
Corollary 4.2. IfT is 2connected, then T is arctraceable.
This first sufficient condition was observed in the more general setting of
multipartite tournaments by Volkmann in [42]. Our second sufficient condition
39
requires the following result, using a technique similar to the proof of Theorem
H by Moon in [29].
Lemma 4.3. Let xy be an arc in a strong tournament T. If P is a longest path
from y to x in T, then P can be extended to a hamiltonian cycle.
Proof. Let P be a longest path from y to x and let C be the longest cycle that
contains P. Assume that C is not hamiltonian. Thus, there is some vertex v
that is not on C. If y dominates v, then v must dominate each vertex of P.
Otherwise, let u be the first vertex along P such that vu 6 A(T) and let w be
the vertex immediately preceding u on P. Now, y ... wvu ... x is path from y
to x longer than P. Thus, v dominates x and by a similar argument using the
maximality of C, v must also dominate the subpath of C from x to y. In other
words, v dominates all of the vertices of C. But since T is strong, there must
be a path from every vertex of C to v. Let Q be the shortest of these paths and
note that this minimality requires that the only vertex of Q on C is the initial
vertex vq. Let v~ and be the immediate predecessor and successor to vq on
C, respectively, If the arc vqv+ is an arc of P, then y... vfQv+ ... x is a path
from y to x longer than P. Otherwise, the cycle C' obtained by replacing the
arc vqv+ with the path Qvq is a cycle containing P that is longer than C. In
either case, we have obtained a contradiction.
We now can show:
Theorem 4.4. Let T be a strong ntournament, and let xy 6 A(T) be on some
cycle of length l > Then xy is on a hamiltonian path ofT.
40
Proof. Let C = yu\ UkX be the longest cycle containing the arc xy. Extend
C xy to H, a hamiltonian cycle of T. Let H = yu\ Ukxwm w\. So
n = k + m + 2, and since C has length k + 2 > k > m.
If Wi dominates Ui for some i, choose the minimal such i. If i = 1
then define the path P = wm w\U\ Ukxy, otherwise define the path
P = wm WiUi Ukxyu\ UiiWii wi. In either case, P is a hamil
tonian path of T containing xy. So we may assume that Ui dominates Wi
for every i, 1 < i < m. In particular, we may assume that G A(T).
If k = m, then let P = xyu\ UkWm w\, and if k > m, set P =
um+1 Ukxyui umwrn w\. In either case, P is a hamiltonian path of T
containing the arc xy.
From this we infer a second sufficient condition for a strong tournament to
be arctraceable.
Corollary 4.5. IfT is a strong tournament and every arc ofT is on some cycle
of length l > then T is arctraceable.
We now consider again our observation above that every 2connected tour
nament is arctraceable. If a tournament is twoconnected (and hence arc
traceable), then Theorem E states that for any two vertices x and y such that
y /> x, there must be at least two internally vertex disjoint paths from y to x.
Of course, in a tournament y x implies that x > y. So we can restate our
observation above as follows.
Proposition 4.6. If T is a tournament with the property that there exist at
least two internally vertex disjoint path from y to x for every arc xy, then T is
41
arctraceable.
We show this property applies locally as well. Any arc xy where the smallest
y, x separating set has size at least 2 is traceable. We use Theorem E and state
the result in terms of internally vertex disjoint paths.
Theorem 4.7. Let T be a strong tournament, and let xy G A(T) be such that
there exist at least two internally vertex disjoint paths from y to x in T. Then
there exists a hamiltonian path ofT which includes the arc xy.
Proof. Let P and Q be two internally vertex disjoint paths from y to x such
that for any internally vertex disjoint paths P', Q' from y to x, \V(P)UV(Q)\ >
V(P') U V(Q')\. Let P = yu0 umx and Q = yw0w\ WkX, and let U
{uo, ,m} and W = {tuo, ,Wk} If V(P) U V(Q) = V(T), then H =
Uo umxyw\ Wk is a hamiltonian path of T containing xy. So assume V(P) U
V(Q) C V(T) and let S be the tournament induced on the vertices of V(T) \
(V(P) U V(Q)). If V(S) dominates U U W, then for any hamiltonian path Hs
of S, H = HsUq umxywo Wk is a hamiltonian path of T containing xy.
Additionally, if V(S) is dominated by U U W, then H = uo umxywo WkHs
is a hamiltonian path of T which contains xy for any hamiltonian path Hs of
S. Hence, we may assume that V(S) neither dominates nor is dominated by
UUW. Choose the minimal r such that a vertex v of the rth strong component
of S is beaten by some vertex of U U W. Without loss of generality, assume that
UiV G A(T) for some i.
If vuj G A(T) for some j > z, choose the minimal such j. Observe that
P' = yuo Uj^ivUj urnx and Q' Q are internally vertex disjoint paths from
42
y to x with\V(P'){JV{Q')\ > \V(P)UV(Q)\, contradicting the maximality of P
and Q. Consequently, Uj dominates v for every j > i, and in particular, umv e
A(T). Now, partition S into two disjoint subtournaments, Si (possibly empty)
containing the vertices of the first r 1 components of S and S2 containing the
remaining vertices. Thus, v is in the initial strong component of the tournament
S2 Let Hi be any hamiltonian path of S\ and let be a hamiltonian path
of S2 that begins at v. Since the terminal vertex of Hi is from the (r l)st
component of S, this vertex dominates U U W by the minimality of r. Thus,
H = Hiw0 w^xyuo umi/2 is a hamiltonian path of T containing xy.
The above result can be used to derive some tests for traceability for a given
arc xy. In the next section we will show that each of the following results can
be improved.
Corollary 4.8. Let xy be an arc of T. If d+(y) > d+(x), then there is a
hamiltonian path ofT that includes the arc xy.
Proof As d+(y) > d+(x), Ar+(?/) > A'+(x). Furthermore, xy A{T) so
ye N+{x)\N+(y). Thus
\N+(y) \ N+(x)I = \N+(y)\ \N+ (y) n N+{x)
> W+{y)\ \N+(x) \ {y}\ = d+(y) (d+(x) 1)
>2.
Thus, there exist distinct vertices u\ and u2 such that yuix is a path of length
two for i = 1,2, and by Theorem 4.7, the arc xy is traceable.
43
The next three sufficient conditions for arctraceable tournaments are closely
related, and follow from the fact that all 2connected tournaments are arc
traceable, which can be thought of as a corollary of Theorem 4.7.
Corollary 4.9. IfT is a tournament with 5 > then T is arctraceable.
Proof. We prove that the condition guarantees that T is 2connected. Assume
otherwise, and choose v such that T v is not strong. Let a and b be the number
of vertices in the initial and terminal strong components of T v, respectively.
Then T v must contain a vertex with indegree at most and a vertex with
outdegree at most Thus,
25{T) < S+(T)+5~(T) < 5+(Tv)+5{Tv)+2 < a + b~2+2 = a~b+~.
Z z
Finally, since n > a + b + 1, S(T) <
Corollary 4.10. IfT is a tournament such that for every uv G A(T), d~(u) +
d+(v) > then T is arctraceable.
Proof. The proof is the same as for Corollary 4.9, combined with the additional
observation that the vertex u with indegree at most in T v dominates the
vertex w with outdegree at most ^ in T v. Thus we have an arc uw such
that
d~(u) + d+(w) < df_v(u) + df_v(w) + 2 <  + 2 < ^*7
Corollary 4.11. Let T be a tournament such that i(T) < Then T is
arctraceable.
44
Proof. The result follows from Corollary 4.9 and the fact that i(T) = (n 1)
28. Thus, 8 > s implies that i(T) <(nl)^ = ^.
4.2 The structure of nonarctraceable tournaments
Since the results of the previous section are really based on the observa
tion that every twoconnected tournament is arctraceable, Theorem 4.7 has
not yet proven useful in the study of arctraceable tournaments. However, the
contrapositive of Theorem 4.7 can be used to obtain some important necessary
conditions for nonarctraceable tournaments. This necessary structure is the
basis for improving the bounds given in the Corollaries above and for many of
the results to follow.
Theorem 4.12. If T is a strong tournament, and xy 6 A(T) is not on a
hamiltonian path, then:
(i) There exists a vertex z such that T z is not strong.
(ii) T z has k strong components, k > 4.
(Hi) x is in the initial strong component of T z, and y is in the terminal
strong component ofT z.
(iv) z is dominated by the 2nd strong component ofT z and z dominates the
(k l)st strong component ofT z.
Proof. By Theorem 4.7, there is at most a single vertex disjoint path from y to
x in T, and since T is strong, there must be exactly one such path. Equivalently,
by Theorem E, there is a y, xseparating set of size one. Let {z} be this set.
45
Thus, there is no path from y to x in T z, so y and x are in different strong
components of T z and this tournament is not strong, establishing (i). Let Tz
denote T z, k be the number of strong components of Tz, and Tz1\t^2\ T
be the strong components of Tz where dominates Tz^ whenever i < j.
As x dominates y in Tz, x must be in a strong component that precedes
the strong component containing y. So, x can not be in the terminal strong
component of Tz. If Â£ is not in the initial strong component of Tz, then T x
is strong and every arc incident with x is on some hamiltonian path. Thus, x
must be in the initial strong component of Tz. Similarly, y must be a cut vertex
of T, so y must be in the terminal strong component of Tz, establishing (iii).
If k = 2, then let Pi be a hamiltonian path of Tj^ that terminates at x, and
P2 be a hamiltonian path of Ti that begins at y. Since T is strong, z must
beat some vertex of the path Pi. Let w be the first such vertex along the path
Pi. If w is the initial vertex of Pi, then let H = zP\P2 Otherwise, let w~ be
the vertex immediately preceding w on Pi and replace the arc w~w of Pi with
the path w~zw to form P'x and let H = P[P2 In either case, H is a hamiltonian
path of T containing xy, contradicting the choice of xy. So, k > 3.
Next, assume that there is some z+
we can choose z Â£ N^(z) fl V(Ti^), and let Pk be some path from y to
z' in Tzk\ Now, let P'k be a hamiltonian path of the tournament induced on
V(Tzk^)\V(Pk), let Pi be a hamiltonian path of Tj1^ that terminates at x, let P2
a hamiltonian path of T^ that originates at z+, and let p be any hamiltonian
path of for 3 < i < k 1. Combining these paths we can construct
H = PiPfczP2P3 PkiP'k, a hamiltonian path of T containing xy. Hence, there
46
Figure 4.1: An arctraceable tournament.
is no such z+ in V(Tj2'*). Dually, we have that there is no Nif (z)nF(Tjfc~^) = 0,
establishing (iv). This argument also shows that k 1^2, and so k ^ 3. Hence,
k > 4 establishing (ii).
j The above result indicates a necessary structure for tournaments that are
j not arctraceable. However, such a structure is not sufficient to guarantee non
j arctraceability. For example, the arctraceable tournament in Figure 4.1 has
the structure indicated in Theorem 4.12.
In an attempt to complete a characterization of arctraceable tournaments,
 we consider whether additional structure imposed on the first and last strong
I
j components of T z is sufficient to guarantee nonarctraceability.
j
 Lemma 4.13. Let T be a strong tournament with cut vertex z Â£ V(T), such
 that T z has k > 4 strong components. Further, let T) dominate z and let z
 dominate Tzk~^ inT. For x Â£ andy Â£ Tzk\ xy is part of some hamiltonian

j path if and only if (i) the vertices of can be partitioned into paths P\, Q\
\
\ such that Pi begins at a vertex dominated by z and Q\ ends at x or (ii) the
i
i

!
I
i
i
i
47
(k)
vertices of Tz can be partitioned into paths Pk, Qk such that Qk begins at y
and Pk ends at a vertex that dominates z.
Proof. We prove only the sufficiency of condition (i), as condition (ii) is equiv
alent to condition (i) in the reversal of T. Assume that condition (i) holds. Let
Pj be a hamiltonian path of for 2 < i < k 1, and let Qk be any path
in Tz^ from y to a vertex that dominates z. Finally, let P*. be a hamiltonian
path of T(zk) V{Pk). Then H = QiQfc^P^A ... Pk is a hamiltonian path of
T containing the arc xy.
For the converse, assume that T is arc traceable and let H be a hamiltonian
path of T containing the arc xy with x G T1]1^ and y G Tzk\ First, observe
that H contains at most one other arc uv with u G and v Â£ Tzl\ as z
must lie between any two such arcs on H. If H does not contain another arc
with this property, then the initial vertex of H must be a vertex of Tz In
this case, the portion of the path H that lies in is a hamiltonian path of
the subtournament Tj1'* that begins at a vertex dominated by z and ends at x.
Removing any arc of this subpath yields two paths that satisfy condition (i).
So, we may assume that H contains an arc uv ^ xy with u G and v tfz
and in this case, the portion of H that lies in Tz^ consists of two vertex disjoint
paths, Pi and Qi (assume that Pi precedes Qi on H). If xy precedes uv on H,
then Pi ends at x and the vertex immediately preceding Qi on if must be z,
and so condition (i) is satisfied. If uv precedes xy on H, then there must be an
arc u'v' with u' ^ and v' G Tsuch that u'v' precedes xy on H. In the
reversal of T, we find that yx precedes v'u! on the reversal of H, and condition
(i) is satisfied in T, and equivalently, condition (ii) is satisfied in T.
48
We note that a corollary of this result does give a sufficient condition for
nonarctraceability in strong tournaments.
Corollary 4.14. Let T be a strong tournament having the structure given by
Theorem 412. If \N+(z) D T^\ = 1 and jV~(z) n  = 1, then T is not
arctraceable.
Proof. Let N+(z) D = {x} and N~(z) H = {y}. Then by Lemma 4.13,
xy is nontraceable.
Note that the converse of this corollary is false, as the tournament in Figure
4.1 is not arctraceable.
At this point it appears we have characterized arctraceable tournaments.
However, Lemma 4.13 is deceptive. We offer the following corollary to make this
clear.
Corollary 4.15. Let T be a strong tournament having arc xy and the structure
given by Theorem 412. Let If N+(z) nTi1^ and W = N~(z) D Tj^. Now, if
necessary, reverse arcs ofTz^ to form the tournament R\ such that x dominates
U. Similarly, form the tournament Rwhere W dominates y by reversing arcs,
if necessary. Then xy is traceable in T if and only if the arc xu is traceable in
Ri for any u .6 U, or the arc wy is traceable in Rk, for any w G W.
Proof. If such a traceable arc exists in Rk or f?i, let H be a hamiltonian path
containing this arc. Now form paths P and Q that satisfy Lemma 4.13 by
deleting the arc xu or wy. Conversely, if there exist two paths that satisfy this
Lemma, then these two paths plus an arc xu or wy form a hamiltonian path of
Rx or Rk, respectively.
49
It is now clear that our characterization is something of a tautology. A
tournament T is not arctraceable if and only if some other related tournaments
Rx and Rk are not arctraceable. For this reason, we generally will find it easier
to use the incomplete results of Theorem 4.12 to produce sufficient conditions
for arctraceable tournaments (and conversely, necessary conditions for nonarc
traceable tournaments), and will use the additional structure given by Lemma
4.13 less often.
One aspect of Lemma 4.13 that we will use in the next section is that
whenever Tz has more than one vertex of minimal indegree (outdegree), then
one of these vertices must dominate (be dominated by) z. We state this as a
separate lemma.
Lemma 4.16. Let T be a nonarctraceable strong tournament, and let xy be
a nontraceable arc of T. If 5 (T) > 1, then either x is the unique vertex
of minimal indegree in Tz or 8~(T) = 8~(TZ) for the vertex z in Theorem
412. Similarly, either y is the unique vertex of minimal outdegree in Tz or
8+(T) = 8+(Tz).
Proof As 8(T) > 1 and 8(TZ) > 8(T) 1, we conclude that 8(TZ) > 1, and
the initial and terminal strong components of Tz contain at least three vertices.
Let R and S be the initial and terminal strong components of Tz, respectively,
and consider Rx and Sy. Vertices of minimal indegree in Tz must either be x or
in the initial strong component of Rx, and by Lemma 4.13, Rx must dominate
z (otherwise any hamiltonian path of Rx and the trivial path x imply that the
arc xy is traceable). Thus either 8~(TZ) 8~(T) or the only vertex of Tz with
minimal indegree is x. In exactly the same way, the terminal strong component
50
of Sy is dominated by z and so either 8+(Tz) = 3+(T) or the only vertex of Tz
with minimal outdegree is y.
4.3 Applications of the structure results
Although the structure described above falls short of a complete character
ization of nonarctraceable tournaments, it gives a great deal of information
about such tournaments. Using this structure, we improve several of the pre
vious sufficient conditions for arctraceable tournaments as well as improving a
result of Volkmann [42] for tournaments with 3 > 2.
Theorem 4.17. IfT is cl strong tl tournainent vjtth 8 ^ 2 and d (^r) ~\~d (gj')
 2 for every xy G A(T), then T is arctraceable.
Proof. We prove the contrapositive: if T is not arctraceable, then for some arc
xy of T, d~(x) + d+(y) <  2. Assume that T is not arctraceable, with arc
xy on no hamiltonian path of T. Thus, T has the structure given by Theorem
4.12. Let a be the number of vertices in and let b be the number of vertices
in T^k\ Since Tand Tzk~X^ are distinct and nonempty and \TZ\ \T\ 1,
n > a+b(3. Choose vertices u of minimal indegree and v of minimal outdegree
from Tz.
Clearly, u G and v G Tzk\ and hence uv is an arc of Tz and so also
an arc of T. As 8(TZ) > 5(T) 1 > 0, both and Tcontain at least
three vertices. Furthermore, if Tz^ is regular or nearlyregular, then by Lemma
4.16, we can choose u such that df(u) = dif (u) < Otherwise, df(u) <
dfz(u) + 1 < yy + 1 = yy. Similarly, df.(v) < yy. Thus df(u) + df(v) <
a+]p2 < 2=^ <  2, completing the proof.
51
The above result gives Orelike degree conditions on a tournament that
guarantee arctraceability. As an obvious corollary we state the result with
Diraclike degree conditions.
Corollary 4.18. IfT is a strong ntournament with 5 > ^ 1 > 1, then T is
arctraceable.
As a consequence of this Diraclike condition, we state the result in terms
of irregularity, similar to Theorem I.
Corollary 4.19. IfT is a strong ntournament with 5 > 1 and i(T) <  + 1,
then T is arctraceable.
Proof. i(T) = (n 1) 2<5, so i(T) <  + 1 implies that (n 1) 25 <  + 1.
Solving for 5, we obtain 5 > f 1.
The structure of nonarctraceable tournaments also gives a succinct proof
of the following result of Volkmann.
Theorem L (Volkmann [42]). In a strong tournament T, every arc of T is
on some path of length at least [.
Proof. If T is arctraceable, then every arc of T is on a path of length n and the
result is immediate. So we may assume that T is not arctraceable, and hence
for any arc xy that is not on a hamiltonian path, T has the structure indicated
in Theorem 4.12.
Let rq be the number of vertices in the ith component of Tz. Now, let j be
the largest integer less than k such that z is dominated (in T) by some vertex
52
in the jth component of Tz. Note, 2 < j < k 1 and some vertex in the j + 1st
component of Tz is dominated by z. We can now construct two paths Pi and P2,
each containing the arc xy with orders 1 + rik + Ylf%=i ni and 1 + ^1 + Yli=j+1 nn
respectively. Thus, the sum of the orders is at least
k
n\ + nk + 2 + ^ rii = ni + nk + 2 + (n 1) > n + 3
2 = 1
and one of has order at least and hence length at least
In fact, by combining the above proof and Lemma 4.16 we obtain the fol
lowing corollary.
Corollary 4.20. IfT is a strong ntournament with 1 < 5 <  1, then every
arc xy is on a path of length at least + 25.
We present one additional degree condition based on Theorem 4.12, a local
condition that is sufficient to guarantee that a given arc is traceable.
Theorem 4.21. Let T be a strong tournament with 5 > 1 and let xy G A(T).
If d+{y) > d+(x) 4, then xy is traceable.
Proof. Assume that xy is nontraceable. Then T has the structure given by
Theorem 4.12. Furthermore, as <5 > 1, we can choose ui from Tj1^ such that x
dominates u\, and u2 from Tz^ such that U2 dominates y. Next, we can choose u3
and U4 from Tj2^ and Tzk~X\ respectively. From the structure of Tz, x dominates
ut and Ui dominates y for each i, 1 < i < 4. Additionally, x dominates y, so
{ui,U2,u3,U4,y} C N+(x) \ N+(y). Finally, N+(y) \ N+(x) C {z}, and so we
have
d+(y) = d+(x) + A^+(y) \ N+{x)I A^+(x) \ N+{y)\ < d+(x) 4.
53
Next, we give two results that relate arctraceability to kings in tournaments.
A king in a tournament is a vertex that reaches all other vertices via a directed
path of length at most two. Tournaments in which every vertex is a king were
studied in [35] and [8]. The first result, for all tournaments, is sufficient to show
that allkings tournaments are arctraceable.
Theorem 4.22. If T is an ntournament with n or n 1 kings, then T is
arctraceable.
Proof. Assume that T is not arctraceable, and hence has the structure given in
Theorem 4.12. Choose v\ and v% from Tand Tzk\ respectively and observe
that for any vertex u G Tz the shortest path from v, to u has length at least
three. Thus neither v\ nor V2 are kings and so T has at most n 2 kings.
When 5 > 1, similar techniques give a slightly improved result.
Theorem 4.23, If T is a nonarctraceable strong ntournament with <5 > 1,
then T has at most n 3 2S+ kings.
Proof. Assume that T is nonarctraceable, and let xy be a nontraceable arc
of T. Then T has the structure given by Theorem 4.12, and since <5 > 1,
T2(1) has order at least three. As a consequence of Lemma 4.13, there must be
some vertex v G with v > 2. Now, for any vertex w G Tz^ for 3 > 1.
the shortest path from w to v has length at least three. Hence we conclude
that the set of kings of T is contained in V(TzU {2}. We count the vertices
not in this set and find at least one vertex each in Tz and Tz and at least
54
26+(Tz) + 1 vertices in Tzk\ Thus, there are at most n 2 (25+(Tz) + 1)
kings of T, and the proof is complete if 5+(Tz) = <5+(T). Otherwise, since
<5 > 1, Lemma 4.16 implies that Tz^ is not regular or nearly regular, and so
must have at least 2S+(TZ) + 3 vertices. In this case, we again have at most
n 2 (2 5+{Tz) + 3) = n 2 (2(6+(T) l) + 3) = n3 <5+(T) kings in
T.
4.4 Extremal results related to arctraceable tournaments
In this section, we use the structure of nonarctraceable strong tournaments
to produce some extremal results. First, we fix n and consider the maximum
number of nontraceable arcs in a strong ntournament. Later, we consider tour
naments with m arcdisjoint paths between any two vertices, and we determine
the minimal n such that some marcstrong ntournament is not arctraceable.
In Chapter 3, we constructed an upset ntournament with n2~^n+3 non
traceable arcs for any odd n, and we proved that this tournament was maximal
with respect to the number of nontraceable arcs. We will denote this tour
nament Tmax, and recall that this tournament is obtained from the transitive
tournament on the set V = {u0,... un_i} where d+{vi) = i by reversing the arcs
ViVi+2 for each even i < n 1. We now prove that any strong ntournament T
has at most this number of nontraceable arcs with equality if and only if T is
isomorphic to Tmax.
Lemma 4.24. Let T be a strong tournament having a cutvertex z. If X =
{x : T2(1) can not be covered by paths P and Q such that P begins at a vertex
dominated by z and Q ends at x}, then X < where a = \Til\. Similarly,
T < for the analogous set Y, where b \Tzk^\.
55
Proof. Assume that X = {xo, Xi,..., xm}. If IV+(z) n X\ > 1, then assume
that z dominates xq. Let p be the longest path not containing Xj that begins
at a vertex dominated by z. As z dominates xo or some some vertex z+ ^ X,
Pi is a path containing at least one vertex for each i, 1 < i < m. Let Si =
V(Tz^) \ V(Pi) for 1 < i < m. We claim first that Si \ {xj dominates V(Pi).
Assume otherwise, and let v be the last vertex along p such that v dominates w
for some w Â£ Si\{xj}. If v is the terminal vertex of p, then pic is a longer path
than Pi beginning at a vertex dominated by z. Otherwise, by the minimality of
v, we can replace the arc vv+ of Pi with the 2path vwv+ and again obtain a
path that begins at vertex dominated by z that is longer than Pj. Note, since
P(1) is strong, Si must be reachable from V(Pj), and thus some vertex of 1/(Pj)
must dominate Xj. Choose such a vertex and call it t/j.
Now, let Qi be the longest path of T[Si} that ends at Xj, and let P, =
Si \ V(Qi). By the definition of X, Ui 7^ 0 for 1 < i < m and Ui C Si \ {xj},
so Ui dominates V(Pi). By a similar argument used above, we also note that
P, is dominated by each vertex of V(Qi). Thus, we conclude that V'(Qj) \ {xj}
dominates both Pj and V(Pj).
Additionally, observe that the terminal strong component of P[Pj] contains
no vertex of X and hence Pj \ X 0. To see this, let H be any hamiltonian
path of P[Pj] ending at some vertex of X, and construct the paths QiH and Pj,
which partition the vertices of The initial vertex of Pj begins at a vertex
dominated by 2, and so by definition the terminal vertex of QiH is not in X.
Since we can choose H so that it ends at any vertex in the terminal strong
component of T[Pj], this terminal strong component is disjoint from X.
56
Finally, we claim that UiDUj = 0 for all i ^ j. Assume otherwise, and choose
i ^ j with u G U, fl Uj. Without loss of generality assume that xt dominates xr
Since u G Ui, and Ui dominates V(Pi), u dominates V{. Similarly, as V(Qi) and
V (Qj) dominate U,nUj, Xi and Xj both dominate u. Since Vi does not dominate
u and V(Qj) dominates u, ^ V(Qj), and hence U; G V(Pj) U Uj. Also, since
Xi dominates xj by assumption, and V(Qj) dominates Uj, xt ^ Uj. Further, xt
dominates u and Uj dominates V(Pj) so Xj ^ V(Pj). Thus, Xi G V(Qj) \ {xj}
and so Xi dominates both Uj and V(Pj). Since vt G V(Pj)UUj, this requires that
Xi dominates V{, contradicting the choice of v, as a vertex of Pi that dominates
Xi
The above arguments show that Ui \ X ^ 0 for 1 < i < m and UiHUj =
for i ^ j, which establishes that
. i=l
= Â£;t/i\X>m = Xl.
i= 1
Thus, we have a > A + m = 2m + 1 = 2\X\ 1 and so AT <
The bound for the set Y is obtained using an identical argument in the
reversal of T.
Corollary 4.25. Let T be a strong tournament having the structure given by
Theorem 412. The number of nontraceable arcs from Tj1'* to Tis at most
lab+a+b+l) where a = Tb) and b = TW_
Proof. Let B be the set of arcs we wish to count. Define the sets X and Y as in
Theorem By Lemma 4.13, an arc a = uv is in the set B if and only if u G X
and v G Y and so J3 = XT and by Lemma 4.24, JAy = AtlALtll
57
Theorem 4.26. If T is a strong ntournament, then T has at most 4k
nontraceable arcs, with equality if and only ifT is isomorphic to Tmax.
Proof For n = 3 and n 4, there is a unique strong ntournament, and in
both cases this tournament is arctraceable and so has at most 0 = _4 ~F4)+3j
nontraceable arcs, and this tournament is isomorphic to Tmax.
For n > 4, assume that T is nonarctraceable. Let xy be a nontraceable
arc of T, and let T have the structure given by Theorem 4.12. Let A = and
B = Tzk\ with a = \A\ and b = P, and choose u Â£ Tand w Â£ Tik~l\ If
a x'y' is a nontraceable arc of T, neither T x' nor T y' are strong, and
hence x' and y' must both be in the set A U B U {z}. Thus, a is either an arc of
T[A U {u, z}], an arc of T[B U {w, z}], or an arc from A to B.
We claim that every arc of T[Al){u, z}] or T[Bu{w, z}} that is nontraceable
in T is also nontraceable in this subtournament. Assume that some arc a is
traceable in T[A U {u, z}], and let P be a hamiltonian path of this tournament
containing the arc a. If P ends at a vertex other than z, then for any hamiltonian
path Q of the vertices not on P, PQ is a hamiltonian path of T containing a.
On the other hand, u has outdegree one in this subtournament, so if H ends
at z it must end with the arc uz. If a is not the arc uz, then we can remove
this arc from the end of P to obtain the path P'. Then for any hamiltonian
path of the remaining vertices Q such that Q ends at a vertex dominating z,
P'Qz is a hamiltonian path of T containing a. Finally, if a = uz, then we can
let P' be any hamiltonian path of beginning at a vertex dominated by 2
and if Q is any hamiltonian path of the remaining vertices of Tz u, aP'Q is a
hamiltonian path of T. An identical argument in the reversal of T establishes
58
the corresponding result for T[B U {w, z}}.
As both of the subtournaments T[A U {u, z}] and T[B U {w, z}] are strong,
we can apply the induction hypothesis, and hence T[Au{u, z}] and T[B\j{w, z}]
have at most (a+2) 4(a+2)+3 an(j (6+2) 4(b+2)+3 nontraceable arcs, with equality
if and only if each of these subtournaments are isomorphic to Tmax. Summing
these two values, we obtain 2+f~2.
Finally, by Corollary 4.25, there are at most (+1)(fc+i) n0ntraceable arcs
from A to B. Combining and observing that a + b < n 3, the number of
nontraceable arcs in T is at most
a2 + b2 2 ab + a + b+l (a2 + 2ab H b2) + 2(a + b)
 +  = g
(cl + b)2 + 2(o + b)
~ 8
^ (n 3)2 + 2(n 3)
8
^ n2 6n + 9 + 2n 6
8
n2 4n + 3
~ 8
The proof is complete by noting that in the above equation, equality is
established if and only ifn = a + Â£>F3 and the subtournaments T[AU {u, z}}
and T[B U {u>, z}) are both upset tournaments isomorphic to the appropriate
size Tmax. From this it follows directly that T is also an upset tournament and
isomorphic to Tmax.
As noted earlier, a consequence of Theorem 4.7 implies that for any non
traceable arc xy in a strong tournament T, there exists a y,x separating set of
59
Figure 4.2: A tournament with nontraceable arc xy and two arcdisjoint paths
from y to x.
vertices of order 1 (the vertex 2 in the theorem). We now show that a similar
result for a separating set of arcs is impossible. In particular, we show that for
any m > 0 there exists a strong tournament T that has a nontraceable arc xy
with m arcdisjoint paths from y to x. As an example, in the tournament in
Figure 4.2, xy is not on any hamiltonian path, and there exist 2 arcdisjoint
paths from y to x.
For convenience, throughout the remainder of this chapter we will let n =
2m+i. For an arbitrary m, we construct a strong tournament by reversing the
arcs of a set of m arcdisjoint paths in a transitive tournament of order n + 1.
Let T be a transitive (n + l)tournament with vertices labeled v0,... ,vn such
that d+{vi) = 2. Now consider the paths
Pi = VnV(2*)l>(T,22)V(n3.2*) WO, for 1 < i < 171.
We reverse the arcs in each of these paths to obtain the tournament T[m}, and
will refer to the reversed path Pt as the ith upset path and denote it Ut. Note, ri
is on each Lfo and thus for any i < ^ < j, v* separates n, and v3. Also, observe
that we can view the construction of 7]m+1] recursively; take two copies of 7m]
sharing a single vertex (the terminal endpoint of all the upset paths from one
copy, and the initial endpoint of the upset paths in the other copy) and reverse
i
60
the 2path Pm+1
Lemma 4.27. The arc vnvo is not on any hamiltonian path of the tournament
T[m}
Proof. For m 1, Tp] is an upset tournament on 5 vertices, and it is easy to
verify that v^vq is not on any hamiltonian path of Tp]. Now, assume the result
for m and consider Tjm+i]. Consider P, a path in Tjm+i] containing the arc V2nvo
of maximal length, and as Tjm+1] is isomorphic to its reversal, without loss of
generality assume that vn precedes V2n on P. Let vt be the terminal vertex of
P and Vi the first vertex of P with index i < n. Since vn separates va from Vb
for each a < n < b, every vertex between vl and vn must have index j < n.
Similarly, every vertex between vn and n must have index j > n and every
vertex following vq must have index j < n. Thus, all the vertices of P with index
j < n are contained in the subpaths Vi... vn and v0 ... vt. We now consider the
combined sequence of vertices Q = Vi,... ,vn,v o,... ,vt. Each of the vertices
in this sequence has index j < n, and every pair of consecutive vertices other
than vnv0 are joined by an arc of 7]m+1]. Since vnv0 Â£ A(T[m]),.we can use the
recursive perspective described earlier and think of this sequence as a path of
T[m]. Since Q contains the arc vnvQ, by the induction hypothesis, this can not be
a hamiltonian path of Tjm], and so there is a vertex va, a < n, that is not in the
sequence Q. By the minimality of i, va can not precede vi} and vn separates va
from V2n, so va can not lie between vn and V2n on P. Hence va is not on the path
P. Consequently, the longest path containing the arc nt hamiltonian,
and V2nvo is nontraceable.
61
Thus for any m, we can construct a tournament with n + 1 vertices with a
nontraceable arc xy such that there exist m arcdisjoint paths from y to x. Next
we show that this is the minimal number of vertices among strong tournaments
with this property.
Theorem 4.28. IfT is a strong ktournament containing a nontraceable arc xy
such that there exist m arcdisjoint paths from y to x, then k > n + l = 2m+1 + l.
Proof. Again, the proof is by induction. For m = 1, the result is obtained
by observing that the unique strong tournaments on 3 and 4 vertices are arc
traceable. Next, assume the result for m and consider the smallest strong k
tournament T, with nontraceable arc xy and m + 1 arcdisjoint paths from y
to x. Assume that k < 2n + 1 = 2m+2 + 1.
As xy is nontraceable, T must have the structure given by Theorem 4.12.
Furthermore, the minimality of T implies that Tz has exactly four strong com
ponents, and that the second and third components both consist of a single
vertex. Let X be the set of vertices in the first and second strong components
of Tz, and Y = V{TZ) \ X. Clearly, either X < n or T < n. Without
loss of generality, assume X < n and consider the tournament T[X U {z}}. If
zx G A(T), then reverse this arc to form the tournament T'. Otherwise, simply
let T' = T[X U {z}]. Since z is on every path from y to x, and there are m + 1
arcdisjoint paths from y to x, there also exist m + 1 arc disjoint paths from z
to x in T and at most one of these contains the arc zx (if it is an arc of T).
Thus, there are at least m arcdisjoint paths from z to x in V. Clearly, V is
strong and has fewer than n+l vertices, and so by the induction hypothesis, xz
is on some hamiltonian path of this tournament. Let P be such a hamiltonian
62
path, and split P into two smaller paths Pl5 consisting of all the vertices up to
and including x and P2, consisting of all the vertices of P that follow z. The
structure of T' guarantees that both Pi and P2 are paths of order at least 1.
The only vertex of T' on neither P\ or P2 is z, so each vertex of X is on either
Pi or P2. Next, the structure of T requires that T[Y U {z}] must be strong, so
let C be a hamiltonian cycle of this tournament and let Q\ be the subpath of
C from y to z, inclusive, and Q2 the subpath of C from the vertex immediately
succeeding z to the vertex immediately preceding y. We allow for the possibility
that Q2 may have order 0. Thus, every vertex of Y U {z} is on either Qi or Q2.
We now construct H = P1Q1P2Q2, and we claim that H is a hamiltonian path
of T. First, the terminal vertex of Pi is x and the initial vertex of Q1 is y, and
xy E A(T) by assumption. Next, the terminal vertex of Q1 is z, and the initial
vertex of P2 is the vertex immediately following z on P. Lastly, the terminal
vertex of P2 is a vertex of X, while the initial vertex of Q2 (if any) is a vertex
of Y, and X dominates Y. So, H is indeed a path of T. That H is hamiltonian
is immediate; it includes all of X and Y as well as the vertex z. Finally, H
includes the arc xy. But xy is nontraceable, contradicting our assumption that
k < 2n + 1.
The previous results apply to a particular arc xy and as a result we make
no claim about the number of arcdisjoint paths between every two vertices.
In fact, for each rn, 7]m] contains a vertex of indegree 1 (i>(_i)) as well as
a vertex of outdegree 1 (iq), so we have yet to produce even a 2arcstrong
tournament that is not arctraceable. We now seek to construct such an marc
strong nonarctraceable tournament. Doing so requires only a minor variation
63
on the construction of 7]m].
Specifically, let 7j'nj be a tournament on n + 4m 3 vertices obtained from
Tjm] by removing the vertices v\ and and adding sets h\ and Un\ each of
order 2m 1. Orient the edges incident with vertices of U\ U Â£/_i such that
T[Ui\ and T[Uni] are regular tournaments of degree m 1, and Un\ dominates
every other vertex of Tj'mj except vn, and U\ is dominated by every remaining
vertex of Tj'mj except Vq.
Lemma 4.29. Tj'm] is marcstrong.
Proof. It suffices to show that v0 both reaches and is reached by every other
vertex of Tj'mj using m arcdisjoint walks. The result then follows by a variant
of Theorem E.
To show that each vertex reaches vq in m different ways, first consider any
vertex u G U\ and let N+(u) D Ui = {u\,..., um_i}. Clearly, Wi = uu^q for
1 < i < m 1 and Wm = uvo are m arcdisjoint walks from u to vq. Additionally,
for any vertex v ^ U\, Wl = vuiVQ for 1 < i < m 1 and lTm = vuvo are arc
disjoint walks from u to vq.
To show that Vo reaches every other vertex by m arcdisjoint walks, we use
the set of m upset paths Ui,... Um. Clearly, Lfi,..., Um are arcdisjoint paths
from Vo to vn. To show that Vo reaches every vertex of w (E Un\ by m arc
disjoint walks, let N~(w) Cl C/i = {w\,... wmi} and let Wi UiWiW for
1 < i < m 1 and Wm = Umw. As above, for v Â£ Cn_i U {vn}, let Wi UiWiV
for 1 < i < m 1 and Wm Umwv.
Lemma 4.30. The arc vnvo of TL, is nontraceable.
64
Proof. Assume the result is false, so there is some hamiltonian path H of Tj'm]
that contains the arc vnv0. Since N~(u) \ Un\ = {vn} for any u G C/n_i, any
path ending at a vertex of Un\ is either a path of T[Un1], or includes an arc
vnw for some w G Un\. Since H can not contain any of these arcs, every
subpath of H ending at a vertex of Un1 is a path of T[Un1] and hence the
first 2m 1 vertices of H are precisely the vertices in the set Un\. Similarly,
every subpath of H beginning at a vertex of U\ is a path of T[Ui] and hence
the last 2m 1 vertices of H are precisely the vertices in U\. Now, the subpath
Q of H beginning with first vertex of H not in Un1 and ending at the last
vertex of H not in U\ is also a path of 7]m] containing vnvo, and this path has
order n + 4m 3 (4m 2) = n 1. Furthermore, this path cannot begin
at the vertex vn because this vertex is in N+{u) for some u G Un\. Similarly,
the last vertex of Q is in N~(w) for some w G U\, so Q does not end at the
vertex Vq. Thus, vn_iQv\ is a path of 7m] with order n + 1, and hence vn\Qvx
is hamiltonian. But this path contains vnvo, contradicting Theorem 4.7. Thus,
vnVQ is nontraceable in 7j'mj,
Finally, we conclude this chapter with a proof that Tj'TO] has the fewest ver
tices among all nonarctraceable marcstrong tournaments.
Theorem 4.31. If T is a nonarctraceable marcstrong ktoumament, then
k > n + 4m 3.
Proof. For m = 1, the result is immediate by observing that all strong tourna
ments are 1 arcstrong and that 21+1 4(1) 3 = 5 is the size of the smallest
nonarctraceable strong tournament. So we can assume that m > 2. Let xy be
65
a nontraceable arc of T. Define Sx as the initial strong component of T x
and Sy as the terminal strong component of T y. If y G Sx, there would exist
a hamiltonian path of T beginning with the arc xy. So y Â£ Sx and similarly,
x Sy. As T is m arcstrong, 5^ > m and > m 1 for any v G V(T).
Thus, S^_x > m 1 and Sj^ > m 1 and consequently both IS^I > 2m 1
and 15^1 > 2m 1.
Next, we claim that Sx CiSy 0. Assume otherwise, and choose z G SxnSy.
Since z G 5^, it reaches every vertex of T x, and since y Sx, it reaches every
vertex of (T x) y. So 2 is in the terminal strong component of T y but the
initial strong component of T y x. As a result, the initial strong component
of T y must be {x}. This requires that = 0 < m 1, a contradiction.
Lastly, observe that no path from y to x can use any vertex of Sx U Sy, as
every path from y to Sx must contain the vertex x, and dually every path from
Sy to x must contain y. Thus we can form V by replacing the entire set Sx with
a single vertex ux and replacing the entire set Sy with a single vertex uy without
disturbing any path from y to x. Thus, there remain m arcdisjoint paths from y
to x in T'. Furthermore, if we let x dominate ux and let uy dominate y, then T' is
strong. By a similar argument to the one used in Lemma 4.30, any hamiltonian
path of T' containing the arc xy can be extended to a hamiltonian path of T
containing this arc. As xy is not on any hamiltonian path of T by assumption,
it is therefore not on any hamiltonian path of T'. By Lemma 4.28, T' has at
least n + 1 vertices and so T has at least (n + 1) 2 + 2(2m 1) = n + 4m 3
vertices.
66
5. Related problems
In this concluding chapter, we consider arctraceability in other classes of
digraphs related to tournaments, as well as various other ways to generalize
arctraceability. We will introduce new definitions and notation as needed. The
main result of this chapter will be a characterization of arctraceability in the
class of strong rounddecomposable locally semicomplete digraphs. These results
are intended to suggest new directions for the investigation of arctraceable
digraphs and to propose the study of properties similar to arctraceability that
bear further study.
5.1 Semicomplete digraphs
A semicomplete digraph is a strict digraph D, such that for every pair of
distinct vertices x,y E V(D), either xy E A(D) or yx E A(D) or both. In other
words, a semicomplete digraph is any strict digraph that contains a tournament
as a spanning subdigraph. As such, we would like to be able to generalize the
techniques and results of Chapter 4 in a natural way to obtain results for this
class of digraphs.
For example, we note that just like tournaments, the condensation D* of a
semicomplete digraph D is a transitive tournament. Thus, just as for tourna
ments we have the following observation.
Proposition 5.1. Let D be a semicomplete digraph. If D is arctraceable, then
D is strong or has two strong components D\ and D2, each of which are arc
traceable semicomplete digraphs.
67
Next, we will show that every 2connected semicomplete digraph is arc
traceable. The argument used in Chapter 4 for tournaments only uses the fact
that strong tournaments are hamiltonian. So our next observation follows by
observing that a strong semicomplete digraph is hamiltonian due to Theorem
D.
Proposition 5.2. Every 2connected semicomplete digraph is arctraceable.
Continuing in this way, a careful reading of Lemma 4.3 and Theorem 4.4
shows that these results hold for semicomplete digraphs as well as tournaments.
Thus we obtain the same sufficient condition given by Corollary 4.5.
Corollary 5.3. If D is a strong semicomplete digraph, and every arc of D is
on some cycle of length l > then D is arctraceable.
Up to this point, we have obtained exactly the same results for semicomplete
digraphs that we did for tournaments. However, an analog of Theorem 4.7 is
not quite as immediate. If an arc xy of a semicomplete digraph D is part of a
cycle of length two, then it makes no sense to speak of a y, xseparating set and
we are not able to use Mengers Theorem. Apart from this difficulty, however,
the proof of Theorem 4.7 remains valid even when other 2cycles remain in the
digraph. This yields a result that is only slightly modified.
Theorem 5.4. Let D be a strong semicomplete digraph and let xy e A(D) be
such that there exist at least two (internally) disjoint paths of length at least two
from y to x in D. Then there exists a hamiltonian path of D containing the arc
xy.
68
As a result of this modification, the structure of a nonarctraceable strong
semicomplete digraph is similar but not identical to the structure for tourna
ments. To make the analog of Theorem 4.12 as simple as possible, we define the
subdigraph D(uv) of D by V(D{uv)) = V(D) and A(D^uv)) = A{D) \ {uv}. So,
in the case where uv ^ A(D), D^uv) = D. Certainly, no path including the arc
xy can also include the arc yx. Thus, we observe that xy is traceable in D if
and only if xy is traceable in D(yx). We now give the main structure theorem
for semicomplete digraphs, which is an amalgam of the semicomplete digraph
analogs of Theorem 4.12 and Corollary 2.2.
Theorem 5.5. If D is a strong semicomplete digraph and xy 6 A(D) is not on
a hamiltonian path, then either Dyx has three or more strong components, or
there exists a vertex z 6 V(D(yx)) such that:
D(yz) z has k > 4 strong components.
x is in the initial strong component, and y is in the terminal strong com
ponent of D(yx) z.
z is dominated by the 2nd strong component and dominates the (k l)st
strong component of D^yx) z
To illustrate Theorem 5.5, we give two nonarctraceable strong semicom
plete digraphs in Figure 5.1. The digraph on the left has nontraceable arc
xy, and the digraph obtained by removing the corresponding arc yx has three
strong components. The right hand digraph has the structure similar to non
arctraceable strong tournaments, but with the additional arc yx. In both cases,
additional 2cycles may be present within the components.
69
s
I
;
i
i
Figure 5.1: Two nonarctraceable strong semicomplete digraphs.
Proceeding in this fashion, we can use the slightly modified structure given
above to yield results for semicomplete digraphs that closely match the results for
tournaments. We illustrate this by giving degree constraints sufficient to guar
antee arctraceability. Observe that these conditions differ significantly from the
conditions for tournaments because in the strong components of a semicomplete
digraph we allow cycles of length two.
Theorem 5.6. If D is a strong semicomplete digraph on n vertices with 8 > 2,
and for every xy E A(D), dr(x) + d+(y) > n 2, then D is arctraceable.
Proof. Assume D is not arctraceable. Then by Theorem 5.5, either D(yx) has
three or more strong components or we can find a vertex z as described in the
theorem.
If D(yX) has three or more strong components, then let a and b be the
number of vertices in the initial and terminal strong components, respectively.
Note, n > a + b +1, and since 5 > 1, both a and b are at least two. This implies
i
)
I
i
70
that we can choose vertices u and v in these components with d^(u) < a 1
and dp(v) v and hence we have an arc of
D with d~{u) + d+(v) < a + b 2 = n 3.
If instead, D^yx) has a vertex z as described in Theorem 5.5, let the number
of vertices in the first strong component of D(yx) z be a and let b be the number
of vertices in the last strong component. This requires that n > a + b + 3, and
both a vertex u with dA (u) < a 1 and a vertex v with dt (v) < b 1.
Again, it is clear that u > v in D and for this arc, dp(u) + dj(u) < (d^ (u) +
!) + (dDiyx)(u) + i) =a + b = n3.
5.2 Round digraphs
Another generalization of tournaments in which arctraceability can be con
sidered is the class of digraphs known as local tournaments. A digraph is a local
tournament if the subdigraphs induced on N+(v) and N~(v) are tournaments
for every vertex v. Originally introduced as locally semicomplete digraphs in [5],
the structure of local tournaments was investigated by Huang in [19].
Our analysis of arctraceable locally semicomplete digraphs begins with a
special case of local semicomplete digraphs called round digraphs. A digraph D
is said to be round if there is an ordering of V(D) such that N~(vi) = {vi 1 <
j < d~(vi)} and Ar+(ui) = {vi+j \ 1 < j < d+(vi)} for each vt G V(D) (addition
of subscripts is modulo n). The ordering is called a round labeling or round
enumeration of the digraph D. We give a few observations about round digraphs
in general.
Theorem M (Huang [20]). A round digraph is locally semicomplete.
71
Figure 5.2: A round local tournament with cycles of length two.
Proof. Let D be a round digraph with round labeling V(D) = {no, un_i}. If
d^{vi) < 1, then the outneighborhood of Vi is trivially a semicomplete digraph.
So for any i such that d+{vi) > 1, choose Vj and Vk from N+(vi). Without loss
of generality, assume that i < j < k. Now since vt E N~(vk), the round labeling
implies that Vj E N~(vk). Thus, every pair of distinct vertices in N+(vi) are
adjacent. Similarly, every pair of distinct vertices in N~(vi) are adjacent, D is
locally semicomplete.
Since a semicomplete digraph with no 2cycles is a tournament, we get a
sufficient condition for a round digraph to be a local tournament.
Proposition 5.7. A round digraph with no cycles of length two is a local tour
nament.
The converse of this statement is false, however, as shown by the round
digraph in Figure 5.2 which is a local tournament despite having a cycle of
length two.
It is easy to see from the round labeling that any round digraph with <5+ > 1
is hamiltonian, since V{ > vi+i for each i, 0 < i < n 1. A similar argument
gives a sufficient condition for a round digraph to be arctraceable.
72
Theorem 5.8. A round digraph D with 5+ > 2 is arctraceable.
Proof. Let D be a round digraph with 5+ > 2, and let V(D) = {u0,..., vni}
be a round labeling of D. Now choose any arc a = ViVj of D. If j = i +1, then a
is on a hamiltonian cycle, so we may assume that j i + 1. Consider the vertex
Vj1 Since d+(vj1) > 2, the round labeling requires that v31 > vj+i and we
can construct the hamiltonian path vi+\vi+2 VjiVj+\vJ+2 .. ViVj.
Before returning to the case of
graphs. Clearly, these are precisely the round digraphs with d+ = 0. We show
that such digraphs are acyclic.
Lemma 5.9. If D is a round digraph that is not strongly connected, then D is
acyclic.
Proof. Let D be a round digraph with the usual round labeling, and let C be
a directed cycle in this digraph. Then some arc of C must be of the form v3Vi
with i < j. The round labeling forces N+(vj) C {v3+\,..., un_i, v0,..., and
so we have VjVq A(D). Again, we use the round labeling, which implies that
Ar~(fo) Â£ {vj,... ,un_i}. Using the round labeling a third time, we find that
N~(vi) C {v3,..., un_i, Vo,. , i}. This implies that d+(vk) > 1 for 0 < k < i
and j < k < n 1 and since Vi is on the cycle C, d+(vi) > 1 as well.
Now certainly, for any k with i < k < j, C contains some arc vaVb with
a < k < b. Thus, using the round labeling once again, Vk N~(vb) and so
d+(vk) > 1 for each i < k < j and hence we have <5+ > 1 and D is strong.
As a consequence of the above lemma, we observe that a round digraph that
is not strongly connected has at most one hamiltonian path.
73
Proposition 5.10. An acyclic digraph has at most one hamiltonian path
Proof. Let Hx = v\v2 vn be a hamiltonian path of a directed graph D. Then
if D contains any other hamiltonian path ff2, this path must include an arc VjVi
with % < j, which implies that ViVi+xvi+2 Vj is a cycle of D.
Hence, the only arctraceable round digraph that is not strongly connected
is a directed path.
Proposition 5.11. A round digraph D that is not strongly connected is arc
traceable if and only if it is a directed path.
To complete our brief analysis of arctraceable round digraphs, we return
to the case where <5+ = 1. We proceed in a similar way as we did for upset
tournaments; we give necessary and sufficient conditions for a given arc to be
traceable.
Theorem 5.12. Let D be a strongly connected round digraph with round labeling
V = {no,... ,vn\}. An arcViVj is traceable if and only if j = i +1, d+(vX 1) > 2
ord+(vj1) > 2.
Proof. Assume that a = ViVj is traceable and j i + 1. Let if be a hamiltonian
path of D containing this arc. Define the sets Vi = {vi+ivi+2 Vj2Vj1} and
V2 = {vj+\Vj+2 If Vi1 precedes a on H, then H must include some
arc vaVb with va G V2 and Vb G V\. Thus, ViX G N~(vb) and so d+(vi1) > 2.
Similarly, if 1 follows the arc a on if, then there is some arc vaVb on if with
va G Vx and vi, G V2 and thus VjX G N~(vb) and d+{vj1) > 2.
For the converse, assume first that j = i + 1. In this case, ViVi+1 vlX
is a hamiltonian path containing a. Next, assume that d+(viX) > 2. Then,
74
Vi^\Vi+\ is an arc of D and ViVjVj+i Vi^iVi+ivi+2 Vj\ is a hamiltonian
path of D so long as j ^ i 1. In this case, ViVjVi+\vi+2 fi2 is a hamil
tonian path of D. Finally, if d+(u7_i) > 2, Vj\Vj+i is an arc of D and thus
Vi+iVi+2 Vj\Vj+1 ViiViVj is a hamiltonian path of D for j ^ i 1 and
vi+\vi+2 Vi2ViVj is a hamiltonian path otherwise.
We now take our characterization of traceable arcs and use it to obtain a
characterization of arctraceable strong round digraphs. Recall that D(uv) is the
digraph obtained from D by removing the arc uv, if it is present.
Theorem 5.13. Let D be a strong round digraph. Then D is arctraceable if and
only if D {x, y} is traceable and D^yx) has S~ + h+ > 0 for every xy A(D).
Proof. Let V = {n0,..., un_i} be a round labeling of D. Assume that D is
arctraceable and choose an arbitrary arc ViVj Â£ A(D). Thus, by Theorem 5.12,
j i + 1, d+(uj_i) > 2 or d+(u,_i) > 2.
First, we show that D(VjVi) has 5~ + > 0. If j ^ i 1, then D(Vjn) is
hamiltonian, and if j = i 1, then either Vj^x vt or Vj > vl+\ and so after
removing the arc VjVi} we still have d+(vj) > 0 or d~(vi) > 0. Since the in
degree and outdegree of all other vertices remains unchanged and D is strong,
it follows that S~ + d+ > 0 in D(VjVi), as desired.
Next, we show that D {x,y} is traceable. If j i 1, then let P be
the path Vi+2^+3 vn\VQ 2 Now, either Pv^i or vi+\P is a hamiltonian
path of D {x,y}. So we can assume that j i 1. If d+(vl_ 1) > 2, then
Vii > vi+x and Vj+1 Viifi+i Vj1 is a hamiltonian path of D {x,y}.
Similarly, if d+(vj_ 1) > 2, then Vi+\ Vj\v3+\ is a hamiltonian path of
75
Figure 5.3: A strong nonarctraceable round digraph.
 D{x,y}.
j
i For the converse, assume that D {vi,Vj} is traceable and D^VjVi) has
 <5+ h A > 0 for each vtVj G A(D). Let Vx = {vi+x,... ,Vj1} and V2 =
{vj+i,... and let H be a hamiltonian path of D {vi,Vj}. If neither
V] nor V2 are empty, then H must contain an arc vavi, from V\ to V2 or from
I V2 to V\. Thus, either Vj 1 G N~(vb) or v^i G N~(vb) and so d+(vj1) > 2
; or d+(uj_i) > 2. Hence, by Theorem 5.12 vtVj is traceable. If Vi is empty,
 then j = 2 + 1 and clearly, V{Vj is traceable. Finally, if V2 is empty, then
I j = i 1 and either N+(vj) = {ui} or Vj > Vi+\. Additionally, either
Ar~(vi) = {vj} or Vj1 > As 8+(D(VjVi)) + 8~(D{VjVi)) > 0, we must have
either Vj > vi+x or VjX > Uj. In the former case, ViVjVi+1 vuiVq Vi2 is
a hamiltonian path of D containing the arc vzVj. Similarly, in the latter case
Vi+\Vi+2 vn\VQV\ VjiVjVj is a hamiltonian path of D containing the re
quired arc. Consequently, ViVj is traceable and since this arc was arbitrary, D
is arctraceable.
j The need for the somewhat awkward extra condition on D{yx) in Theorem
 5.13 is illustrated in Figure 5.3. The transitive tournament with an additional
 arc from x to y is strong, with a single nontraceable arc (the arc xy), but the
i digraph remaining when the vertices incident with this new arc are removed
76
is certainly traceable. To see that this digraph is round, simply note that the
transitive ordering of the original tournament is also a round labeling of the
digraph.
5.3 Locally semicomplete digraphs
Turning our attention to locally semicomplete digraphs in general, we first
consider the case of such digraphs that are not strongly connected. In this case,
we use a result of BangJensen.
Theorem N (BangJensen [5]). If D is a weakly connected (but not strongly
connected) locally semicomplete digraph, then D*, the condensation of D, is
an acyclic round digraph and each strong component of D is a semicomplete
digraph.
Prom this we deduce a result about arctraceability.
Corollary 5.14. If D is a weakly connected (but not strongly connected) locally
semicomplete digraph, then D is arctraceable if and only if each strong compo
nent of D is an arctraceable semicomplete digraph and D*, the condensation of
D, is a directed path.
Once again, this is not quite a characterization, since it relies on a char
acterization of arctraceable semicomplete digraphs, but we do know a great
deal about the structure of nonarctraceable strong semicomplete digraphs from
Theorem 5.5.
In the case of strong locally semicomplete digraphs, we will focus on the
subclass known as round decomposable strong locally semicomplete digraphs.
A round decomposition is somewhat more general than the condensation of a
77
digraph. We will say a strong locally semicomplete digraph D has a round
decomposition if there is a round digraph R with order r and the vertices of D
can be partitioned into sets S\,... ,Sr in onetoone correspondence with the
vertices of R such that each Si is a strong semicomplete digraph and that every
vertex in Si dominates each vertex in Sj whenever the vertex corresponding to
Si dominates the vertex corresponding to Sj.
We note that not all such digraphs have a round decomposition (see [16]).
We will consider only those that do here. Round digraphs are certainly round
decomposable, as we can simply choose Si = {uj} for each vertex w*. We use the
techniques and arguments developed for round digraphs to give necessary and
sufficient conditions for an arc in this larger class of digraphs to be traceable.
Lemma 5.15. Let D be a strong round decomposable locally semicomplete
digraph and let Si,... Sr and R be a round decomposition of D. Then an
arc xy ; A(D) is nontraceable if and only if for some nontraceable arc
WiWj A(R), Si = {x} and Sj = {?/}.
Proof. Let D have the round decomposition specified in the theorem, and let
x e Si and y 6 Sj.
If i = j, let Hi be a hamiltonian path of the semicomplete digraph induced
on Si \ {x,y} and for k i, let Hk be a hamiltonian path of the semicomplete
digraph induced on Sk Then xyHi+iHi+2 HrH\H2 Hi is a hamiltonian
path of D that contains the arc xy.
If i j and Si ^ {x}, then let Hi be a hamiltonian path of Si \ {x} and
let Hj be a hamiltonian path of the strong semicomplete digraph induced on
Sj beginning at y. Now, for k ^ i,j let Hk be any hamiltonian path of Sk and
78
construct the hamiltonian path xHjHj+1 HTH\H2 H3_i of D containing
the arc xy. Similarly, if Si = {x}, but Sj {y}} we use a similar technique and
construct a hamiltonian path Hi+iHl+2 HnHi H^xy.
Thus, we can assume that Si = {x} and S3 {y}. It remains to show that
in this case, xy is traceable in D if and only if WiWj is traceable in R. Clearly,
if WiWj is traceable in R, the we can choose a hamiltonian path Hr containing
this arc and replace each vertex Wk of this path with a hamiltonian path
of Sk and obtain a hamiltonian path of D that contains xy. Conversely, just
as in the proof of Theorem 5.12, any hamiltonian path H of D containing xy
must contain an arc uv with u E Skx and v G Sk2 where one of &q, k2 is in the
set {j + 1, j + 2 ..., i 1} and the other is in the set {i + 1, i + 2,..., j 1}.
This forces the arc Wiiwi+i or the arc wJ^iWJ+\ in R and this arc is sufficient
to guarantee that WiWj is traceable in R by Theorem 5.12.
This gives us precisely the same characterization of arctraceable strong
round decomposable locally semicomplete digraphs that we obtained in the case
of round digraphs.
Theorem 5.16. Let D be a strong round decomposable locally semicomplete
digraph. Then D is arctraceable if and only if D {x, y} is traceable and D^yx)
has 8~ + > 0 for every xy A(D).
Proof. The result follows from Theorem 5.15 using the exact same argument
used in the proof in Theorem 5.13.
To complete an analysis of all arctraceable locally semicomplete digraphs,
such digraphs that are not round decomposable must be considered. This case
79
remains open.
Question. Characterize arctraceable locally semicomplete digraphs that are nei
ther semicomplete nor round decomposable.
5.4 Other Generalizations
In this last section we pose a series of questions that are related to arc
traceability in tournaments. We will suggest other classes of digraphs in which
arctraceability could be investigated, and we will consider properties similar
to arctraceability. For clarity, we will state each problem in the context of all
digraphs. Of course, many such questions could be asked. We present only a
small sample.
Perhaps the most obvious generalization of tournaments not already dis
cussed is the class of multipartite tournaments. A multipartite tournament is an
orientation of a complete multipartite graph.
Question. Characterize arctraceable multipartite tournaments.
Another possibility is to look at directed graphs which fall just short of
tournaments. For example, digraphs with at most ope pair of nonadjacent
vertices.
Question. Characterize arctraceable digraphs whose underlying graph is Kne.
Generalizing the idea of arctraceability itself, we arrive at a fundamental
question: Given any substructure S, what digraphs D have a hamiltonian path
containing S for each S in D1 We briefly consider a few choices for the structure
S.
80
Question. Characterize digraphs D that contain a hamiltonian path containing
S for each S in D where S is:
A path of length k, k > 2.
k vertex disjoint arcs, in any order.
An ordered set of k vertex disjoint arcs.
A linear forest with possibly additional restrictions.
We can also generalize the traceable part of arctraceable. Instead of
requiring a single, spanning path, we can seek digraphs with a linear factorization
containing the desired structure. Such a generalization may be necessary to make
significant progress on these stronger conditions, as there remain many open
questions even in the case of arctraceable digraphs. One might also consider
factorizations containing the given structure that consist of both paths and
cycles. Pathcycle factorizations of semicomplete multipartite digraphs have
been studied by BangJensen, Huang, Gutin and Yeo (for an overview of these
results, we suggest [6] and for specific references, [7] and [17]).
81
REFERENCES
[1] B. Alspach. Cycles of each length in regular tournaments. Canad. Math.
Bull., 10:283286, 1967.
[2] K. T. Balinska, M. L. Gargano, and L. V. Quintas. An edge partition
problem concerning hamilton paths. Congressus Numerantium, 152:4554,
2001.
[3] K. T. Balinska, M. L. Gargano, L. V. Quintas, and K. T. Zwierzyhski.
Graphs with nontraceable edges. Computer Science Center Report 485,
The Techinical University of Poznan, 2002.
[4] K. T. Balinska, M. L. Gargano, L. V. Quintas, and K. T. Zwierzyhski.
Extremal size problems for graphs with nontraceable edges. Congressus
Numerantium, 162:5564, 2003.
[5] J. BangJensen. Locally semicomplete digraphs: a generalization of tour
naments. J. Graph Theory, 14:371390, 1990.
[6] J. BangJensen and G Gutin. Digraphs: Theory, Algorithms and Applica
tions. SpringerVerlag, 2001.
[7] J. BangJensen, G. Gutin, and J. Huang. A sufficient condition for a semi
complete multipartite digraph to be hamiltonian. Discrete Math., 161:112,
1996.
[8] M.F. Bridgland and K.B. Reid. Stability of kings in tournaments. In
Progress in graph theory (Waterloo, Ont. 1982), pages 117128. Academic
Press, 1984
[9] R. A. Brualdi and Q. Li. The interchange graph of tournaments with the
same score vector. In Proceeding in graph theory (Waterloo, Ont., 1982),
pages 129151. Academic Press, 1984.
[10] G. Chartrand and L. Lesniak. Graphs and Digraphs. Chapman and Hall,
1996.
[11] G. A. Dirac. Some theorems on abstract graphs. Proc. London Math. Soc.,
2:6981, 1952.
82
[12] J.D. Foulkes. Directed graphs and assembly schedules. In Proc. Symp.
Appl. Math., pages 218289. Amer. Math. Soc., 1960.
[13] A. GhouliaHouri. Une condition suffisante dexistence dun circuit hamil
tonien. C. R. Adac. Sci. Paris, 156:495497, 1960.
[14] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic
Press, 1980.
[15] R.J. Gould. Advances on the hamiltonian problem a survey. Graphs
Combm., 1:752, 2003.
[16] Y. Guo. Strongly Hamiltonianconnected locally semicomplete digraphs.
PhD thesis, RWTH Aachen, 1995.
[17] G. Gutin and A. Yeo. Note on the path covering number of a semicomplete
multipartite digraph. J. Combin. Math, and Combin. Computing, 32:231
237, 2000.
[18] F. Harary and L. Moser. The theory of round robin tournaments. Amer.
Math. Monthly, 73:231246, 1966.
[19] J. Huang. On the structure of local tournaments. J. Combin. Theory Ser.
B, 63:200221, 1995.
[20] J. Huang. Which digraphs are round? Australas. J. Combin., 19:203208,
1999.
[21] O. S. Jakobsen. Cycles and Paths in Tournaments. PhD thesis, University
of Aarhus, 1972.
[22] T. Koshy. Fibonacci and Lucas Numbers with Applications. John Wiley
and Sons, 2001.
[23] H.G. Landau. On dominance relations and the structure of animal societies,
iii: The condition for score structure. Bull. Math. Biophys., 15:143148,
1953.
[24] J. R. Lundgren and D. J. Siewart. Boolean rank of upset tournament
matrices. Manuscript.
[25] K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:95115, 1927.
[26] H. Meyniel. Une condition suffisante dexistence dun circuit hamiltonien
dans un graph oriente. J. Combin. Theory Ser. B, 14:137147, 1973.
83
[27] J. W. Moon. Topics in Tournaments. Holt, Rinehart and Winston, 1968.
[28] J. W. Moon. The minimum number of spanning paths in a strong tourna
ment. Publ. Math. Debrecen, 19:101104, 1972.
[29] J.W. Moon. On subtournaments of a tournament. Canad. Math. Bull.,
9:297301, 1966.
[30] 0. Ore. Note on hamiltonian circuits. Amer. Math. Monthly, 67:55, 1960.
[31] J. L. Poet and B. L. Shader. Score certificate numbers of upset tourna
ments. Discrete Applied Mathematics, 103:177189, 2000.
[32] L. Redei. Ein kombinatorischer satz. Acta Litt. Szeged, 7:3943, 1934.
[33] K. B. Reid. Tournaments. In J.L. Gross and J. Yellen, editors, The Hand
book of Graph Theory, pages 156184. CRC Press, 2004.
[34] K.B. Reid. Prive communication.
[35] K.B. Reid. Tournaments with prescribed numbers of kings and serfs.
Congr. Numer., 29:809826, 1980. Proceedings of the Eleventh Southeast
ern Conference on Comibinatorics, Graph Theory and Computing (Florida
Atlantic Univ., Boca Raton, FL, 1980), Vol. II.
[36] F, S Robers. Discrete Mathematical Models. Prentice Hall, 1976.
[37] N. J. A. Sloane. The online encyclopedia of integer sequences, published
electronically at http://www.research.att.com/ njas/sequences/. A000213.
[38] C. Thomassen. Hamiltonianconnected tournaments. J. Combin. Thoery
Ser. B, 28:142163, 1980.
[39] C. Thomassen. On the number of hamiltonian cycles in tournaments. Dis
crete Math., 31:315323, 1980.
[40] C. Thomassen. Edgedisjoint hamiltonian paths and cycles in tournaments.
Proc. London Math. Soc. (3), 45:151168, 1982.
[41] F. Tian, Z.S. Wu, and C.Q. Zhang. Cycles of each length in tournaments.
J. Combin. Theory Ser. B, 33:245255, 1982.
[42] L. Volkmann. Longest paths through an arc in strong semicomplete multi
partite digraphs. Discrete Math., 258:331337, 2002.
84
[43] D.R. Woodall. Sufficient conditions for circuits in graphs. Proc. Load.
Math. Soc., 24:739755, 1972.

Full Text 
PAGE 1
ARCTRACEABLE TOURNAMENTS by Arthur H. Busch Bachelor of Arts University of Washington 1997 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the r e quirem e nts for the degree of Doctor of Philosophy Applied Mathematics 2005
PAGE 2
This thesis for the Doctor of Philosophy degree by Arthur H. Busch has been approved K.B. Reid Ellen Gethner .:1 Apr; I .nos Date
PAGE 3
Busch Arthur H. (Ph.D., Applied Mathematics) Arctraceable Tournaments Thesis directed by Professor Michael S. Jacobson ABSTRACT A tournament T is arctraceable when each arc of the tournament i s a part of a hamiltonian path. We characterize arctraceab l e upset tournaments and show that this property is independent of the number of hamiltonian paths in such tournaments. We show that nonarctraceable tournaments have a specific structure, and give several sufficient conditions for strong tournaments to be arc traceable, including Diraclike minimum degree conditions, Orelike conditions and irregularity conditions. In each case, we show that the r es ult is best possible. Next, we give some extremal results for arctraceable tournaments, bounding the number of arcs in a tournament that are not part of any hamiltonian path, and finding the minimum number of vertices in a karc strong tournament that is not arctraceable Finally we also consider the arctraceable property in two other classes of digraphs se micomplete digraphs and local tournaments, both of which share many properties with tournaments. lll
PAGE 4
This abstract accurately repr e s e nts the c ontent of the candid ate's thesis. I recommend its publication IV
PAGE 5
DEDICATION I wou ld lik e to dedicate this diss ertation to m y p a rents. The ir encouragement and support h as been unw ave ring an d the ir patience almost unlimit ed.
PAGE 6
ACKNOWLEDGMENT First and foremost, I would like to thank my advisor, Mike Jacobson. I would lik e to think that my frequent interruptions of his work were usually a welcome distraction, but they were certainly a distraction. I am grateful for the time he has spent with me on this thesis and on other projects that have collectively made me a much better mathematician. In addition, I want to thank both Rich Lundgren and to Bill Cherowitzo who encouraged and mentored me early in my graduate studies and knew long before I did that my education would culminate in a Ph. D Bill in particular, deserves credit for trying his best to turn me into a geometer. Ultimately unsuccessful I learn e d a great deal in the process.
PAGE 7
CONTENTS Figures ............. 1. Introduction and background 1.1 Prologue 1. 2 Background 2. Paths and cycles in tournaments 2.1 Cycles in tournaments 2.2 Paths in tournaments 3. Upset tournaments ... 3.1 Arctraceable upset tournaments 3 2 Counting Hamiltonian Paths in Upset Tourna ments 4. Arctraceability in all strong tournaments . 4 1 Observations on arctraceability in tournaments 4.2 The structure of nonarctraceable tourname nts 4.3 Applications of the structure results ... ... 4.4 Extremal r es ults r elated to arctraceable tournaments 5. Related problems .... 5.1 Semicomplete digraphs 5.2 Round digraphs .... 5.3 Locally semicomplete digraphs 5.4 Other Generalizations R e ferences . . vii Vlli 1 1 3 14 14 17 21 23 28 39 39 45 51 55 67 67 71 77 80 82
PAGE 8
FIGURES Figure 1.1 A digraph and two subdigraphs, one induced. 1.2 A hamiltonian digraph ..... 1.3 A tournament with eight vertices. A simplified r e presentation of a tournament A strong tournament that is not arcpancyclic 4 6 9 13 16 1.4 2 1 2.2 2.3 The two famili es of arc3cyclic tournaments that are not a r cpancy clic. 16 A hamiltoni a n digraph that is not arctraceable. 18 3.1 An 11tournament with 10 nontrace a bl e a rc s 3.2 Two 8tournaments . 4 1 An arctraceable tournament. 4 2 A tournament with nontraceable a r c xy a nd two arcdisjoint p at hs from y to x .................. . .... 5 1 Two nonarctraceable strong semicomplete digraphs 5.2 A round loc a l tournament with cycles of l e ngth two. 5.3 A strong nonarctrac ea ble round digraph ..... viii 26 34 47 60 70 72 76
PAGE 9
1. Introduction and background 1.1 Prologue Questions relating to paths and cycles in graphs and digraphs have been studied extensively from a variety of perspectives. One of the most popular questions in undirected graphs relates to determining the class of graphs that contain a hamiltonian path or cycle. This basic question has been generalized and specialized in many ways which has led to a number of deep and interesting results (for a survey of such results, see [15]). Our particular interest is a property of digraphs we call arctraceable ; an arctraceable digraph is one in which every arc is part of a path that includes every vertex, i.e., a hamiltonian path. This question seems more difficult than the related question for undirected graphs studied by Baliri.ska Zwierzyri.ski Gargano and Quintas ([2], [3] and [4]). As a result, we investigate arctraceability in the subclass of digraphs known as tournaments. Tournaments have additional structure that, in many cases can be shown to guarantee arctraceability. We use this additional structure to investigate tournaments that are not arctraceable. In the next section, we provide some brief background material with an emphasis on terminology and classical results related to digraphs and tourna ments. In Chapter 2, we review some more recent results specifically relating to paths and cycles in digraphs and tournaments, and we develop a necessary condition for a digraph to be arctraceable. This necessary condition is used to show that the study of arctraceable tournaments can be restricted to studying arctraceable strong tournaments. 1
PAGE 10
Initially, we consider the question in the context of a subclass of strong tournaments known as upset tournaments, and in Chapter 3 we give a charac terization of arctraceable upset tournaments. We use this characterization to produce examples of tournaments that have many arcs that are not part of any hamiltonian path (such arcs will be called nontraceable). W e a lso develop some techniques to demonstrate that arctraceability is independent of the number of hamiltonian paths in upset tournaments. In other words, arctraceability in a tournament is not merely a consequence of having many hamiltonian paths. In Chapter 4, we broaden the investigation of arctraceability to all strong tournaments. We begin with some simple observations about sufficient condi tions for a strong tournament to be arctraceable. From these basic observa tions, we then develop some necessary conditions for a strong tournament to be nonarctraceable. These conditions, in turn, yield many new and improved suf ficient conditions for arctraceable tournaments, and a structure that we use to construct minimal nonarctraceable tournaments with many arcdisjoint paths between every pair of vertices. We also use the structure of nonarctraceable tournaments to determine the maximal number of nontraceable arcs in a strong ntournament. In Chapter 5, we briefly consider arctraceability for digraphs in general. We investigate arctraceability in two classes of digraphs that include tournametns, semicomplete digraphs and local tournaments. We also briefly consider some questions closely related to arctraceability in tournaments and these super classes of tournaments. The structure d eve loped in Chapter 4 features promi nently in these questions and we give examples that show how related structures 2
PAGE 11
occur in these contexts. These related questions suggest several directions for future research. 1.2 Background We begin with some of the fundamental results related to directed graphs in general and tournaments in particular. We assume the reader is familiar with the study of undirected graphs and suggest [10] as both a general resource and for more detailed background on the following results for digraphs and [33] as a resource for more information on tournaments. A digraph D = (V, A) consists of a set V called vertices and a collection A of ordered pairs of elements from V called arcs. Just as in the case of undirected graphs the order of D is the number of vertices in V and the size of a digraph is the number of arcs in A. Typically, the study of digraphs is restricted to those digraphs in which vv tf:. A for every v E V and there is at most one copy of each of the remaining ordered pairs. Such a digraph is called strict, and when D is a strict digraph, the collection of arcs is more commonly referred to as a set. Strict digraphs are in a sense analogous to simple undirected graphs; graphs with no loops and at most one edge joining each pair of vertices. Unless specifically stated otherwise, we will assume that all digraphs are strict. For convenience, we often simply write uv to represent the arc ( u, v), and we will say that u dominates v and write u + v when ( u, v) is an arc of D A subdigraph of a digraph D = (V, A) is a digraph D' = (S, T) where both S V and T For a set S c V, we define the induced subdigraph D [ S] as the digraph with vertex set S and arc set T = { ( u, v) I ( u, v) E A and u, v E S}. In other words, the arcs of an induced subdigraph include all arcs that join two vertices in S. In 3
PAGE 12
g d f a b c g d e f ,pl CJ a b c a Figure 1.1: A digraph and two subdigraphs, on e induced Figure 1.1, we show an example of a strict digraph along with two subdigr a phs. The subdigraph on the right is induced while the s ubdigraph on the left i s not ; it includes the vertices c a nd d but not the arc from c to d. The outneighborhood of a vertex v is the s e t { u I vu E A} and is d e not e d Nfj ( v ) or N+ ( v ) when the cont ext i s clear. Similarly N ( v ) = { u I uv E A}. The outd e gree ( d+ ( v)) and ind e gree ( d( v )) are defin e d as IN+ ( v ) I and IN ( v) I, respectively Similar to graphs we then let + (b) b e the smallest out degree (indegree) and + ( be the largest outdegree (ind e gr ee) am on g all the vertices of D. Additionally we s e t <5 = min( +, b) and 0 = Whe n we are working with more than on e digr aph, w e will us e the not a tion b0(D), for example, to clarify the digraph to whi c h we are r e f e rring. A path in a digraph is a sequ e n ce of distin c t v e rtices v1v2 ... v k su c h t h a t viviH E A for e a c h i, 1 :S: i < k. If in a ddition vkv 1 E A the n the sequ e nce is a 4
PAGE 13
cycle. The order of a path or cycle is the number of vertices in the sequence, and the length is the number of arcs. Thus, a path of length l has order l1, while a cycle of length l also has order l. Note, just as for graphs, any consecutive subsequence of the vertices of a path or cycle is also a path. Conversely, we will frequently want to combine two or more paths into larger paths. If P = v1v2 ... Vk and Q = u1u2 ... Um are vertex disjoint paths, and vku1 E A, then we will denote the combined path v1 ... VkU! Um simply as PQ. A digraph D which contains no cycles is called acyclic. Of particular interest is a path or cycle containing all the vertices of D i.e. a hamiltonian path or cycle. Just as for graphs a digraph containing a hamiltonian cycle will be called hamiltonian and a digraph containing a hamiltonian path will be called traceable (of course, every hamiltonian digraph is traceable but not conversely). Figure 1.2 shows a digraph that is hamiltonian, with a hamiltonian cycle highlighted by dashed arcs. For undirected graphs, hamiltonian paths and cycles have been studied ex tensively. Two classic, early results are due to Dirac and Ore. Theorem A (Dirac (11]). If G is a simple graph with at least three vertices and 6 (G) 2: then G is hamiltonian. Theorem B (Ore (30)). Let G be a simple graph. If d(u) + d(v) 2: n for every pair of distinct nonadjacent vertices u and v ) then G is hamiltonian. W e note that for strict digraphs, an analogue of Theorem A was given by GhouilaHouri. Theorem C (Ghoil
PAGE 14
I I I I I v u Figure 1.2: A hamiltonian digraph Similarly, Theorem B has been generalized to strict digraphs by Woodall [43]. Meyniel improved both of these results with the following : Theorem D (Meyniel (26]). If D is a strongly connected strict digraph and d+(u) + d(u) + d+(v) + d(v) 2n1 for every pair of vertices u and v such that neither uv E A(D) nor vuE A(D), then D is hamiltonian. A digraph is strongly connected or simply strong when for every pair of distinct vertices u and v there exists both a path from u to v and a path from v to u. Note, a single vertex digraph is always strong. As such for any digr ap h D each vertex is contained in a strongly connected induced subdigraph of D. When such a strong induced subdigraph is maximal, it is called a strong component of D, and it is easy to see that these strong components must, in fact, partition V. We then define a new digraph D*, called the con densation of D by letting V(D*) be the set of strong components of D and A(D*) = { D i D j I uv E A for some u E Di, v E Dj with i i= j}. Again, it is easy to see that D is an acycl i c digraph. For more information about the condensation of a digraph, see [36]. 6
PAGE 15
In a strong digraph D if the indu ced s ubdigraph D[S] i s not stro ngly con n ecte d for some S C V, then V \ S is called a cutset of D When D[SJ i s s trong for all sets S with [S[ [V[(d1), we say that Dis dconnected and we define K,(D) to b e the smallest d such that D is dconne c ted. Analogously, if D' = (V, T) is not strongly connected for some T C A then A \ T is called an arc cutset, and we d e fine /'i,'(D) as the s mallest k such that D' = (V, T) is not strong for some T C A with [T[ = [AI k We then we say that D is karcconnected or karcstrong when eve r k::; K,1(D). The digraph in Figure 1.2 is 2arcstrong; both the solid arcs and the dashed arcs form hamiltonian cycles, so removing any s ingl e arc still leaves a path between any two vertices. Note, this digraph is not 2 co nnected however s in ce removing the vertex x leaves no path from u to v. When two distinct nonadjacent v e rtic es x and y are specified, an x, yseparatingset is a set S of vertices such that every path from x to y contains at least one vertex of S. Similarly an x, yseparatingset of a r cs is a set T of arcs such that every path from x to y contains at least one a rc of T (in this case, we need not require that x and y be nonadjacent). In both cases, it is easy to see that wh e n there exist m paths from x to y that are internally vertex disjoint (arcdisjoint) then the set S (T) must contain at least one vertex (arc) from each path. The converse also holds in both cases, a r es ult referred to as Menger's Theorem. Menger's Theorem i s stated in a wide variety of ways, both for graphs and digraphs. We give two variations here. Theorem E (Menger [25]). Let D be a digraph and let x and y be distinct nonadjacent vertices of D. The number of internally vertex disjoint paths from 7
PAGE 16
x to y equals the size of the smallest x, yseparating set. Similarly, for any distinct (possibly adjacent) vertices x andy, the number of arcdisjoint paths from x to y equals the size of th e smallest x, yseparating set of arcs. Our main focus will be on a special class of digraphs called tournaments. A tournament is a directed graph D such that for any two distinct vertices u and v, either uv E A(D) or vu E A(D) but not both. Typically a tourna ment is denoted by T rather than D, and we will say T is an ntournament when IV(T)I = n It is often helpful to think of an ntournament as an orientation of the complete graph Kn. From this perspective, it is immediate that a tournament has no selfloops or cycles of length two. It is also clear that IA(T)I = IE(Kn)l =G) and that N(v) and N+(v ) partition the s e t V(T)\ { v } regardless of our choice of v. This also shows that d+ ( v) + d( v) = n 1 for every vertex v. In accordance with the name tournament, we will often refer to d+ ( v) as the score of the vertex v. We illustrate an 8tournament in Figure 1.3. Clearly drawing even relatively small tournaments is imprac tical due to the large number of arcs It is also apparent, by considering the tournament as an orientation of a complete graph, that any induced subdigraph of an ntournament is also a tour nament. We simply refer to such an induced subdigraph as a subtournament, and for the set U C V(T) we denote the subtournament on the set U by T[U}. When U = V(T)\S for some subs etS, we simply write TS instead ofT[V\S]. If S = { v }, then we will abbreviate notation further and refer to T { v} a s T v For any two subsets A and B of V(T), there are exactly !AliBI arcs between these two sets When uv is an arc of T for every u E A and v E B we will 8
PAGE 17
Figure 1.3: A tournament with eight vertices. say A dominates B Note, just as the tournament as a whole can be viewed as an orientation of the complete graph, the arcs between the sets A and B can be viewed as an orientation of the complete bipartite graph KIAI,IBI When A dominates B then this orientation is such that the arcs between A and B always originate in A and terminate in B. In addition to the traditional measures of inand outdegrees in a tourna ment such as c)+, c5and 6, we also measure the irregularity of a tournament, denoted i(T) and defined as maxvEV ld+(v)d(v)l. From this definition, we see that i(T) = 0 if and only if every vertex has equal inand outdegree and all of these values must then be exactly n2l (and hence n must be odd). Such a tournament is called regular. When n is even i(T) 2:: 1 and in the case of equality, the vertices have outdegree either or 1. Such tournaments are ca lled nearregular or almostregular. Proposition 1.1. i(T) = n12c5 Proof. If ld+ ( v)d( v) I > n126 for some v E V then we must have either 9
PAGE 18
d+(v) d(v) > n126 or d(v)d+(v) > n126. Substituting in d+(v) + d(v) for n1 into both equations and simplifying, we obtain either d(v) < 6 or d+(v) < 6, a contradiction Thus, i(T) n1 26. To compl ete the proof note that 2: max ( ( n 1 6 ) 6, 6+ ( n 1 6 +)) 2: max(n 126,n 126+) 0 For any tournament T = (V, A) we ca n orde r the v er tice s v 1 v2, ... Vn in 1 i n, this ordering gives a nondecr eas ing se quenc e S = s 1 s2, s3, ... sn of length n. This s eque nce is called the score seque nce of the tourname nt T. It i s clear that S i = JAJ = (;) since eac h arc is counte d exact l y onc e in the sequence. Also the subset vk = {VI' V2' ... 'Vk} induces a subtourna ment for eac h k < n, so we also must have si 2: JA(T[Vk])J = for eac h k < n. Landau [23] showed that these necess a ry conditions are also sufficient. Thus a n y nondecreasing sequenceS= s1 s2 Sn s u c h that ts, 2: G) f o r each k l S k < n 10
PAGE 19
and tsi = (;) t=l is the score sequence for some tournament T. A tournament is transitive if A(T) induces a transitive (and hence acyclic) relation on the set V (T). Furthermore, since A(T) is antisymmetric and every pair of vertices is joined by an arc, every pair of vertices is comparable under this transitive relation and thus gives a total ordering of the set V(T). If V(T) = { v1 ... vn}, with the subscripts corresponding to this order, then vivj E A(T) if and only if i > j and hence d+(vi) = i 1 (or, of course, v ivj E A(T) if and only if i < j, in which case d(vi) = i1; we generally prefer the former ord e ring) It is well known ( c.f. [36]) that a tournament is transitive if and only if it is acyclic. Note, if a tournament T is strongly connected, the condensation digraph T* consists of a single vertex, which is trivially transitive. If T is not strongly connected, then because Tis an orientation of the complete graph, the underlying graph of T* is also complete, and so T* is also a tournament. Furthermore, T* is by definition acyclic, and hence T* is a transitive tournament. If T = (V, A), for any B A, we can form a new tournament T' by "reversing" the arcs of B. More specifically, let B = { uv J vu E B}, then T' = (V, (A\ B) U B). Two special cases are of particular interest. First, when B = A, we will call T' the reversal ofT and denote this tournament T. Note paths and cycles in T are also paths and cycles in T. The second special case is when the T' obtained is a transitive tournament, and in this case we can use the transitive ordering of V(T') on V(T) as well. Using this ordering in which 11
PAGE 20
vivj is an arc ofT' whenever i > j B is precisely the set or arcs vivj in T such that i < j and the arcs of B are sometimes referred to as the upset arcs of the tournament. Using this idea, we develop a simplified way to draw a tournament. We place the vertices in a linear order, and make the arc from u to v implicit if u comes after v in this ordering. In other words, we only draw the arcs of B. Figure 1.4 uses this technique to represent the same tournament shown in Figure 1.3. In all subsequent figures, we will use this technique to drawn tournaments as well as similar digraphs. In some cases, we may also draw a small number of the nonupset arcs when these arcs are of particular int e rest (to highlight nontraceable arcs, for example). Note, each ordering of V(T) determines a set of upset arcs B and if we choose the ordering badly, the set B can be large which minimizes the advantage of drawing only the upset arcs. We will avoid such orderings. Further simplifying our figures, we will use a similar technique for the condensation of tournaments that are not strong; we will represent the nontrivial components of the tournament with large circles or ellipses, often without specifying the internal structure of these strong components. Further more, using a toptobottom or lefttoright ordering of these components, we need not draw in any arcs at all as the condensation is a transitive tournament. Finally we will sometimes wish to illustrate most of the arcs of a tournament, but leave the direction of one or more a rcs unspecified. We will indicate such unspecified arcs with a dashed line. When V(T) has some ordering such that the set B = { vivj I i < j} is the arc set of a path U from v1 to Vn, T is called an upset tournament and the path U is called the upset path of T. Since reversing the arcs of any path 12
PAGE 21
Figure 1.4: A simplified representation of a tournament l eaves the degrees of the int e rior vertices unchanged d:j (vi) = d:j, (vi) = i 1 for each i, 2 ::; i ::; n1. Similarly d:j(v1 ) = d:j,(vi) + 1 = 0 + 1 = 1 and d:j(vn) = d:j,(vn) 1 = n1 1 = n2. Thus, an upset tournament has score sequence 1 1 2, ... n 3 n 2 n 2. Brualdi and Li [9] showed the converse of this result i s a lso true; that any tournament with this sore seq uence is an upset tournament. The tournament in Figures 1.3 and 1.4 is an exa mpl e of an upset tournament. These two figures also show the advantage of using our simplified representation in the cas e of upset tournaments; it is easy to see that the tournament in Figure 1.4 is an up set tournament, but this is f a r from clear by looking at the same tournament in Figure 1.3 with all t he a rcs drawn. Upset tournaments form a very natural subclass of tournaments, because they are very nearl y hereditary. While it is not true that every subtournament of an upset tournament is itself an upset tournament, it turns out that every nontrivial strong component of such a s ubtournament is an upset to urn a ment. In particular, every strong subtournament of an upset tournament i s an upset tournament. 13
PAGE 22
2. Paths and cycles in tournaments The study of hamiltonian paths and cycles in tournaments began with the very early result of Redei. Theorem F (Redei [32]). Every tournament is traceable. Similarly strong tournaments wer e shown to b e hamiltonian ind e p en dently by Foulks and by Harary and Moser (this is also implied by Theorem D). Theorem G (Foulkes [12] and Harary and Moser [18]). Ev ery strong tournament is hamiltonian As a result the investigation of hamiltonian paths and cycles in tournaments focuses on stronger conditions than the existence of at least one hamiltonian path or cycle. We survey a few of these stronger conditions, beginning with results for cycles in tournaments, and then turning our attention to paths. 2.1 Cycles in tournaments One of the first results generalizing hamiltonicity in tournaments is due to Moon. He showed that every strongly connected tournament has a property he called vertexpancyclic. Theorem H (Moon [29]). If T is a strong tournament, and v is any vertex ofT, then v is in a cycle of length k for 3 ::; k ::; n. We note that a similar property do es not hold for the arcs of a strong tournament. Consider the tournament with six vertices shown in Figure 2.1. R e versing 14
PAGE 23
the arc a from the bottom vertex to the top vertex gives a tournament T' with two strong components, each of order three. Any cycle of this tournament that does not use the arc a is also a cycle of T' and hence has order at most three Since no cycle can contain both a and either of the other upset arcs shown, these upset arcs can not be on any cycle of length four or more. A natural question arises; what conditions on a tournament guarantee that every arc is on a cycle of all possible lengths? We will call tournaments in which every arc is contained in a cycle of length exactly k arckcyclic, and if a tournament is arckcyclic for each possible k (in othe r words for 3 :S k :S n), then the tournament is called arcpancyclic. In the special case where k = n, we will say a tournament is archamiltonian rather than arcncyclic. Alspach [1] initially showed that every regular tournament is arcpancyclic. Jakobsen [21] studied nearregular tournaments and found that whil e not necessarily arc pancyclic, for n 2: 8, such tournaments are arckcyclic for each k 4 :S k :S n. In 1980, Thomassen [38] showed that every 3conn ected tournament is arc pancyclic and that there are infinitely many 2connected tournaments that are not archamiltonian (and hence, not arcpan cyclic). Thomassen was also able to give a sufficient condition for almost arcpancyclic tournaments based on irregularity. Theorem I. Thomassen {38} IJT is anntournament with i(T) :S n53 then T is k arccyclic for 4 :S k :S n As regular and nearregular tournament have irregularity zero and one, re spectively, this result implies (along with the simple observation that for regular tournaments, each arc is in a cycle of l ength three) the results of both Alspach 15
PAGE 24
Figure 2.1: A strong tournament that is not arcpancyclic Figure 2.2: The two families of arc3cyclic tournaments that are not arcpancy clic. and Jakobsen. For k = 3, Moon [27] was able to show that nearly all tournaments are arc3cyclic. This last result was then used by Tian, Wu and Zhang to aid in c haracterizing arcpancyclic tournaments. They showed the following: Theorem J (Tian, Wu and Zhang (41]). An arc3cyclic tournam ent is arcpancyclic unless it belongs to on e of th e fam i lie s D6 or D8 shown in F i gur e 2.2 From this result one can deduce the above r es ults of Thomasse n a nd h e nce also of Jakobsen and Al s pach 16
PAGE 25
2.2 Paths in tournaments Properties related to similar generalizations of traceability in tournaments are not as well studied. The work of Redei [32] showed that not only does every tournament have a hamiltonian path, but that every tournament has an odd number of such paths. Further, it is a simple exercise ( cf. [36]) to demonstrate that a tournament has a unique hamiltonian path if and only if it is acyclic (or equivalently, is transitive). The number of distinct hamiltonian paths in a tournament has been studied, and it has been shown by Moon [28] that for strong tournaments, the number of such paths grows exponentially with n. For nonstrong tournaments, the number of distinct hamiltonian paths is simply the product of the number of hamiltonian paths in each strong component. The question of which arcs in a digraph can be extended to a hamiltonian path was first suggested by Balinska, Gargano and Quintas [2] in a paper analyz ing the analogous concept in undirected graphs. We use the term arctraceable to describe digraphs with this property. In this undirected context, it was shown that every hamiltonian graph is edgetraceable (called totallytraceable in [2], [3] and [4]). Since hamiltonian graphs are extensively studied, this gives a great deal of information about edgetraceable graphs. In the directed case, examples abound which show that hamiltonicity is not sufficient to guarantee arctraceability. One such example is shown in Figure 2.3. The lack of a well known sufficient condition for a digraph to be arctraceable would seem to make the problem significantly more difficult than in the undi rected case. Apart from some very special cases mentioned in [2], we note the following necessary condition. 17
PAGE 26
. < / Figure 2.3: A hamiltonian digraph that is not arctraceable. Theorem 2.1. If D is an arctraceable digraph, then D*, the condensation of D is a path. Proof. Let D be an arctraceable digraph Assume D has m strong components and let D* be the condensation of D. If Dis traceable D* must a lso be tracea ble. So, it suffices to show that when D is arctraceable then D is a n oriented tree, as the only traceable oriented tree is a path. We establish this by showing that the underlying graph of D* is acyclic. Since D* is acyclic, it contains some vertex of indegr ee 0. Label such a vertex viNow D* { vn is also acyclic and so this subgraph also has at least one vertex of indegree 0. Choose such a vertex and label it v2. Proceeding inductively, we can label all the vertices of D* as vi, v2, ... v:n such that vP has indegree 0 in D* {v1 .. Vpd Thus, for any p > q, v;v; tt A(D*) This well known ord e ring is known as a topological sorting by Golumbi c [14] and an acyclic ordering by BangJensen and Cutin [6]. W e use this same ord e ring for the strong components of D: D1 ... Dm so that v; corresponds to compon ent D;. Now, assume that C is a cycle of the underlying graph of D*. Choo se the 18
PAGE 27
smallest index i such that v; is on C, and let vj and v'k be the neighbors of v; on this cycle. By the minimality of i we have i < j and i < k, and without loss of generality we can assume that j < k. Since v;vz E E(C), the acyclic ordering requires that we must have v;vz E A(D*). This in turn requires that there are distinct vertices x andy in Di and Dk respectively such that xy E A(D). Now choose any vertex z in D j. Since Dis arctraceable, xy is on some hamiltonian path of D, and z must precede x or follow y on such a path, and so there must be either a path in D from z to x or a path in D from y to z. But clearly, any such path must contain an arc uv where u E DP and v E Dq with p > q. This requires that E A(D*), a contradiction. Hence, the underlying graph of D* must be acyclic. 0 Unfortunately, this necessary condition gives no information about strong digraphs, as the condensation of such a digraph is an isolated vertex, which is trivially a path. Recently, Reid [34] began to study arctraceable tournaments. Attempting to find conditions that are necessary and sufficient for a tournament to be arc traceable and several related questions is the primary focus of this dissertation. The necessary condition given above, along with the observation made ear lier that the condensation of a tournament is a transitive tournament implies the following corollary. Corollary 2.2. If a tournament T zs arctraceable, then T has at most two strong components. 19
PAGE 28
As noted above, our n eces sary condition for digraphs gives no inform a tion about which strong tournaments are arctraceable. However, w e can us e the hamiltonicity of strong tournaments to observe that the analysis of a r ctracea ble tournaments reduces to the study of arctraceable strong tournaments. Corollary 2.3. A tournament T with two strong components is arctraceable if and only if the subtournaments induc e d by th e strong compon e nts are arc traceable. Proof. Let T1 and T2 be the subtournaments induced by the strong components ofT, and let every vertex of T1 dominat e each vertex in T2 Now, eve ry hamil tonian path ofT must be of the form P1P2 with P ; a hamiltonian path ofT;, for i = 1, 2. So, if T; is not arctraceable for i = 1 or i = 2, then there is some arc that is not part of any hamiltonian path ofT. Conversely, if both T1 and T2 are arctraceable then each arc within these subtournaments is also traceable in T. To co nclude that T is arctraceable, we must show that the remaining arcs are also traceable. Each of these arcs is of the form xy with x E V(T1 ) and y E V(T2). We use the hamiltonicity of each of these subtournaments to construct a hamiltonian path Pt of T1 that en ds at x and a hamiltonian path P2 of T2 that begins at y. Consequently P1g is a hamiltonian path ofT containing xy, completing the proof. 0 Thus, if we are able to obtain even partial results in the case of strong tournaments, these results will have simple extensions to all tournam e nts. 20
PAGE 29
3. Upset tournaments We begin by studying the class of upset tournaments. As noted in Chapter 1 these are precisely the set of tournaments obtained from transitive tournaments by reversing the arcs of any singl e path from the source (i.e., vertex of indegree zero) to the sink (i.e. vertex of outdegree zero). This reversed path is referred to as the upset path. Reversing the arcs of a path leaves the scores of the vertices on the interior of the path unchanged, and the initial and terminal vertices of the path have their scores decreased and increased by one respectively. If we begin with a transitive ntournament, this yields a tournament with score sequence (1, 1, 2, 3, ... n3, n2, n2). We note that an identical argument indicates that reversing any path from a vertex of outdegree one to a vertex of indegree one in an upset tournament T yields a transitive tournament. This would seem to indicate that the upset path of an upset tournament may not be unique. To see that the upset path is n e ver unique, let u and u' be the vertices of an upset tournament with outdegree one and let v and v' be vertices with indegree one. Without loss of generality, assume that u dominates u' and v dominates v'. Thus, any path that originates at u must begin with the arc uu', and any path that terminates at v' must end with the arc vv'. So, if U is an upset path of the tournament that originates at u, then U u is a path from u' to a vertex of indegre e one and this shorter path is also an upset path. Similarly, if U terminates at v', then U v' is an upset path that terminates at v. On the other hand, if U is an upset path that 21
PAGE 30
originates at u', then u cannot be a vertex of U since u i s not the terminal vertex of U and the onl y vertex that can follow u on a path i s u'. In this case, uU is a l s o a n upset path of the tournament, and duall y if U is a n upset path ending at v, then Uv' is also an upset path. To address the above ambiguity we can r eq uir e that our upset path U conta in the a r cs uu' and vv' or, alternately, we can forbid the inclusion of these arcs. The former approach is used in [31] and [24], a mong othe rs. In general we pre f e r the latter approach; we require that U be as short as possible. However if there is a hamiltonian path from a vertex of outdegree one to a vertex of indegre e one, it is oft e n convenient to choose this hamiltonian path as U. W e pres ent a result of Brualdi and Li [9] showing that upse t tournaments a r e c h a racterized b y their score se quen ce. The ir proof u ses the adjace nc y matrices o f upset tournaments. To illustrate the powerful inductive nature of this cl ass of tournaments, we present an alternate proof. Theorem 3.1 (Brualdi and Li [9]). L e t n 2: 4. Anntournament T is an upset tournament if and only if the score sequence ofT is (1, 1 2, 3 n 3, n2, n2). Proof. Necessity follows by the argument above; that the reversal of the arcs of a path of the transitive tournament from source to sink leaves the scores of the vertices on the interior of the path unchanged, decreases the score of the sour ce by 1 and in c reases the score of the s ink by 1. This produces a tournament with the d es ired score sequence. For sufficiency w e use induction. For n = 4 the tournament with score se quence (1, 1 2 2) is uniqu e and it is easily seen that this i s an upset tourna22
PAGE 31
ment. For n > 4, letT be antournament with the given score sequ e nce let u and v be the vertices ofT with score 1, and assume that uv E A. Consider the tournament T' = Tu. Clearly, the score of every vertex x in T' is one less than the score of x in T, apart from v, whose score is unchanged Thus, the score sequence of the (nI)tournament T' is (1, 1, 2, 3, ... n4, n3, n3). By the induction hypothesis, T' is an upset tournament. Let U be an upset path of T'. The first vertex of U has outdegree 1 in T'. If v is on the path U then we consider the subpath U' that begins at v and ends at the terminal vert ex of U. Reversing this path in either T' or T leaves a transitive tournament, and henc e U' is an upset path of both T' and T. If v is not on the path U, then the only neighbor of the initial vertex of U is clearly the second vertex of this path. Hence v dominates the initial vertex of U. As a result, we can form the path U' = vU, and just as before this path U' is an upset path of both T' and T D 3.1 Arctraceable upset tournaments We now address the question of arctraceability in upset tournaments. Ini tially, we characterize which arcs of an upset tournament lie on a hamiltonian path. Theorem 3.2. LetT denote an upset tournament on n 2:: 6 vertices with upset path U. If V is labeled V = { v1 ... Vn} 1 so that vivj E A if and only if either i < j or ViVj is an arc of U1 then the arc VrVs ofT is nontraceable if and only if all of th e following hold: Both Vr E V(U) and Vs E V(U). VrVs is not an arc of the upset path. 23
PAGE 32
For each vertex Vk E V(U) with r < k < s, neither vkl nor vk+l are vertices of the upset path. Proof. Let VrVs be an arc ofT that is on no hamiltonian path. First, we show that both Vr and V5 are vertices of the upset path. This follows from the ob servation that T vi is an upset tournament for any vi not on the upset path. Since upset tournaments are strong, this tournament has a hamiltonian cycle and consequently, a hamiltonian path beginning or ending at any specified ver tex. So if Vr is not on the upset path, we can cho ose a hamiltonian path H ofTVr that begins at the vertex V5 Now, vrH is a hamiltonian path ofT containing the arc VrVs, a contradiction. Similarly, if V5 is not on the upset path, we choose H a hamiltonian path ofTV5 that ends at the vertex Vr and Hvs is a hamiltonian path containing VrV5 As no such path exists, V5 E V(U). Next, we show that VrVs is not an arc of the upset path. This follows from the observation that TV(U) is a transitive tournament whose sourc e is dominated by v1 in T. If H is the unique hamiltonian path of T V ( U), U H is a hamiltonian path ofT containing the arc VrV8 As no such path exists, VrVs can not be an arc of the upset path. Thus, r < s and for at leas t one k such that r < k < s, Vk E V(U). Now, we show that for each vertex Vk E V(U) where r < k < s, neither vkl nor vk+l is on the upset path. Suppose that for some such k, Vk1 is on the upset path, so vkvkl is an arc of U. Then, both T1 = T[{ v1, ... vkd] and T2 = T[ { Vk, ... vn}] are upset tournaments and hence strong We can then choose a hamiltonian path H1 of T1 that ends at Vr and a hamiltonian path H2 of T2 that begins at the vertex V5 But then H1H2 is then a hamiltonian path of 24
PAGE 33
T containing VrVs, a contradiction. Similarly if vk+l is on the upset path then by the same argument with T1 = T[ { v1 ... vk}] and T2 = T[ { Vk+l, ... Vn}], VrVs is on a hamiltonian path. So, neither Vkl nor vk+l are on the ups e t path. For the converse, suppose that VrVs is an arc ofT, where both Vr E V(U) and V8 E V(U), VrVs is not an arc of the upset path, and that for each Vk on the upset path U between Vr and V8 neither vkl nor Vk+l are on the upset path. Let Q be a longest path ofT that contains the arc VrVs, and let U[vs, vr] be the subpath of U beginning at V8 and ending at Vr. First, note that Q can not contain U[v8 vr] as a subpath, since v8 follows Vr on this path but Vr follows V8 on Q. So we can choose an upset arc VqVp of U[v8 vr] that is not part of the path Q. Note, by assumption p + 1 =f q and every path from Vp+l to Vr must contain the arc vqvp. Sin ce Q does not contain this arc, Vp+l does not preced e Vr on Q. Similarly, every path from V8 to Vp+l must include the arc VqVp, and hence Vp+l does not follow V8 on Q But Vr and V8 are consecutive on Q, and so Vp+l is not on the path Q. Thus, Q is not a hamiltonian path, and since the length of Q is maximal, no hamiltonian path COntaining VrVs exists. 0 The above result completely characterizes arctraceable upset tournaments with six or more vertices. Corollary 3.3. An upset tournament T on n 6 vertices zs arctraceable if and only if for ever y vertex vk on the interior of the upset path, either Vkl or Vk+l is also on the upset path. Proof. If T is a tournament satisfying the given condition, then Theorem 3.2 25
PAGE 34
Figure 3.1: An 11tournament with 10 nontraceable arcs implies that there is no arc that is nontraceable, i.e. T is arctraceable. For the converse, assume there is some vk on the upset path with neither Vk_1 nor vk+l on the upset path. Let vi and Vj be the vertic e s immediately preceding and succeeding Vk on U, respectively. Then, by Theorem 3.2 VjVi is on no hamiltonian path. D The above results fail for n = 5 vertices as the upset tournament obtained from reversing the unique hamiltonian path of the transitive tournament on five vertices is not arctraceable, despite satisfying the conditions of Corollary 3.3. This is a consequence of the fact that this tournament is isomorphic to the upset tournament with an upset path of length with middle vertex of score 2, and this tournament does not meet the criteria indicated in the corollary. In fact, there are only two nonisomorphic upset tournaments on five vertices. The other is obtained by reversing the single arc from source to sink in a transitive tournament, and this tournament is easily seen to be arctraceable. Next we describe an upset tournament with many nontraceable arcs, and prove that this example is maximal. Theorem 3.4. If T is an upset tournament with n ?::: 5 vertices n odd, and the th 1T th tl n24n+3 1 (n) 3(n1) upset pa o zs VnVn2Vn_ 4 ... V3V1, en exac y 8 = 4 2 8 arcs ofT are not on a hamiltonian path. 26
PAGE 35
Proof. By Theorem 3.2 the arcs ofT on no hamiltonian path are of the form vivi+(2k+2) for i odd, 1 ::; i ::; n 4 and 1 ::; k ::; 1. Thus, for a fixed i = 2j + 1, there are exactly 1 = 1 = j nontraceable arcs starting at vertex vi. Summing all possible values of j, we obtain n5 (n3 j) = (n3) (n3) n2 4n + 3 2 2 2 2 8 j=O nontraceable arcs in T. 0 Figure 3.1 shows a tournament of order 11 with the structure describ e d above. We now show that this family of examples has the maximal number of nontraceable arcs among all upset ntournaments. Theorem 3.5. An upset ntournament T n 2 5, has at most n2 4n + 3 = (n) 3(n1) 8 4 2 8 nontraceable arcs. Proof. We prove the result by induction on n. For n = 5, it is easy to verify that any upset tournament on five vertices not having the structure indicated in Theorem 3.4 is arctraceable, and that the upset tournament with this structure has = 1 arc that is not on any hamiltonian path. Next assume the result for upset tournaments with f e wer than n > 5 vertices. Let i be the vertex that immediately precedes the vertex v1 on the upset path. As observed e arlier, T1 = T[vi, ... vn] is an upset tournament, and so by the induction hypothesis there are at most (ni + 1)2 4(ni + 1) + 3 = n2 4n + 3 (i 1)_2n__4_'(i__1') 8 8 8 27
PAGE 36
nontraceable arcs in T1 By applying Theorem 3.2 twice, once for n ece ssity in T1 and again for sufficiency in T, we note that eac h of these arcs i s also nontraceable in T All that remains is to count the nontraceable arc s of T that are not arc s of TI Clearly, no arc incident with the vertices v 2 ... viI is nontraceable so any nontraceable arc of T that is not an a rc of T1 is incident with VI Additionally, if i = 2, then by Theorem 3 .2, every arc incident with vi is also on a hamiltonian path. In this case, the Theorem follows by observing that ( i 1) = 2n8 5 > 0 as n > 5. So, we may assume that i ;::: 3. In this case, as n > 5 it follows that (ni + 1)2 4(ni + 1) + 3 (n2)2 4(n2) + 3 n2 8n + 15 < = 8 8 8 Thus, we must show that at most 4n8I2 = arcs incident with VI ar e nontraceable. Let j be the largest index such that the arc VI Vj is nontraceable. As a consequence of Theorem 3.2, at most j;I of the vertices v i, Vj a re on the upset path of T and vi is one of these vertices. Since viv1 is part of the upset path, and thus is part of a hamiltonian path, this implies that at most 9 1 :S arcs incident with the vertex VI are not a part of any hamiltonian path, and the result follows. 0 3.2 Counting Hamiltonian Paths in Upset Tournaments To conclude this section, we consider the connection between arctraceability and the number of distinct hamiltonian paths in upset tournaments. We note a result by Moon [28] that gives a lower bound for the number of hamiltonian paths in strong tournaments. 28
PAGE 37
Theorem K (Moon [28]). An strong tournament on n vertices has at least n1 64 (.639)(1.565n) distinct hamiltonian paths. It is natural to expect that, in general, arctraceable upset tournaments have more hamiltonian paths than nonarctraceable upset tournaments. However, we shall now show that this is not always the case. We observe again that for any vertex v in an upset tournament T, Tv is also an upset tournament if v is not the interior of some upset path. If v is on the interior of some upset path, then it is a cut vertex and the first and last strong components of T v are upset tournaments with the remaining strong components all trivial (consisting of single vertices). Combined with the observation that the number of hamiltonian paths in a tournament T is the product of the number of hamiltonian paths of the strong components of T, this suggests that we can find the number of hamiltonian paths of an upset tournament recursively. In particular, we next consider two simple techniques that will show that it suffices to count the number of hamiltonian paths of any upset tournament in which no three consecutive vertices lie on the upset path. Let Pr denote the number of distinct hamiltonian paths of the tournament T. Theorem 3.6. If T is an upset ntournament and Vj is a vertex on the upset path such that neither Vj_1 nor VJ+1 are on the upset path, then then Pr = Proof. Let'}{ be the set of hamiltonian paths ofT, and let 'H1 and 'H2 be the sets of hamiltonian paths of T[v1 ... vj] and T[vj, ... vn], respectively. We show a bijection between 'H and 'H1 x 'H2 29
PAGE 38
Let H be a hamiltonian path of T. We define the sequence of vertices S1 by deleting each vertex of H with index greater than j. We claim that s1 is a hamiltonian path of T[v1, ... ) vjl Assume otherwise and let Vs and Vt be consecutive in S1 with Vs /+ Vt Since H is a path, V8 and Vt can not be consecutive on H, and so there must exist a vertex Vr between V8 and Vt on H with r > j. But since T is an upset tournament every path from Vr to Vt must include the vertex Vj, and since Vj was not deleted from S1 we conclude that t = j and so s < t. Since V8Vt is not an arc ofT, VtVs must be an upset arc. Since v8 precedes Vt on H, this arc is not part of H. It follows that this arc is included on every path from Vjl to V8 in Taswell as on every path from Vt to Vj_1 Thus, we conclude that Vjl does not precede V8 or succeed Vt on H. Since H is a hamiltonian path, this vertex must lie between V8 and Vt on this path, contradicting the fact that these vertices are consecutive in S1 Consequently, S1 must be a hamiltonian path of T[v1 ... vj] Similarly, the sequence 52 obtained by deleting the vertices of H with index less than j is a hamiltonian path of T[vj, ... Vn] On the other hand, let P 1vjQ1 and P2v]Q2 be hamiltonian paths ofT[v1 ... vj] and T[vj, vn], respectively. Then H = P 1 P 2vQ1 Q 2 is a hamiltonian path of T D Our next result is a similar result that applies to tournaments in which two consecutive vertices may be on the upset path. Theorem 3. 7. Let T be an upset tournament, and let vi+l vi be an arc of the upset path ofT, where vi+2 and vi_1 are not vertices of the upset path. Then 30
PAGE 39
th e number of hamiltonian paths ofT is 2ab cd wher e a is PT[v1 ... ,vi), b is PT[vi+l,vn]J c is PT[vi+2,vn] and d is PT[vl ,Vid. Proof. The proof is similar to the proof of Theorem 3.6 Begin with P1 v;Q1 and P2vi+l Q 2 hamiltonian paths of T[v 1 ... v;] and T[vi+1 ... vn], r es pec tively. Now, define two sequences of vertices H1 = P1P 2vi+1v;Q1 Q2 and H2 = P1v;Q 1P2vi+1Q2. Clearly, H 1 is a hamiltonian path and H 2 is as well provided that either Q1 =J. 0 or P2 =J. 0. Now if Q1 = 0, then P1 must be a hamiltonian path of T[v1 ... v;_I] and if P2 = 0 then Q2 is a hamiltonian path of T[vi+ 2 ... vn]. Thus the number of distinct hamiltonian paths ofT is at least ab + (abcd) = 2abcd where a, b c and dare defined as in the Theorem For the reverse inequality let H be a hamiltonian path ofT. First, assume that v;+ 1 v; is an arc of H. Then let H = Pv;+ 1 v; Q and let Pr and Q 1 be the vertices of P and Q, respectively, with index less than i. We claim that P1v;Q1 is hamiltonian path of T[v1 ... v;]. Assume othe rwise Then, there are consecutive vertices V8 and Vt in the sequence P1v;Q1 such that Vt dominates Vs. This requires that vi+1 must succeed V8 and precede Vt on H and thus t = i. Since v; dominates only one vertex in T[v1 ... v;J, this vertex must be V5 and since v;_1 is not on the upset path s < i1. As above, the arc VtVs is on e very path from Vt to vi_1 as well as every path from v;_1 to V8 Since this arc i s not included in H v;_1 must preced e Vt and succeed V5 This contradicts our choice of v 8 and Vt as consecutive vertices of P1 v; Q 1 so this sequence of vertic es forms a hamiltonian path of T[v1 ... v;]. Similarly, P2vi+1Q 2 is a hamiltonian path of T[vi+1 ... vn] where P 2 = P \ P1 and Q2 = Q \ Q1 Thus, there are at most ab hamiltonian paths ofT that contain the arc v;+1v;. 31
PAGE 40
Now, assume that vi+1vi is not an arc of H Then H is also a hamiltonian path of the tournament T' obtained by reversing this arc. T' has two strong components, T[v1 ... vi] and T[vi+l, ... vn] and so any hamiltonian path ofT' must have the form PQ where P is a hamiltonian path of T[v1 ... vi] and Q is a hamiltonian path of T[vi+1 ... vn] So H has this form and since His also a hamiltonian path ofT, we cannot have both Pending at vi and Q beginning at vi+l Clearly there are ab ways of choosing an arbitrary P and Q, and there are cd ways of choosing such that both P ends at vi and Q begins at Vi+l Thus, there are at most ab cd hamiltonian paths of T that do not contain the arc 0 Next, we count the hamiltonian paths of an upset tournament with an upset path of length one. This, combined with the previous two results, permits a recursive technique that can be used to determine the number of hamiltonian paths of any upset tournament in which no three consecutive vertices are on the upset path. Theorem 3.8. The upset tournament on n vertices with a single upset arc has 2n2 + 1 hamiltonian paths. Proof. LetT be an upset ntournament with the single upset arc vnv1 First, we consider hamiltonian paths that do not use the upset arc. Each such path is also a hamiltonian path of the transitive tournament obtained by reversing this upset arc. Since the transitive tournament has a unique hamilto nian path, we conclude that there is a unique hamiltonian path of T not using the arc Vn v1. 32
PAGE 41
Now, we consider hamiltonian paths using the upset arc ofT. Let S1 be the set of vertices preceding Vn on such a hamiltonian path. We note that S1 is a subset of S = { v 2 v3 ... Vnd Conversely let S1 be any subset of S and let s2 = s \St. Since T[Sd and T[S2] are both transitive tournaments, and Vn is dominated by S1 and v1 dominates S 2 there is a unique hamiltonian path ofT containing the arc VnVt where S1 is the set of vertices preceding Vn Thus, there is a bijection between subsets of S and hamiltonian paths ofT containing the arc VnVt and consequently, it follows that there are exactly 2ISI = 2n2 hamiltonian paths containing the arc vnv1 and 2n2 + 1 hamiltonian paths in total. D Corollary 3.9. If T is an upset tournament on n vertices with an upset path of length 2, then T has at least 2n3 + 2 n21 + 1 hamiltonian paths, with equality if and only if n is odd and the upset path is Vn Vn+l v1 2 Proof. Let Vj be the middle vertex of the upset path. Then by Theorem 3.6, PT = PT[v1 ... ,viJPT[ vi ... ,vnJ Furthermore, by Theorem 3.8 PT[v1 ... ,vil = 2j2 + 1 and PT[vj, ... ,vn] = 2njl + 1. Thus PT = 2nJ + 2j2 + 2njl + 1. The proof is complete by noting that the function f(x) = 2x2+2nlx has a global minimum at X= ntl. D We note, as a consequence of this corollary the number of hamiltonian paths in upset ntournaments with upset paths of length two grows exponentially with n at a faster rate than the lower bound given by Theorem K. Specifically, 2n < PT < 2n for n > 5. Additionally we note that for n 2: 5 upset tournaments with upset paths of length two are necessarily nonarctrac eablP. by Corollary 3.3. 33
PAGE 42
.... Figure 3.2: Two 8tournaments We can now use the above results to show that the first 8tournament shown in Figure 3.2 has precisely 2(5)(5)1 = 49 hamiltonian paths and by Corollary 3.3 is arctraceable. Similarly the second 8tournament shown in Figure 3 2 is nonarctraceable and yet has 3(17) = 51 hamiltonian paths. The above results also permit us to count the number of hamiltonian paths of every upset tournament on seven or fewer vertices, with one exception. The only exception is the upset tournament on seven vertices with upset path v7v5v4v3v1, which is isomorphic to the upset tournament with upset path v7v6v5v4v3v2v1 For this case, we will show that this tournament has 31 distinct hamiltonian paths. Table 3.1 lists all upset tournaments of order three through seven the number of distinct hamiltonian paths, and whether the tournament is arctraceable or not according to Corollary 3.3. From the data, we conclude that the tournaments in Figure 3.2 are minimal with respect to the number of vertices. In other words if T is an arctraceable upset ntournament with k hamiltonian paths, and T' is a nonarctraceable upset ntournament with k' > k hamiltonian paths, then n 8. We now consider the family of upset ntournaments with upset paths of length n1. In other words, the tournaments obtained by reversing the arcs in 34
PAGE 43
Tournament: T PT Arctraceable? Tournament: T PT Arctraceable? 3 Yes 5 Y es 9 Yes 9 No 17 Yes 15 No 15 No 17 Yes 33 Yes 27 No 25 No 29 Yes 27 No 27 No 29 Yes 31 Y es Table 3.1: All upset tournaments of order three through seven. the unique hamiltonian path of a transitiv e ntournament. We show that the the number of hamiltonian paths of such anntournament satisfies the tribonacci recurrence for n 2: 3 and use this recurrence to obtain asymptotic results for the number of hamiltonian paths in such tournaments. For convenience, in the remainder of this chapter we will use the notation Ti to refer to the upset tournament with ivertices with an upset path of length i 1. W e will then denote the number of hamiltonian paths of T i as Pi. In the following proof we require some new notation. We will say that a path P is vdeletable when v is on the path P, and either v is the initial v e rtex of P or the vertex immediately preceding v dominates the vertex immediately following v. Conversely v can be inserted into P if v is not on P a nd there are consecutive vertices x and y on P such that x > v and v > y. If the 35
PAGE 44
terminal vertex of P dominates v, then we will say that v can be appended onto P. Dually, if the initial vertex of P is dominated by v, then we will say that v can be prepended onto P. Theorem 3.10. Pn = Pn1 + Pn2 + Pn3 for n 2: 3. Proof. Let Si be the set of hamiltonian paths We establish the result by showing a bijection between Sn and Sn1 U Sn2 U Sn3 Initially, we partition the set Sn into two parts; Sn, 1 the hamiltonian paths ending at Vn and Sn,2 those ending at any vertex other than VnWe further subdivide each Sn,i; let Un,l be the set of all hamiltonian paths of Sn,1 that are Vn 1 deletable and let Un,2 be the set of all hamiltonian paths of Sn, 2 that are Vn deletable. Finally, let Wn,i = Sn,i \ Un i fori= {1, 2}. We now construct the desired bijection in three parts. First, we not e that the re is a bijection between Un, 2 and Sn_1 By deleting V n from each path of Un 2 we obtain a hamiltonian path of Tn_1 and since N+(vn) = {vn1}, Vn can be inserted into or prepended onto a hamiltonian path of Tn_1 in a unique way. Since no path of Un, 2 ends at Vn Vn is interior on every path of Un 2 and thus two hamiltonian paths of Un,2 are distinct if and only if the y can be obtained in this way from distinct hamiltonian paths of Tn_1 Next we observe a bijection between Un,1 and Sn_2 By deleting both Vn and Vn_1 from a hamiltonian path of Un,1, we obtain a hamiltonian path of Tn_2 and as in the previous case, Vn_ 1 can b e inserted into the interior of each hamiltonian path of Tn_2 in a unique way Furthermore we can append Vn to the end of each of these paths, thus obtaining hamiltonian paths of U n ,1 Just as above, two paths of Un,1 are distinct if and only if they can be obtained in 36
PAGE 45
this way from distinct paths of Tn_2 The last part of our bijection is between Wn,l U Wn,2 and Sn3 We first show that each path P of Wn, l must end with the subpath Vn3VnIVn2Vn Since a path P of Wn,l does not end at Vnl, and N+ ( Vnd = { Vnd, P must include the arc VnIVn_2 Furthermore becaus e P is not Vnl deletable the vertex immediately preceding Vnl must be dominated by Vn_2 and so must be a vertex in N+(vn2) = { Vn3, Vn} As P ends at Vn by definition, this vertex must be Vn3 and the vertex immediately following Vn2 must be Vn, the terminal vertex of P. Similarly we show that each path P of Wn,2 must end with the subpath Vn2VnVn1 Since P does not end at Vn and N+(vn) = {vnI} it contains the arc VnVn1 and since P is not Vn deletable, the vertex immediately preceding Vn on P must be in the set N+(vnd = {vnd Further, since this is the only vertex dominated by Vnl, Vnl must be the terminal vertex of P Thus, for any path of Wn,l U Wn,2 the first n3 vertices form a hamiltonian path of Tn3 Conversely, any hamiltonian path H of Tn_3 can be extended to a hamiltonian path of Tn by appending the path Vn1Vn2Vn if H e nds at Vn3, or appending the path Vn2VnVn1 if H does not end at Vn3 D Next, we note that p1 = p2 = 1 anq p3 = 3 and this defines the sequence A000213 in the database maintained by Sloane [37] (offset by one) Note that by Corollary 3.3, Ti is not arctraceable for all i 6. Also, p7 = 31, completing our table of the number of distinct hamiltonian paths for all upset tournaments with b e tween three and seven vertices. 37
PAGE 46
The tribonacci recurrence shares many similarities with the better known Fibonacci recurrence. In particular just as the ratio of Fibon acci numbers approaches the positive r ea l root of x2 x 1 the ratio of consecutive numbers in a sequence satisfying the tribonacc i recurrence approaches the positive (and only) real root of x3 x2 x 1 [22]. Corollary 3.11. The number of hamilton ian paths of an upset ntournament with upset path of length n 1 approach es an as n approaches infinity, where a is the real root of x3 x2 x 1 (approximately 1. 8329). Thus, it is clear that the tourname nts in Figure 3.2 are not isolat ed examples; in fact, there exist infinitely many such exa mples. For n 2: 15, the nonarc traceable upset tournament T with upset path VnVrntl1v1 h as more distinct hamiltonian p aths than the arctraceable upset tournament T' with ups et path VnVn1 ... v1, and PTPT' grows exponentially with n. 38
PAGE 47
4. Arctraceability in all strong tournaments In this chapter we turn our attention to arctraceability in all strong tour naments. We require very different techniques than were used for up set tourna ments, and we will fall just short of a characterization of arc traceabl e strong tournaments. However we will develop a specific structure that is shared by all nonarctraceable strong tournaments, and we will use this structure to obtain many sufficient conditions for strong tournaments to be arc traceabl e and to yield some extre mal results for nonar ct raceable tournaments. 4.1 Observations on arctraceability in tournaments We recall that in a hamiltonian digraph D, then for any v E V(D), D has a hamiltonian path that begins at v and also a hamiltonian path that e nds at v. Since every strong tournament is hamiltonian, we observe that nontraceabl e arcs of a tournament must join two cut vertices. Proposition 4.1. If T is a strong tournament and v is not a cutv ertex ofT, then ever y arc incident with v is on a hamiltonian path. This gives us our first sufficient condition for arctraceable tournaments; if T has no cut v e rtices then T has no nontrac eab le arcs. Corollary 4.2. If T is 2connected, then T is arctraceable. This first sufficient cond ition was observed in the more general setting of multipartite tournaments by Volkmann in [42]. Our second sufficient condition 39
PAGE 48
requir e s the following result using a techniqu e similar to the proof of Theorem H by Moon in [29]. Lemma 4.3. L e t xy be an arc in a strong tournament T. If P is a long est path from y to x in T, then P can be ext ende d to a hamiltonian c ycle. Proof. Let P be a longest path from y to x and l e t C be the longest c ycle that contains P Assume that C is not h a miltonian Thus, there is some vertex v that is not on C. If y dominates v then v must dominate each v e rtex of P. Otherwise let u be the first vertex along P such that vu E A(T) and let w be the vertex immediately prec eding u on P. Now y ... w v u ... x is p ath from y to x longer than P. Thus, v dominates x and by a similar argument using the maximality of C v must al s o dominate the subp ath of C from x toy. In other words, v dominates all of the vertices of C. But since T is strong, the re must be a path from every vert e x of C to v. Let Q be the shortes t of these paths and note that this minimality requires that the only vertex of Q on C is the initial vertex vq. Let v;; and v; be the immediate predecessor and successor to Vq on C r e spectively. If the arc vqv; is an arc of P, the n y ... v;;Qv; ... x i s a path from y to x longer than P. Otherwise the cycle C' obtaine d by replacing the arc vqv; with the path Qv; is a cycle containing P that is longer than C In either case, we have obtained a contradiction. 0 W e now can show: Theorem 4.4. LetT b e a strong ntournament, and let x y E A(T) b e o n som e cycl e of length l > n!l. Th e n xy is on a hamiltonian path ofT. 40
PAGE 49
Proof. Let C = yui ukx be the longest cycle containing the arc xy. Extend Cxy to H, a hamiltonian cycle ofT. Let H = yui UkXWm WI. So n = k + m + 2 and since C has length k + 2 > nti, k m. If wi dominates ui for some i choose the minimal such z If i = 1 then define the path P = Wm wiul ukxy, otherwise define the path P = Wm WiUi UkXYUI uiIwil WI In either cas e P is a hamil tonian path of T containing xy. So we may assume that ui dominates wi for every i, 1 :::; i :::; m. In particular, we may assume that UmWm E A(T). If k = m, then let P = xyui ukwm WI, and if k > m set P = Um+l UkXYUI UmWm WI In either case, P is a hamiltonian path of T containing the arc xy. D From this we infer a second sufficient condition for a strong tournament to be arctraceable Corollary 4.5. 1fT is a strong tournament and every arc ofT is on some cycle of length l > nti then T is arctraceable. We now consider again our observation above that every 2connected tour nament is arctraceable. If a tournament is twoconnected (and h e nce arc traceable), then Theorem E states that for any two vertices x and y such that y x, there must be at least two internally vertex disjoint paths from y to x. Of course, in a tournament y x implies that x + y. So we can restate our observation above as follows. Proposition 4.6. If T is a tournament with the property that ther e e xist at least two internally vertex disjoint path from y to x for every arc xy, then T is 41
PAGE 50
arctrac eable. We show this property applies locally as well. Any arc xy where the smallest y, x separating set has size at least 2 is traceable. We use Theor e m E and state the result in terms of internall y vertex disjoint paths. Theorem 4.7. LetT be a strong tournament, and let xy E A(T) be such that there exist at least two internally v e rtex disj oint paths from y to x in T. Then there exists a hamiltonian path ofT which includes the ar c xy. Proof. Let P and Q b e two internally vertex disjoint paths from y to x such that for any internally vertex disjoint paths P' Q' from y to x, IV(P) UV(Q)I 2: IV(P') U V(Q')I. Let P = yuo UmX and Q = ywowl WkX, and l e t U = {ua, ... ,um} and W = {wa, ... ,wk}. If V(P) U V(Q) = V(T), the n H = u0 umx yw1 wk is a hamiltonian path ofT containing x y So assume V ( P) U V(Q) C V(T) and let S be the tournament induc e d on the vertices of V(T) \ (V(P) U V(Q)). If V(S) dominates U U W then for any hamiltonian path Hs ., of S, H = Hsuo umxyw0 wk is a hamiltonian path ofT containing xy. Additionally, if V(S) is dominated by U U W, then H = uo UmXYWo wkHs is a hamiltonian path ofT which contains xy for any h a miltonian path Hs of S. Hence we may assume that V(S) neither dominates nor is dominat e d by U U W. Choose the minimal r such that a vertex v of the rth strong component of S is beaten by some vertex of U U W. Without loss of generality, assume that u i v E A(T) for some i. If vuJ E A(T) for som e j > i, choos e the minimal s uch j Observe that P' = yu0 U j _1vuj UmX and Q' = Q are internally vertex di s joint paths from 42
PAGE 51
y to x with IV(P')UV(Q')I > IV(P)UV(Q)I, contradicting the maximality of P and Q. Consequently, Uj dominates v for every j > i, and in particular, umv E A(T). Now, partition 8 into two disjoint subtournaments, 81 (possibly empty) containing the vertices of the first r 1 components of 8 and 82 containing the remaining vertices Thus, v is in the initial strong component of the tournament 82 Let H1 be any hamiltonian path of 81 and let H2 be a hamiltonian path of 82 that begins at v. Since the terminal vertex of H 1 is from the ( r 1 )st component of 8, this vertex dominates U U W by the minimality of r. Thus H = H1w0 WkXYUo umH2 is a hamiltonian path ofT containing xy. D The above result can be used to derive some tests for traceability for a given arc xy. In the next section we will show that eac h of the following results can be improved. Corollary 4.8. Let xy be an arc ofT. If d+(y) > d+(x), then there is a hamiltonian path ofT that includes the arc xy. Proof. As J+(y) > d+(x), jN+(y)l > IN+(x)l. Furthermore xy E A(T) so y E N+(x) \ N+(y). Thus IN+(y) \ N+(x)l = IN+(y)l IN+(y) n N+(x)l IN+(y)IIN+(x) \ {y}l = d+(y)(d+(x)1) 2. Thus, there exist distinct vertices u1 and u2 such that yu ix is a path of length two for i = 1 2, and by Theorem 4.7, the arc xy is traceable. D 43
PAGE 52
The next three sufficient conditions for arctraceab l e tournaments are closely related and follow from the fact that all 2connected tournaments are arctraceable, which can be thought of as a corollary of Theorem 4. 7. Corollary 4.9. IJT is a tournament with 6 > n11 } then T is arctraceable. Proof. We prove that the condition guarantees that T is 2connected. Assume otherwise, and choose v such that Tv is not strong. Let a and b be the number of vertices in the initial and terminal strong components ofTv respectively Then Tv must contain a vertex with indegree at most a;l and a vertex with outdegree at most b;1 Thus, Finally, since n 2: a+ b + 1 6(T) :S n1l. 0 Corollary 4.10. IJT is a tournament such that for every uv E A(T)) d(u) + d+(v) > then T is arctraceable. Proof. The proof is the same as for Corollary 4.9, combined with the additional observation that the vertex u with indegree at most a;l in Tv dominates the vertex w with outdegree at most b;l in Tv. Thus we have an arc uw such that Corollary 4.11. Let T be a tournament such that i(T) < arctraceable 44 n3 4. 0 Th e n T is
PAGE 53
Proof. The result follows from Corollary 4.9 and the fact that i(T) = (n1)26. Thus, o0 > ntl implies that i(T) < (n1 ) = 0 4.2 The structure of nonarctraceable tournaments Since the results of the previous section are really based on the observation that every twoconnected tournament is arctraceable Theorem 4.7 has not yet proven useful in the study of arctraceabl e tournaments. However, the contra positive of Theorem 4. 7 can be used to obtain some important necessary conditions for nonarctraceable tournaments. This necessary structure is the basis for improving the bounds given in the Coro ll aries above and for many of the results to follow. Theorem 4.12. If T zs a strong tournament, and xy E A(T) is not on a hamiltonian path, then: (i) There exists a vertex z such that Tz is not strong (ii} T z has k strpng components, k ;:::: 4. {iii} x is in the initial strong componeht ofT z, and y is in the terminal strong component ofT z (iv) z is dominated by the 2nd strong component ofT z and z dominates the ( k 1) st strong component ofT z. Proof. By Theorem 4. 7 there is at most a single vertex disjoint path from y to x in T, and since Tis strong, there must be exactly one such path. Equival e ntly, by Theorem E there is a y, x separatin g set of size one Let { z} be this set. 45
PAGE 54
Thus, there is no path from y to x in Tz, so y and x are in different strong components ofTz and this tournament is not strong establishing (i). Let T z denote Tz, k be the number of strong components of Tz, and rPl' rP)' ... be the strong components of Tz where rYl dominates rYl whenever i < j. As x dominates y in Tz, x must be in a strong component that precedes the strong component containing y. So x can not be in the terminal strong component of Tz. If x is not in the initial strong component of Tz, then Tx is strong and every arc incident with x is on some hamiltonian path. Thus, x must be in the initial strong component of Tz. Similarly, y must be a cut vertex ofT, soy must be in the terminal strong component of Tz, establishing (iii). H k = 2, then let P1 be a hamiltonian path of rP) that terminates at x, and P2 be a hamiltonian path of rPl that begins at y. Since T is strong, z must beat some vertex of the path P1 Let w be the first such vertex along the path P1 If w is the initial vertex of P1 then let H = zP1P2 Otherwise, let wbe the vertex immediately preceding w on P1 and replace the arc ww of P1 with the path wzw to form P{ and let H = P{ P2 In either case His a hamiltonian path ofT containing xy, contradicting the choice of xy. So, k 2: 3. Next, assume that there is some z+ E N:j:(z) n V(TP)). Since T is strong, we can choose zE Ni(z) n V(T?l), and let Pk be some path from y to zin rikl, Now, let be a hamiltonian path of the tournament induced on V(T;k)) \ V(Pk), let P1 be a hamiltonian path of rPl that terminates at x, let P2 a hamiltonian path of TP) that originates at z+, and let Pi be any hamiltonian path of TY) for 3 i k 1. Combining these paths we can construct H = P1PkzP2P3 a hamiltonian path ofT containing xy. Hence, there 46
PAGE 55
Figure 4.1: An arctraceable tournament. is no such z+ in V(TP)). Dually, we have that there is no Uf"(z)nV(T;k1)) = 0 establishing ( iv). This argument also shows that k1 # 2, and so k # 3. Hence, k 2 4 establishing (ii). D The above result indicates a n ecessary structure for tournaments that are not arctraceable. However, such a structure is not sufficient to guarantee non arctraceability For e xample, the arctraceable tournament in Figure 4.1 has the structure indicated in Theorem 4.12. In an attempt to complete a characterization of arctraceable tournaments, we consider whether additional structure imposed on the first and last strong components ofTz is sufficient to guarantee nonarctra cea bility Lemma 4.13. LetT be a tournamen t with cut vertex z E V(T), such that T z has k 2 4 strong components. Further let rP) dominate z and let z dominate r;k1 ) in T. For X E rP) andy E r;k)' xy is part of some hamiltonian path if and only if (i) the vertices of TP) can be partitioned into paths P1, QJ such that P1 begins at a vertex dominated by z and Q1 ends at x or (ii) th e 47
PAGE 56
vertices of can be partitioned into paths Pk, Qk such that Qk begins at y and Pk ends at a vertex that dominates z. Proof. We prove only the sufficiency of condition (i), as condition (ii) is equiv alent to condition (i) in the r e versal ofT. Assume that condition (i) holds. Let be a hamiltonian path of TY) for 2 :S i :::; k 1 and let Q k be any path in from y to a vertex that dominates z. Finally let Pk be a hamiltonian path of V(Pk) Then H = Q1QkzP1P2P2 ... Pk is a hamiltonian path of T containing the arc xy. For the converse, assume that T is arc traceable and let H be a hamiltonian path of T containing the arc xy with x E TP) and y E First observe that H contains at most one other arc uv with u E TP) and v :. TP), as z must lie between any two such arcs on H. If H does not contain another arc with this property, then the initial vertex of H must be a vertex of TP). In this case, the portion of the path H that lies in TP) is a hamiltonian path of the subtournament that begins at a vertex dominated by z and ends at x. Removing any arc of this subpath yields two paths that satisfy condition (i). So, we may assume that H contains an arc uv =I= xy with u E and v :. TP ) and in this case, the portion of H that lies in TP) consists of two vertex disjoint paths, P1 and Q1 (assume that H precedes Q1 on H). If xy precedes uv on H then P1 ends at x and the vertex immediately preceding Q1 on H must be z, and so condition (i) is satisfied. If uv precedes xy on H, then there must be an arc u'v' with u' :. and v' E such that u'v' precedes xy on H. In the reversal of T, we find that yx precedes v' u' on the reversal of H, and condition (i) is satisfied in T, and equivalently, condition (ii) is satisfied in T. D 48
PAGE 57
We note that a corollary of this r es ult does g ive a sufficient condition for nonarctraceability in strong tournaments. Corollary 4 .14. Let T be a strong tournament having the structure given by Theorem 4.12. If JN+(z) n TP)I = 1 and IN(z) n = 1 then T is not arctraceable. Proof. Let N+(z) nTP) = {x} and N(z) = {y}. Then by L emma 4.13, xy is nontraceable. 0 Note that the converse of this corollary is false as the tournament in Figure 4.1 is not arctraceable. At this point it appears we hav e characterized arctraceable tournaments. However, Lemma 4.13 is deceptive. We offer the following co rollary to make this clear. Corollary 4.15. L et T be a strong tournament having arc xy and the structure given by Theorem 4.1 2 Let U = N+(z) n TP) and W = N(z) n Now, if necessary, rev e rse arcs ofTP) to form the tournament R1 such that x dominates U. Similarly, form the tournament Rk where W dominates y by reversing arcs, if necessary. Then xy is traceable in T if and only if the arc xu is traceable in R1 for any u. E U, or the arc wy is traceabl e in Rk for any wE W. Proof. If such a traceable arc exists in Rk or R1 let H be a hamiltoni a n path containing this arc. Now form paths P and Q that satisfy L emma 4.13 by deleting the arc xu or wy. Conversely, if there ex ist two paths that satisfy this Lemma then these two paths plus an arc xu or wy form a hamiltonian path of R1 or Rk. resp ect ively. 0 49
PAGE 58
It is now clear that our characterization is something of a tautology. A tournament T is not arctraceable if and only if some other related tournaments R1 and Rk are not arctraceable. For this reason, we generally will find it easier to use the incomplete results of Theorem 4.12 to produce sufficient conditions for arctraceable tournaments (and conversely necessary conditions for nonarc traceable tournaments) and will use the additional structure given by Lemma 4.13 less often. One aspect of Lemma 4.13 that we will use in the next section is that whenever Tz has more than one vertex of minimal indegree (outdegree), then one of these vertices must dominate (b e dominated by) z. W e state this as a separate lemma. Lemma 4.16. Let T be a nonarctraceable strong tournament, and let xy be a nontraceable arc ofT. If 6(T) > 1, then either x is the unique vertex of minimal indegree in Tz or 6(T) = 6(Tz) for the vertex z in Theorem 4 12. Similarly either y is the unique vertex of minimal outdegree in Tz or 6+(T) = 6+(Tz). Proof. As 6(T) > 1 and 6(Tz) 2: 6(T) 1, we conclude that 6(Tz) 2: 1, and the initial and terminal strong components of T z contain at least three vertices. Let R and S be the initial and terminal strong components of Tz respectively and consider Rx and Sy. Vertices of minimal indegree in T z must either be x or in the initial strong component of Rx, and by Lemma 4.13, Rx must dominate z (otherwise any hamiltonian path of Rx and the trivial path x imply that the arc xy is traceable). Thus either 6(Tz) = 6(T) or the only v e rtex with minimal indegree is x In exactly the same way, the terminal strong component 50
PAGE 59
of Sy is dominated by z and so either o +(Tz) = o+(T) or the only vertex of Tz with minimal outdegree is y. 0 4.3 Applications of the structure results Although the structure described above falls short of a complete characterization of nonarctraceable tournaments, it gives a great deal of information about such tournaments. Using this structure, we improv e several of the previous sufficient conditions for arctraceable tournaments as well as improving a result of Volkmann [42] for tournaments with <5 2: 2. Theorem 4.17. IJT is a strong ntournament with o0 2: 2 and d(x) +d+(y) ;:::: 2 for every xy E A(T), then T is arctraceable. Proof. We prove the contrapositive: if T is not arctraceable, then for some arc xy ofT, d(x) + d+(y) < 2. Assume that Tis not arctraceable, with arc xy on no hamiltonian path ofT. Thus, T has the structure given by Theorem 4.12. Let a be the number of vertices in rPl and let b be the number of vertices in Since rPl and rYl) are distinct and nonempty and ITzl = ITI 1 n 2: a+b+3. Choose vertices u of minim a l indegree and v of minimal outdegree from T z Clearly, u E rPl and v E and hence uv is an arc of Tz a nd so also an arc ofT. As o0(Tz) 2: o0(T) 1 > 0, both rPl and contain at least three vertices. Furthermore, if rPl is regular or nearlyregular, then by Lemma 4.16, we can choose u such that dY,(u) = dY,.(u) a;1 Otherwise, dY,(u) < dY,z(u) + 1 a23 + 1 = a;1 Similarly, d:F(v) b;1 Thus dY,(u) + di(v) < a+b2 < nS < .!! 2 completing the proof 2 2 2 0 51
PAGE 60
The above result gives Orelike degree conditions on a tournament that guarantee arctraceability. As an obvious corollary we state the result with Diraclike degree conditions. Corollary 4.18. If T is a strong ntournament with 6 2: 1 > 11 then T is arctraceable. As a consequence of this Diraclike condition we state the result in terms of irregularity, similar to Theorem I. Corollary 4.19. If T is a strong ntournament with 6 > 1 and i(T) :::; + 11 then T is arctraceable. Proof. i(T) = (n1)26, so i(T):::; + 1 implies that (n1)26:::; + 1. Solving for 6, we obtain 6 2: 1. 0 The structure of nonarctraceable tournaments also gives a succinct proof of the following result of Volkmann Theorem L (Volkmann (42]). In a strong tournament T1 every arc ofT is on some path of length at least rntll Proof. If Tis arctraceable then every arc ofT is on a path of length nand the result is immediate. So we may assume that T is not arctraceable, and hence for any arc xy that is not on a hamiltonian path, T has the structure indicated in Theorem 4.12. Let ni be the number of vertices in the ith component of T z Now, let j b e the largest integer less than k such that z is dominated (in T) by som e vertex 52
PAGE 61
in the ;th component of Tz. Note, 2 ::; j < k1 and some vertex in the j + pt component of T z is dominated by z. We can now construct two paths P1 and P2 each containing the arc xy with orders 1 + nk + "Li=l ni and 1 + n1 + "L7=J+l n i, respectively. Thus, the sum of the orders is at least k n1 + nk + 2 + L ni = n 1 + nk + 2 + (n1) 2 n + 3 i=l and one of has order at least rn!3l and hence l ength at l east rn!ll 0 In fact, by combining the above proof and Lemma 4.16 we obtain the following corollary. Corollary 4.20. IfT is a strong ntournament with 1 < o0 ::; 1, then every arc xy is on a path of length at least rn!ll + 25. We present one additional degree condition based on Theorem 4.12, a local condition that is sufficient to guarantee that a given arc is traceable. Theorem 4.21. LetT be a strong tournament with 0 > 1 and let xy E A(T). If d+ (y) > d+ ( x) 4, then xy is traceable. Proof. Assume that xy is nontraceable. Then T has the structure given by Theorem 4.12. Furthermore as 0 > 1, we can choose u1 from TP) such that x dominates u1 and u2 from r;k) such that u2 dominates y. Next, we can choose u3 and u4 from ypl and r;kl), respectively. From the structure of Tz, X dominates ui and ui dominates y for each i 1 ::; i ::; 4 Additionally, x dominates y so have 53
PAGE 62
D Next, we give two results that relate arctraceability to kings in tournaments. A king in a tournament is a vertex that reaches all other vertices via a directed path of length at most two. Tournaments in which every vertex is a king wer e studied in [35] and [8]. The first result, for all tournaments, is sufficient to show that allkings tournaments are arctraceable. Theorem 4.22. If T is an ntournament with n or n 1 kings, th e n T zs arctrac eable. Proof. Assume that T is not arctraceable, and hence has the structure given in Theorem 4.12. Choose v1 and v2 from r;kl) and T;k), respectively and observ8 that for any vertex u E rP)' the shortest path from Vi to u has length at least three. Thus neither v1 nor v2 are kings and soT has at most n2 kings D When S0 > 1, similar techniques give a slightly improved result. Theorem 4.23. If T is a nonarctraceable strong ntournament with S0 > 1, then T has at most n32S+ kings. Proof. Assume that T is nonarctraceable, and let xy be a nontraceable arc ofT. Then T has the structure given by Theorem 4 12, and since c5> 1, TP) has order at least three. As a consequence of Lemma 4.13, there must be some vertex v E T{l) with v z Now for any vertex w E TY) for j > 1 the shortest path from w to v has length at least three. Hence we conclude that the set of kings of T is contained in V (TP)) U { z}. We count the vertices not in this set and find at least one vertex each in TP) and r;kl) and at least 54
PAGE 63
26+(Tz) + 1 vertices in Thus, there are at most n 2 (2t5+(Tz) + 1) kings of T and the proof is complete if 6 +(Tz) = 6+(T). Otherwise since 6 > 1, Lemma 4.16 implies that is not regular or nearly regular, and so must have at least 26+(Tz) + 3 vertices. In this case, we again have at most n2(2t5+(Tz) + 3) = n2(2(t5+(T)1) + 3) = n36+(T) kings in T. D 4.4 Extremal results related to arctraceable tournaments In this section, we use the structure of nonarctraceable strong tournaments to produce some extremal results. First, we fix n and consider the maximum number of nontraceable arcs in a strong ntournament. Later we consider tour naments with m arcdisjoint paths between any two vertices, and we determine the minimal n such that some marcstrong ntournament is not arctraceable. In Chapter 3, we constructed an upset ntournament with non traceable arcs for any odd n, and we proved that this tournament was maximal with respect to the number of nontraceable arcs. We will denote this tour nament Tmax., and recall that this tournament is obtained from the transitive tournament on the set V = {v0 ... Vnl} where d+(vi) = i by reversing the arcs vivi+2 for each even i < n1. We now prove that any strong ntournament T pas at most this number of nontraceable arcs with equality if and only if T is isomorphic to T max. Lemma 4.24. Let T be a strong tournament having a cutvertex z. If X = { x : rPl can not be covered by paths P and Q such that P begins at a vertex dominated by z and Q ends at x}, then lXI ::; a!l, where a= ITP) I Similarly, IYI ::; b!l for the analogous set Y, where b = 1 55
PAGE 64
Proof. Assume that X = { x0 x1 ... xm} If JN+(z) n XI :::: 1 then ass ume that z dominates x0 Let Pi be the longest path not containing xi that begins at a vertex dominated by z. As z dominates x0 or some so me vertex z+ ; X, Pi is a path containing at least one vertex for each i, 1 :::::; i :::::; m. L et Si = V(TPl ) \ for 1 :::::; i :::::; m. We claim first that Si \{xi} dominates V(Pi) Assume otherwise, and let v be the last vertex along such that v dominates w for some w E si \ {Xi} If vis the terminal vertex of Pi, then is a long er path than Pi beginning at a vertex dominated by z. Otherwise, by the minimality of v we can replace the arc vv+ with the 2path vwv+ and again obtain a path that begins at v ertex dominated by z that is longer than Pi. Note, sinc e rPl is strong, Si must be reachable from V(Pi), and thus some vertex of V(Pi) must dominate Xi Choose such a vertex and call it vi Now, let Qi be the longest path of T[Si] that ends at Xi, and l e t ui = Si \ V(Qi) By the definition of X, Ui # 0 for 1 :::::; i :::::; m and Ui c Si \ {xi}, so Ui dominates By a similar argument used above, we also note that Ui is dominated by each vertex of V(Qi) Thus, we conclude that V(Qi) \{xi} dominates both Ui and V(Pi) Additionally observe that the terminal strong component of T[Ui] contains no vertex of X and hence U i \X # 0. To see this, let H be any hamiltonian path of T[Ui] ending at some vertex of X, and construct the paths QiH and Pi, which partition the vertices of rPl. The initial vertex of Pi begins at a vertex dominated by z, and so by definition the t e rminal vert ex of QiH is not in X Since we can choose H so that it ends at any vertex in the te rminal strong component of T[U i], this terminal strong component is disjoint from X 56
PAGE 65
Finally we claim that Uinu1 = 0 for all i =I= j. Assume otherwise, and choose i =I= j with u E ui n uj. Without loss of generality assume that Xi dominates Xj. Since u E ui, and ui dominates u dominates Vi Similarly, as V(Qi) and v ( Q j ) dominate ui n uj' Xi and X j both dominate u. Since Vi does not dominate u and v ( Q j) dominates u Vi :. v ( Q j)' and hence Vi E v ( pj) u uj. Also, since Xi dominates Xj by assumption, and V(Qj) dominates uj, Xi :. uj Fur the r Xi dominates u and uj dominat es V(Pj) so Xi :. V(Pj) Thus, Xi E V(Qj) \ {xj} and so Xi dominates both uj and V(Pj) Since ViE V(Pj)UUj, this requires that xi dominates vi, contradicting the c hoice of vi as a vertex of that dominates The above arguments show that Ui \ X =/= 0 for 1 :::; i :::; m and Ui n Uj = 0 for i =I= j which establishes that (Qu)\x Thus, we have a 2: lXI + m =2m+ 1 = 2IXI 1 and so lXI :::; The bound for the set Y is obtained using an identical argument in the reversal of T. 0 Corollary 4.25. LetT be a strong tournament having the structure given by Theorem 4.12. The number of nontraceable arcs from rP> to r;k) is at most (ab+a:b+l) where a = ITP) I and b = IT;k) j. Proof. Let B be the set of arcs we wish to co unt Define the sets X andY as in Theorem By Lemma 4.13, an arc a= uv is in the set B if and on l y if u EX and v E Y and so IBI = IXIIYI and b y Lemma 4.24, IXIIYI = 0 57
PAGE 66
Theorem 4.26. If T is a strong ntournament, then T has at most n2:n+3 nontraceable arcs with equality if and only if T is isomorphic to T max Proof For n = 3 and n = 4, there is a unique strong ntournament, a nd in both cases this tournament is arctraceable a nd so has at most 0 = J nontraceable arcs, and this tournament is isomorphic to T max. For n > 4, assume that T is nonar ct raceable Let xy be a nontracea bl e arc ofT, and let T have the structure given by Theorem 4.12. Let A = TP ) and B = r;k), with a = !AI and b = IE!, and choose u E TP) and w E r;kl). If a = x'y' is a nontracea ble arc ofT, neither Tx' nor Ty' are strong, and hence x' and y' must both be in the set AU B U { z}. Thus, a is either an arc of T[A U {u, z}], an arc of T[B U {w z}], or an a rc from A to B We claim that every arc of T[AU{ u, z}] or T[Bu{ w, z}] that is nontra cea ble in T is also nontraceabl e in this subtournament. Assume that some arc a is traceable in T[ A U { u, z}], and let P be a hamiltonian path of this tournament containing the arc a. If P ends at a vertex other than z, then for a ny hamiltonian p ath Q of the vertices not on P PQ is a hamiltonian path ofT containing a. On the other hand, u has outdegree one in this subtournament, so if H ends at z it must end with the arc u z. If a is not the arc uz, then we can r e mov e this arc from the end of P to obtain the path P'. Then for any hamiltonian path of the remaining vertices Q such that Q ends at a vertex dominating z P' Q z is a hamiltonian path of T containing a. Finally if a = uz, then we can let P' be any hamiltonian path of TP) beginning at a vertex dominated by z and if Q is any hamiltonian path of the remaining vertices of T z u aP' Q is a h a miltonian path ofT. An identical argument in the rev e rsal of T establishes 58
PAGE 67
the corresponding result for T [ B U { w z } ]. As both of the subtournaments T[A U { u, z }] and T[B U { w, z }] ar e strong, we can apply the induction hypothesis and h e nce T[AU{u, z}] and T[BU{w z}] have at most (a+2f 4(a+2)+3 and (b+ 2 )2 4 (b+ 2)+3 nontraceable arcs with e quality 8 8 if and only if each of these subtournaments are isomorphic to Tmax Summing these two values we obtain a2+f2 Finally, by Corollary 4.25, there are at most nontrac e able arcs from A to B Combining and observing that a + b ::; n 3 the number of nontraceable arcs inTis at most a2 + b2 2 ab + a + b + 1 8 + 4 (a2 + 2ab + b2 ) + 2(a +b) 8 (a+b)2+2(a+b) 8 < (n 3)2 + 2(n3) 8 n 2 6n + 9 + 2n 6 <8 n2 4n + 3 <8 The proof is complete by noting that in the a bove equation, equality is established if and only if n = a+ b + 3 and the subtourname nts T[A U { u, z}] and T[B U {w, z}] are both upset tournaments isomorphic to the appropriat e size T max. From this it follows directly that T is also an upset tourname nt and isomorphic to Tmax 0 As noted earlier a consequence of Theorem 4 7 implies that for a ny nontraceable arc xy in a strong tournament T there exists a y x s e parating set of 59
PAGE 68
X y Figure 4.2: from y to x. A tournament with nontraceable arc xy and two arcdisjoint paths verti ces of order 1 (the vertex z in the theorem) We now show that a similar result for a separating set of arcs is impossible In particular, we show that for any m > 0 there exists a strong tournament T that has a nontraceabl e arc xy with m arcdisjoint paths from y to x. As an example in the tournament in Figure 4.2, xy is not on any hamiltonian path, and there exist 2 arcdisjoint paths from y to x. For convenience, throughout the r e mainder of this ch apter we will let n = 2m+1. For an arbitrary m, we construct a strong tournament b y rev e r s ing the arcs of a set of m arcdisjoint paths in a transitive tourna m e nt of order n + 1. Let T b e a transitive (n + 1)tournament with vertices labeled v0 ... Vn such that d+(vi) = i. Now consider the paths We reverse the arcs in each of these paths to obtain the tournament T[m], and will refer to the reversed path P i as the ith upset path and denote it Ui. Note, V!! 2 is on each Ui, and thus for any i < < j, separates vi a nd v1 Also, observe that w e can vi ew the construction of 1[m+l] re c ur s ively; take two copies of T [m] sharing a single vertex (the terminal e ndpoint of all the up set paths from one copy and the initial endpoint of the upset paths in the other copy) a nd revers e 60
PAGE 69
the 2path Pm+I Lemma 4.27. The arc VnVo is not on any hamiltonian path of the tournament T[m] Proof. For m = 1, Tr1J is an upset tournament on 5 vertices, and it is easy to verify that v5v0 is not on any hamiltonian path of T [ l] Now, assume the result form and consider 'I[m+l] Consider P, a path in 'I[m+l] containing the arc v 2nvo of maximal length, and as T[m+l] is isomorphic to its reversal, without loss of generality assume that Vn precedes v 2 n on P Let Vt be the terminal vertex of P and vi the first vertex of P with index i n. Since Vn separates V a from Vb for each a < n < b every vertex between vi and Vn must have index j < n. Similarly, every vertex between Vn and v 2 n must have index j > n and every vertex following v0 must have index j < n. Thus, all the vertices of P with index j n are contained in the subpaths vi ... Vn and v 0 ... Vt. We now consider the combined sequence of vertices Q = vi, ... Vn, v0 ... Vt. Each of the vertices in this sequence has index j n, and every pair of consecutive vertices other than VnVo are joined by an arc of T[m+l] Since VnVo E A(T[mj), we can use the recursive perspective described earlier and think of this sequence as a path of 'I[m] Since Q contains the arc Vn v0 by the induction hypothesis this can not be a hamiltonian path of T[m], and so there is a vertex Va, a < n that is not in the sequence Q. By the minimality of i Va can not precede vi, and V n separates Va from v2n, so Va can not lie between Vn and v 2 n on P. Hence Va is not on the path P. Consequently the longest path containing the arc v 2nvo is not hamiltonian and v2nVo is nontraceable. D 61
PAGE 70
Thus for any m, we can construct a tournament with n + 1 vertices with a nontraceab le arc xy such that there exist marcdisjoint paths from y to x. Next we show that this is the minimal number of vertices among strong tournaments with this property. Theorem 4.28. 1fT is a strong ktournament containing a nontraceable arc xy such that there exist m arcdisjoint paths from y to x, then k 2:: n + 1 = 2m+1 + 1. Proof. Ag a in, the proof is by induction For m = 1 the result is obtained by observing that the unique strong tournaments on 3 and 4 vertices are arc traceable. Next, assum e the result for m and consider the small est strong ktournament T, with nontraceable arc xy and m + 1 arcdisjoint paths from y to x. Assume that k < 2n + 1 = 2m+2 + 1. As xy is nontraceable, T must have the structure given by Theorem 4.12 Furthermore the minimality of T implies that Tz has exactly four strong com ponents and that the second and third components both consist of a single vertex. L e t X be the set of vertices in the first and second strong co mponents of Tz, and Y = V(Tz) \ X. Clearly either !XI < n or !YI < n. Without loss of generality, assume IX! < nand consider the tournament T[X U { z }]. If zx E A(T) then reverse this arc to form the tournament T'. Otherw ise, simply letT' =T[X U {z}]. Since z is on every path from y to x, and there are m + 1 arcdisjoint paths from y to x, there also exist m + 1 arc disjoint paths from z to x in T and at most one of these contains the a r c z x (if it is an arc ofT). Thus, there are at least m arcdisjoint paths from z to x in T'. Clearly, T' is strong and has fewer than n + 1 vertices and so by the induction hypothesis xz is on some hamiltonian path of this tournament. L et P be such a hamiltonian 62
PAGE 71
path, and split P into two smaller paths P1 consisting of all the vertices up to and including x and P2 consisting of all the vertices of P that follow z. The structure of T' guarantees that both P1 and P2 are paths of order at least 1. The only vertex of T' on neither Pt or P2 is z so each vertex of X is on either P1 or P2 Next, the structure ofT requires that T[Y U {z}] must be strong, so let C be a hamiltonian cycle of this tournament and let Q1 be the subpath of C from y to z inclusive and Q2 the subpath of C from the vertex immediately succeeding z to the vertex immediately preceding y. We allow for the possibility that Q2 may have order 0. Thus, every v e rtex of Y U { z } is on either Q1 or Q2 We now construct H = P1Q1P2Q2 and w e claim that His a hamiltonian path ofT. First, the terminal vertex of P1 is x and the initial vertex of Q1 is y and xy E A(T) by assumption Next the terminal vertex of Q1 is z and the initial vertex of P2 is the vertex immediately following z on P. Lastly, the terminal vertex of P2 is a vertex of X, while the initial vertex of Q2 (if any) is a vertex of Y, and X dominates Y. So, His indeed a path ofT. Tha t His hamiltonian is immediate; it includ e s all of X and Y as well as the vertex z Finally H includes the arc xy. But xy is nontraceable, contradicting our assumption that k < 2n + 1. 0 The previous results apply to a particular arc xy and as a result we make no claim about the number of arcdisjoint paths between e very two vertices. In fact, for each m, T[m] contains a vertex of indegree 1 (v(n1)) as well as a vertex of outdegree 1 ( v1 ) so we have yet to produce even a 2arcs trong tournament that is not arctraceabl e We now seek to construct such an marc strong nonarctraceabl e tournament. Doing so requir e s only a minor variation 63
PAGE 72
on the construction of T[m] Specifically, let T{mJ be a tournament on n + 4m 3 vertices obtained from T[m] by removing the vertices v1 and Vn1 and adding sets U1 and Un_1 each of order 2m 1. Orient the edges incident with vertices of U1 U Un_1 such that T[U1] and T[Un1] are regular tournaments of degree m 1, and Un1 dominates every other vertex of T{mJ except vn, and U1 is dominated by every remaining vertex of T{mJ except Vo. Lemma 4.29. T{mJ is marcstrong. Proof. It suffices to show that v0 both reaches and is reached by every other vertex of T{mJ using m arcdisjoint walks. The result then follows by a variant of Theorem E. To show that each vertex reaches v0 in m different ways, first consider any vertex u E u1 and let N+(u) n u1 = {u1, ... ,Umd Clearly, W; = UU;Vo for 1 :S i :S m 1 and W m = uv0 are marcdisjoint walks from u to vo. Additionally, for any vertex v : U1 W; = vu;v0 for 1 :S i :S m 1 and W m = vuvo are arc disjoint walks from v to v0 To show that v0 reaches every other vertex by m &rcdisjoint walks, we use the set of m upset paths U1 ... Um. Clearly, U1 ... Um are arcdisjoint paths from v0 to Vn To show that v0 reaches every vertex of w E Un1 by m arc disjoint walks, let N(w) n Un_1 = {w1 Wmd and let W; = Uiw;w for 1 :S i :S m1 and Wm = Umw. As above, for v : Un1 U {vn}, let W; = U;w;v for 1 :::; i :::; m 1 and w m = u m wv. 0 Lemma 4.30. The arc VnVo of is nontraceable. 64
PAGE 73
Proof. Assume the result is false so there is some hamiltonian path H of T{mJ that contains the arc VnVo. Since N(u) \ Un_1 = {vn} for any u E Un_1 any path ending at a vertex of Un_1 is either a path of T[Un_ 1], or includes an arc VnW for some w E Un_1 Since H can not contain any of these arcs, every subpath of H ending at a vertex of Un_1 is a path of T[Un_1 ] and hence the first 2m1 vertices of Hare precisely the vertices in the set Un_1 Similarly, every subpath of H beginning at a vertex of U1 is a path of T[U1 ] and hence the last 2m 1 vertices of H are precisely the vertices in U1 Now, the subpath Q of H beginning with first vertex of H not in Un_1 and ending at the lasL vertex of H not in U1 is also a path of T[m] containing VnVo, and this path has order n + 4m 3 ( 4m 2) = n 1. Furthermore, this path cannot begin at the vertex Vn because this vertex is in N+(u) for some u E Un_1 Similarly, the last vertex of Q is in N( w) for some w E U1 so Q does not end at the vertex Vo. Thus, vn1Qv1 is a path of T[m] with order n + 1, and hence VnlQvl is hamiltonian. But this path contains VnVo, contradicting Theorem 4.7 Thus, Vn Vo is nontraceable in T{mJ. D Finally, we conclude this chapter with a proof that T{mJ has the fewest ver tices among all nonarctraceable marcstrong tournaments. Theorem 4.31. If T is a nonarctraceable marcstrong ktoumament, then k 2:: n +4m3. Proof. For m = 1, the result is immediate by observing that all strong tourna ments are 1 arcstrong and that 21+1 4(1) 3 = 5 is the size of the smallest nonarctraceable strong tournament. So we can assume that m 2:: 2 Let xy be 65
PAGE 74
a nontraceable arc ofT. Define Sx as the initial strong component ofTx and Sy as the terminal strong component ofTy. If y E Sx, there would exist a hamiltonian path ofT beginning with the arc xy. So y :. Sx and similarly, x :. Sy. As T is m arcstrong, ;:::: m and ;:::: m 1 for any v E V(T). Thus, 5y._x ;:::: m1 and 5:f_y ;:::: m1 and consequently both ISx l ;:::: 2m1 and ISyl 2: 2m1. Next, we claim that S x n Sy = 0. Assume otherwise, and choose z E S x n Sy. Sinc e z E Sx, it reaches every vertex ofTx, and since y :. Sx, it reaches every vertex of (Tx)y. So z is in the terminal strong component ofTy but the initial strong component ofTyx. As a result, the initial strong component ofTy must be {x}. This requires that 5y._Y = 0 < m1, a contradiction. Lastly, observe that no path from y to x can use any vertex of S x U Sy, as every path from y to Sx must contain the vertex x, and dually every p ath from Sy to x must contain y. Thus w e can form T' by r e placing the entire set S x with a single vertex Ux and replacing the entire set Sy with a single vertex uy without disturbing any path from y to x. Thus, there rem a in marcdisjoint paths from y to x in T'. Furthermore, if we let x dominate Ux and let uy dominate y, the n T' is strong. By a similar argument to the one used in Lemma 4.30, any hamiltonian path of T' containing the arc xy can be extended to a hamiltonian path of T containing this arc. As x y is not on any hamiltonian path ofT by assumption it is therefore not on any hamiltonian path ofT'. By Lemma 4.28, T' has at least n + 1 vertices and soT has at least (n + 1)2 + 2(2m1) = n +4m3 vertices. D 66
PAGE 75
5. Related problems In this concluding chapter, we consider arctraceability in other classes of digraphs related to tournaments, as well as various other ways to generalize arctraceability. We will introduce new definitions and notation as needed. The main result of this chapter will be a characterization of arctraceability in the class of strong rounddecomposable locally semicomplete digraphs. These results are intended to suggest new directions for the investigation of arctraceable digraphs and to propose the study of properties similar to arctraceability that bear further study. 5.1 Semicomplete digraphs A semicomplete digraph is a strict digraph D, such that for every pair of distinct vertices x, y E V(D), either xy E A(D) or yx E A( D) or both. In other words, a semicomplete digraph is any strict digraph that contains a tournament as a spanning subdigraph. As such, we would like to be able to generalize the techniques and results of Chapter 4 in a natural way to obtain results for this class of digraphs. For example, we note that just like tournaments, the condensation D* of a semicomplete digraph D is a transitive tournament. Thus, just as for tourna ments we have the following observation. Proposition 5.1. Let D be a semicomplete digraph. If D is arctraceable, then D is strong or has two strong components D1 and D2, each of which are arc traceable semicomplete digraphs. 67
PAGE 76
Next, we will show that every 2connected semicomplete digraph is arc traceable. The argument used in Chapter 4 for tournaments only uses the fact that strong tournaments are hamiltonian. So our next observation follows by observing that a strong semicomplete digraph is hamiltonian due to Theorem D. Proposition 5.2. Every 2connected semicomplete digraph is arctraceable. Continuing in this way, a careful reading of Lemma 4.3 and Theorem 4.4 shows that these results hold for semicomplete digraphs as well as tournaments. Thus we obtain the same sufficient condition given by Corollary 4.5. Corollary 5.3. If D is a strong semicomplete digraph and every arc of D is on some cycle of length l > n!l, then D is arctraceable. Up to this point, we have obtained exactly the same results for semicomplete digraphs that we did for tournaments. Howe ver an analog of Theorem 4.7 is not quite as immediate. If an arc xy of a semicomplete digraph D is part of a cycle of length two, then it makes no sense to speak of a y, xseparating set and we are not able to use Menger's Theorem. Apart from this difficulty, however, the proof of Theorem 4. 7 remains valid even when other 2cycles remain in the digraph. This yields a result that is only slightly modified Theorem 5.4. Let D be a strong semicomplete digraph and l et xy E A(D) be such that there exist at least two (internally) disjoint paths of l engt h at least two from y to x in D. Then there exists a hamiltonian path of D con taining the arc xy. 68
PAGE 77
As a result of this modification, the structure of a nonarctraceable strong semicomplete digraph is similar but not identical to the structure for tourna ments. To make the analog of Theor e m 4.12 as simple as possible, we define the subdigraph D(uv) of D by V(D(uv)) = V(D) and A(D(uv)) = A(D) \ {uv}. So, in the case where uv rf. A(D), D(uv) = D Certainly, no path including the arc xy can also include the arc yx. Thus, we observe that xy is traceable in D if and only if xy is traceable in D(yx). W e now give the main structure theorem for semicomplete digraphs which is a n amalgam of the semicomplete digraph analogs of Theorem 4.12 and Corollar y 2.2. Theorem 5.5. If D is a strong semi comp lete digraph and xy E A(D) is not on a hamiltonian path then either Dyx has three or more strong components or there exists a vertex z E V(D(yx)) such that: D(yz) z has k 2: 4 strong components. x is in the initial strong component, and y is in the terminal strong com ponent of D(yx)z. z is dom inated by the 2nd strong component and dominates the ( k 1) st strong component of D(yx) z To illustrate Theorem 5.5 we give two nonarctraceable strong semicom plete digraphs in Figure 5.1. The digraph on the l eft has nontraceable arc xy, and the digraph obtained by removing the corresponding arc yx has three strong components. The right hand digraph has the structure similar to non arctraceable strong tournaments, but with the additional arc yx. In both cases additional 2cycles may be present within the components. 69
PAGE 78
Figure 5.1: Two nonarctraceable strong semicomplete digraphs Proceeding in this fashion we can use the slightly modified structure given above to yield results for semicomplete digraphs that closely match the results for tournaments. We illustrate this by giving degree constraints sufficient to guar antee arctraceability. Observe that these conditions differ significantly from the conditions for tournaments because in the strong components of a semicomplete digraph we allow cycles of length two. Theorem 5.6. If D is a strong semicomplet e digraph on n vertices with 6 2: 2, and for every xy E A(D), d(x) + d+(y) 2: n2, then D is arctraceable. Proof. Assume D is not arctraceab le. Then by Theorem 5.5 either D(yx) has three or more strong components or we can find a vertex z as described in the theorem If D(yx) has three or more strong components, then let a and b be the number of vertices in the initial and terminal strong components respectively. Note n 2: a+b+ 1, and since !5> 1 both a and bare at least two. This implies 70
PAGE 79
that we can choose vertices u and v in these components with d[; ( u) :::; a 1 and d1J ( v) :::; b1. It must be the case that u + v and hence we have an arc of If instead, D(yx) has a vertex z as described in Theorem 5.5, let the number of vertices in the first strong component of D(yx)z be a and let b be the number of vertices in the last strong component. This requires that n 2: a+ b + 3, and both a vertex u with d[; (u) :::; a1 and a vertex v with d1J (v) :::; b1. (yx) (yx) Again, it is clear that u + v in D and for this arc, d[; ( u) + d1J ( v) :::; (d[; ( u) + (yx) 1)+(d[;(yx)(u)+1)=a+b=n3. 0 5.2 Round digraphs Another generalization of tournaments in which arctraceability can be considered is the class of digraphs known as local tournaments. A digraph is a local tournament if the subdigraphs induced on N+ ( v) and N( v) are tournaments for every vertex v. Originally introduced as locally semicomplete digraphs in [5], the structure of local tournaments was investigated by Huang in [19]. Our analysis of arctraceable locally semicomplete digraphs begins with a special case of local semicomplete digraphs called round digraphs. A digraph D is said to be round if there is an ordering of V (D) such that N(vi) = { Vij I 1 :::; j:::; d(vi)} and N+(vi) = {vi+j J1:::; j:::; d+(vi)} for each viE V(D) (addition of subscripts is modulo n). The ordering is called a round labeling or round enumeration of the digraph D. We give a few observations about round digraphs in general. Theorem M (Huang [20]). A round digraph is locally semicomplete. 71
PAGE 80
Figure 5.2: A round local tournament with cycles of length two. Proof. Let D be a round digraph with round labeling V(D) = { Vo, ... Vnd If d+(vi) ::; 1, then the outneighborhood of vi is trivially a semicomplete digraph. So for any i such that d+(vi) > 1, choose v 1 and Vk from N+(vi) Without loss of generality, assume that i < j < k. Now since vi E N(vk), the round labeling implies that v1 E N(vk) Thus, every pair of distinct vertices in N+(vi) are adjacent. Similarly, every pair of distinct vertices in N(vi) are adjacent, D is locally semicomplete. 0 Since a semicomplete digraph with no is a tournament, we get a sufficient condition for a round digraph to be a local tournament. Proposition 5. 7. A round digraph with no cycles of length two is a local tournament. The converse of this statement is false however, as shown by the round digraph in Figure 5 2 which is a local tournament despite having a cycle of length two. It is easy to see from the round labeling that any round digraph with c5+ 1 is hamiltonian, since vi + vi+l for each i, 0 ::; i ::; n 1. A similar argument gives a sufficient condition for a round digraph to be arctraceable. 72
PAGE 81
Theorem 5.8. A round digraph D with + 2 is arctraceable Proof. Let D be a round digraph with + 2 and let V(D) = {vo, ... Vn1} b e a round labeling of D. Now choose any arc a= ViVj of D. If j = i + 1, then a is on a hamiltonian cycle, so we may assume that j =I= i + 1. Consider the vertex Vj_1 Since d+(vjd > 2, the round lab e ling r e quires that Vjl + Vj+l and we can construct the hamiltonian path vi+lvi+2 Vj_1vJ+1 vj+2 ... vivj D Before returning to the case of + = 1, we consider nonstrong round di graphs. Clearly these are precisely the round digraphs with + = 0 W e show that such digraphs are acyclic. Lemma 5.9. If D is a round digraph that is not strongly connected, then D is acyclic. Proof. Let D be a round digraph with the usual round labeling, and let C be a directed cycle in this digraph. Then some arc of C must be of the form VjVi with i < j. The round labeling forces N+(vj) {vj+1 ... Vn1, Vo, ... vi} and so we have VjVo E A(D). Again we use the round labeling, which implies that N(v0 ) {vj, ... ,vn 1}. Using the round labeling a third time, we find that N(vi) {vj, ... Vn_1 v0 ... vi_1}. This implies that d+(vk) 1 for 0 :S k < i and j ::; k :=:; n 1 and since vi is on the cycle C, d+ (vi) 1 as well. Now certainly, for any k with i < k < j, C contains some arc Va Vb with a < k < b. Thus, using the round labeling once again, vk E N (vb) and so d+ ( vk) 1 for each i < k < j and hence we have + 1 and D is strong. D As a consequence of the above lemma we observe that a round digraph that is not strongly connected has at most one hamiltonian path. 73
PAGE 82
Proposition 5.10. An acyclic digraph has at most one hamiltonian path Proof. Let H1 = v 1 v 2 Vn be a hamiltonian path of a directed graph D. Then if D contains any other hamiltonian path H2 this path must include an arc v 1 v i with i < j, which implies that vivi+ 1vi+2 v 1 is a cycle of D. 0 Hence, the only arctraceable round digraph that is not strongly connected is a directed path. Proposition 5.11. A round digraph D that is not strongly connected is arctraceable if and only if it is a directed path. To complete our brief analysis of arctraceable round digraphs, we return to the case where + = 1. We proceed in a similar way as we did for upset tournaments; we give necessary and sufficient conditions for a given arc to be traceable. Theorem 5.12. Let D be a strongly connected round digraph with round labeling V = { vo, ... Vn1} An arc vivj is traceable if and only if j = i+ 1, d+(vi1) ?: 2 or d+(vj_ 1 ) ?: 2. Proof. Assume that a = vivj is traceable and j != i + 1. Let H be a hamiltonian path of D containing this arc. Define the sets V1 = { vi+1 vi+2 v12v1d and V2 = {vJ+1Vj+2 vi2Vil} If v;_ 1 precedes a on H, then H must include some arc VaVb with Va E v2 and Vb E v1 Thus, Vi1 E N(vb) and so d+(vi1) ?: 2. Similarly, if vi_ 1 follows the arc a on H, then there is some arc VaVb on H with Va E V1 and Vb E v2 and thus Vj1 E N( Vb) and d+( Vjd 2: 2. For the converse, assume first that j = i + 1. In this case, vivi+1 vi1 is a hamiltonian path containing a. Next, assume that d+(vi_r) 2: 2. Then, 74
PAGE 83
vilvi+l is an arc of D and ViVjVj+ 1 vilvi+1vi+2 VjI is a hamiltonian path of D so long as j =f. i1. In this case, vivjvi+Ivi+2 vi_2 is a hamiltonian path of D Finally, if d+(vj_I) 2: 2 VjIVj+l is an arc of D and thus vi+lvi+2"'VjIVj+l'"ViIViVj i s a hamiltoni a n path of D for j =f. i 1 a nd vi+ I vi+2 vi2vivj is a hamiltonian path othe rwise. D We now take our characterization of traceable arcs and use it to obtain a characterization of arctraceable strong round digraphs R ecall that D (uv) i s the digraph obtained from D by removing the arc uv, if it is prese nt. Theorem 5.13. Let D be a strong round digraph. Then D is arctraceable if and only if D{x, y} is traceable and D (yx) ha s 15+ J+ > 0 for every xy E A(D). Proof. Let V = { vo ... Vnd be a round labeling of D Assum e that D is arctraceable and choose an arbitrary arc vivj E A(D). Thus, by Theorem 5.12 j = i + 1 d+(vi_I) :2: 2 or d+(vj_I) 2: 2. First, we show that D(vjv;) has 15+ J+ > 0 If j =f. i 1, then D(viv;) is hamiltonian, and if j = i 1, then e ither Vjl + vi or Vj + vi+l and so a fter removing the arc VjVi, we still have d+(vj) > 0 or d (vi) > 0. Since the in degree and outdegree of all other v e rtices r e mains unchanged and D is strong, it follows that 15+ & + > 0 in D(vjv;), as desired Next, we show that D{x y} is traceable. If j ::;:: i 1, then let P be the path vi+2vi+3 VnIVo Vi2 Now either Pvi1 or vi+lp is a hamiltonian path of D{x, y}. So w e can assume that j =f. i 1. If d+(vi_I) ;:::: 2 then vi l + vi+ I and vi+1 viI vi+! Vjl is a hamiltonian path of D { x, y}. Similarly if d + (vjd 2: 2 then vi+l Vj 1vi+1 viI is a hamiltoni a n path of 75
PAGE 84
Figure 5.3: A strong nonarctraceable round digraph. D{x,y}. For the converse, assume that D {vi, v1 } is traceable and D(vjv;) has 6+ + 6> 0 for each ViVj E A( D). Let VJ. = { Vi+l> ... Vjd and v2 = { VJ+l, ... Vid, and let H be a hamiltonian path of D {vi v1 } If neither vl nor v2 are empty, then H must contain an arc Va Vb from VJ. to v2 or from v2 to vl Thus, either Vj1 E N(vb) or vi1 E N(vb) and so d+(vj d 2: 2 or d+(vi1) 2: 2. Hence, by Theorem 5.12 ViVj is traceable. If v1 is empty, then j = i + 1 and clearly, ViVj is traceable. Finally if v2 is empty then j = i 1 and either N+ ( v1 ) = {vi} or v1 vi+l Additionally either N(vi) = {vj} or Vj1 As 6+(D(vjv;)) + 6(D(vjv;)) > 0 we must have either v1 Vi+l ot v1 _1 vi. In the former case viVjVi+I VnIVo Vi2 is a hamiltonian path of D containing the arc vivj. Similarly, in the latter case vi+ I vi+2 vn1vov1 v1 _1vivj is a hamiltonian path of D containing the re quired arc. Consequently, vivi is traceable and since this arc was arbitrary, D is arctraceable. D The need for the somewhat awkward "extra" condition on D(yx) in Theorem 5.13 is illustrated in Figure 5.3. The transitive tournament with an additional arc from x toy is strong, with a single nontraceable arc (the arc xy) but the digraph remaining when the vertices incident with this new arc are removed 76
PAGE 85
is certainly traceable. To see that this digraph is round, simply note that the transitive ordering of the original tournament is also a round labelin g of the digraph 5.3 Locally semicomplete digraphs Thrning our attention to locally semicomplete digraphs in general we first consider the case of such digraphs that are not strongly conn ecte d In this case we use a result of BangJ e nsen. Theorem N (BangJensen [5]). If D is a weakly connected (but not strongly connected} locally semicomplete digraph then D*, the condensation of D is an acyclic round digraph and e ach strong component of D is a semicomplete digraph. From this we deduce a result about arctraceability. Corollary 5.14. If D is a weakly connected (but not strongly connected} locally semicomplete digraph then D is arctraceable if and only if eac h $trong compo nent of D i's an arctraceabl e semicomplete digraph and D*, the condensation of D, is a directed path. Once again, this is not quite a characterization, since it relies on a characterization of arctraceable semicomplete digraphs but we do know a great deal about the structure of nonarctrac eable strong semicomplete digraphs from Theorem 5.5 In the case of strong locally semicomplete digr a phs we will focus on the subclass known as round decomposable strong locally semicomplete digraphs. A round decomposition is somewhat more general than the condensation of a 77
PAGE 86
digraph. We will say a strong locally semicomplete digraph D has a round decomposition if there is a round digraph R with order r and the vertices of D can be partitioned into sets 51 ... Sr in onetoone correspondence with the vertices of R such that each Si is a strong semicomplete digraph and that e very vertex in si dominates each vertex in sj whenever the v ertex corresponding to si dominates the vertex corresponding to sj. We note that not all such digraphs have a round decomposition (see [16]). We will consider only those that do here. Round digraphs are certainly round decomposable, as we can simply choose Si = {vi} for each vertex vi We use the techniques and arguments developed for round digraphs to give necessary and sufficient conditions for an arc in this larger class of digraphs to be traceable. Lemma 5.15. Let D be a strong round decomposable locally semicomplete digraph and let S1, ... Sr and R be a round decomposition of D. Then an arc xy E A(D) is nontraceable if and only if for some nontraceable arc WiWj E A(R), si = {x} and sj = {y}. Proof. Let D have the round decomposition specified in the theorem, and let X E Si and y E Sj. If i = j, let Hi be a hamiltonian path of the semicomplete digraph induced on Si \ { x, y} and for k #i, let Hk be a hamiltonian path of the semicomplete digraph induced on Sk. Then xyHi+1Hi+2 HrH1H2 Hi is a hamiltonian path of D that contains the arc xy. If i #j and si #{X} then let Hi be a hamiltonian path of s i \ {X} and let H1 be a hamiltonian path of the strong semicomplete digraph induced on Sj beginning at y. Now, for k #i, j let Hk be any hamiltonian path of Sk and 78
PAGE 87
construct the hamiltonian path xHjHJ+1 HrH1H2 Hjl of D containing the arc xy. Similarly, if si = {X} but sj =I= { y}, we use a similar technique and construct a hamiltonian path H i+1Hi+2 HnHl Hi_1xy. Thus, we can assume that si = { X } and sj = {y}. It remains to show that in this case, xy is traceable in D if and only if WiWj is traceable in R. Clearly if wiwj is traceable in R, the we can choose a hamiltonian path HR containing this arc and replace each vertex wk of this path with a hamiltonian path Hk of Sk and obtain a hamiltonian path of D that contains xy. Conversely, just as in the proof of Theorem 5.12 any hamiltonian path H of D containing xy must contain an arc uv with u E Sk, and v E Sk2 where one of k1, k2 is in the set {j + 1, j + 2 ... i1} and the other is in the set { i + 1 i + 2, ... j 1 }. This forces the arc wilwi+l or the arc WjlWj+l in Rand this arc is sufficient to guarantee that WiWj is traceable in R by Theorem 5.12. 0 This gives us precisely the same characterization of arctraceable strong round decomposable locally semicomplete digraphs that we obtained in the case of round digraphs. Theorem 5.16. Let D b e a strong round decomposable loca lly semicomplete digraph. Then D is arctraceable if and only if D { x, y} is traceable and D(yx) has 6+ 6+ > 0 for every xy E A(D). Proof. The result follows from Theorem 5.15 using the exact sa me argument us e d in the proof in Theorem 5.13. 0 To complete an analysis of all arctraceable locally semicomplete digraphs, such digraphs that are not round decomposable must be considered. This cas e 79
PAGE 88
remains open. Question. Characterize arctraceable locally semicomplete digraphs that are nei ther semicomplete nor round decomposable. 5.4 Other Generalizations In this last section we pose a series of questions that are relat ed to a r c traceability in tournaments. We will suggest other classes of digraphs in which arctraceability could be inv es tigated, and we will consider properties similar to arctraceability. For clarity, we will state eac h problem in the context of all digraphs. Of course, many such questions could be asked. We present only a small sample. Perhaps the most obvious generalization of tournaments not already dis cussed is the class of multipartite tournaments A multipartite tournament is an orientation of a complete multipartite graph. Question. Characterize arctraceabZ,e multipartite tournaments. Another possibility is to look at directed graphs which fall just short of tournaments. For exa mple, digraphs with at most one pair of nonadjacent vertices. Question. Characterize arctraceable digraphs whose underlying graph is Kn e. G e neralizing the idea of arctraceability itself, we arrive at a fundamental question: Given any substructure S, what digraphs D hav e a hamiltonian path containing S for each S in D? We briefly consider a f e w choices for the structure S. 80
PAGE 89
Question. Characterize digraphs D that contain a hamiltonian path containing S for each S in D where S is: A path of length k, k 2: 2. k vertex disjoint arcs, in any order. An ordered set of k vertex disjoint arcs A linear forest with possibly additional restrictions. We can also generalize the "traceable" part of arctraceable. Inst ead of requiring a single spanning path, we can see k digraphs with a lin ea r factorization containing the desired structure. Such a generalization may be necessary to make significant progress on these stronger conditions as there remain many open questions even in the case of arctraceable digraphs. One might also con sider factorizations containing the given structure that consist of both paths and cycles. Path:c ycle ff:Lctorizations of semicomplete multipartite digraphs have been studied by BangJensen, Huang, Gutin and Yeo (for an overview of these results, we suggest [6] and for specific references, [7] and [17]). 81
PAGE 90
REFERENCES [1] B. Alspach. Cycles of eac h length in regular tournaments. Canad Math Bull. 10:283286 1967 [2] K. T. Balin s ka M. L Garg a no and L. V Quintas An e d g e parti t ion problem concerning h a milton paths. Congres s us Numerantium, 152:4554, 2001. [3] K. T. Balinska, M L Gargano, L. V. Quint a s and K. T. Zwi e rzynski. Graphs with nontraceable edges. Compute r Science Center R ep ort 485, The T e chinical Univ e rsity of Poznan 2002. [4] K. T. Balinska M L. Gargano, L. V. Quint as, and K. T. Zwie rz y nski. Extremal size probl e ms for graphs with n o ntraceable edg es. Con gr ess us Nume rantium, 162:55 64 2003. [5] J BangJensen. Locally semicomplete digraphs: a generalization o f tourname nts. J. Graph Th e ory 14:371390, 1990 [6] J B a ngJensen and G Gutin. Digraphs : Th e ory Algorithms and Appl icat i ons SpringerVerl a g 2001. [7] J. BangJensen, G Gutin, and J. Huang. A s ufficient condition for a se mi complete multipartite digraph to be hamiltoni a n Discrete Math 161: 1 12, 1996. [8] M F. Bridgland and K.B. Reid. Stability of kings in tourname nt s In Progress in graph th e ory {Waterloo, Ont. 1982 ) pages 117128 A ca d e mic Press 1984. [9] R. A. Brualdi and Q. Li. The interchange graph of tournaments wit h the same score vector. In Proceeding in graph th e ory (Waterloo Ont 1982), pages 129151. Academic Press, 1984. [10] G. Chartrand and L L e sniak. Graphs and D i graphs. Chapman a nd Hall 1996. [11] G A Dirac. Some theorems on abstrac t graphs Proc. London Math So c 2:6981 1952. 82
PAGE 91
[12] J.D. Foulkes. Directed graphs and assembly schedules. In Proc. Symp. Appl. Math., pages 218289. Amer. Math. Soc., 1960. [13] A. GhouliaHouri. Une condition suffisante d existence d un circuit hamil tonien. C. R. Adac. Sci Paris, 156:495497, 1960. [14] M. C. Golumbic Algorithmic Graph Th e ory and Perfect Graphs. Academic Press, 1980. [15] R.J. Gould. Advances on the hamiltonian problem a surv ey. Graphs Combin 1:752, 2003. [16] Y. Guo. Strongly Hamiltonianconnected loc ally semic ompl e t e digraphs PhD thesis, RWTH Aachen, 1995. [17] G. Gutin and A. Yeo. Note on the path covering number of a se micomplet e multipartite digraph. J. Combin. Math. and Combin. Computing, 32:231 237, 2000. [18] F. Harary and L. Moser. The theory of round robin tourname nts. Amer. Math. Monthly, 73:231 246, 1966. [19] J. Huang. On the structure of local tournaments. J. Combin. Theory Ser. B, 63:200221, 1995. [20] J. Huang. Which digraphs are round? Australas. J. Combin., 19:203 208 1999. (21] 0. S. Jakobsen Cycles and Paths in Tournaments. PhD thesis, University of Aarhus, 1972. [22] T. Koshy Fibonacci and Lucas Numbers with Appli c ations John Wiley and Sons, 2001. [23] H. G. Landau. On dominance relations and the structure of animal societies, iii: The condition for score structure. Bull. Math. Biophys 15:143148, 1953. [24] J. R. Lundgren and D. J. Sie wart. Boolean rank of upset tournament matrices. Manuscript. (25] K. Menger. Zur allgemeinen kurventheorie. Fund. Math., 10:95 115, 1927. [26] H. Meyniel. Un e condition suffisante d'existence d'un circuit hamiltoni e n dans un graph oriente. J Combin. Theory Ser. B 14 : 137147 1973. 83
PAGE 92
[27] J. W. Moon. Topics in Tournaments. Holt, Rinehart and Winston, 1968. [28] J. W. Moon. The minimum number of spanning paths in a strong tourna ment. Publ Math. Debr ecen, 19:101104 1972 (29] J.W. Moon. On subtournaments of a tournament. Canad. Math. Bull. 9:297301, 1966. [30] 0 Ore. Note on hamiltonian circuits. Amer. Math. Monthly, 67:55 1960. [31] J L. Poet and B. L. Shader. Score certificate numbers of upset tourna ments. Discrete Appli ed Mathematics, 103:177 189 2000. (32] L Redei. Ein kombinatorischer satz. Acta Litt. Szeged, 7:3943, 1934. (33] K. B. Reid. Tournaments. In J .L. Gross and J. Yell en, editors, Th e Handbook of Graph Theory pages 156 184. CRC Press 2004 [34] K.B. Reid. Prive communication (35] K.B Reid Tournaments with prescribed numbers of kings and serfs Congr. Numer., 29:809 826, 1980. Proceedings of the Eleventh Southeast ern Conference on Comibinatorics, Graph The ory and Computing (Florida Atlantic Univ., Boca Raton, FL 1980), Vol. II. (36] F S Robers Discr e te Mathematical Models Prentice Hall, 1976. [37] N J. A. Sloane. The online encyclopedia of integer sequences. published electronically at http:/ jwww.research.att.com/ njas/sequences/. A000213. [38] C. Thomassen. Hamiltonianconnected tournaments. J. Combin. Thoery Ser. B, 28:142163, 1980. (39] C. Thomassen. On the number of hamiltonian cycles in tournaments. Dis cre te Math. 31:315 323, 1980. [40] C. Thomassen. Edgedisjoint h a miltonian paths and cycles in tournaments Proc. London Math. Soc. (3), 45:151168, 1982. [41] F. Tian, Z.S. Wu, and C.Q. Zhang. Cycles of each l ength in tournaments. J. Combin. Theory Ser. B, 33:245255, 1982. [42] L. Volkmann. Longest paths through an arc in strong sem icompl ete multipartite digraphs. Dis cre te Math., 258:331 337, 2002. 84
PAGE 93
[43] D.R. Woodall. Sufficient conditions for circuits in graphs. Proc. Lond. Math. Soc., 24:739755 1972. 85

