Citation
Arc-traceable tournaments

Material Information

Title:
Arc-traceable tournaments
Creator:
Busch, Arthur H
Publication Date:
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 )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 82-85).
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
ARC-TRACEABLE 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)
Arc-traceable Tournaments
Thesis directed by Professor Michael S. Jacobson
ABSTRACT
A tournament T is arc-traceable when each arc of the tournament is a part
of a hamiltonian path. We characterize arc-traceable upset tournaments and
show that this property is independent of the number of hamiltonian paths in
such tournaments. We show that non-arc-traceable tournaments have a specific
structure, and give several sufficient conditions for strong tournaments to be arc-
traceable, including Dirac-like minimum degree conditions, Ore-like conditions,
and irregularity conditions. In each case, we show that the result is best possible.
Next, we give some extremal results for arc-traceable 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 fc-arc-strong tournament that is
not arc-traceable. Finally, we also consider the arc-traceable 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 Arc-traceable upset tournaments ................................... 23
3.2 Counting Hamiltonian Paths in Upset Tournaments.................... 28
4. Arc-traceability in all strong tournaments......................... 39
4.1 Observations on arc-traceability in tournaments.................... 39
4.2 The structure of non-arc-traceable tournaments..................... 45
4.3 Applications of the structure results.............................. 51
4.4 Extremal results related to arc-traceable 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 arc-pancyclic........................ 16
2.2 The two families of arc-3-cyclic tournaments that are not arc-pancyclic. 16
2.3 A hamiltonian digraph that is not arc-traceable...................... 18
3.1 An 11-tournament with 10 non-traceable arcs.......................... 26
3.2 Two 8-tournaments.................................................... 34
4.1 An arc-traceable tournament.......................................... 47
4.2 A tournament with non-traceable arc xy and two arc-disjoint paths from
y to x.............................................................. 60
5.1 Two non-arc-traceable strong semicomplete digraphs................... 70
5.2 A round local tournament with cycles of length two................... 72
5.3 A strong non-arc-traceable 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 arc-traceable; an
arc-traceable 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 arc-traceability
in the sub-class of digraphs known as tournaments. Tournaments have additional
structure that, in many cases, can be shown to guarantee arc-traceability. We use
this additional structure to investigate tournaments that are not arc-traceable.
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 arc-traceable. This necessary condition is used to
show that the study of arc-traceable tournaments can be restricted to studying
arc-traceable strong tournaments.
1


Initially, we consider the question in the context of a sub-class of strong
tournaments known as upset tournaments, and in Chapter 3, we give a charac-
terization of arc-traceable 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 non-traceable). We also develop some
techniques to demonstrate that arc-traceability is independent of the number of
hamiltonian paths in upset tournaments. In other words, arc-traceability in a
tournament is not merely a consequence of having many hamiltonian paths.
In Chapter 4, we broaden the investigation of arc-traceability to all strong
tournaments. We begin with some simple observations about sufficient condi-
tions for a strong tournament to be arc-traceable. From these basic observa-
tions, we then develop some necessary conditions for a strong tournament to be
non-arc-traceable. These conditions, in turn, yield many new and improved suf-
ficient conditions for arc-traceable tournaments, and a structure that we use to
construct minimal non-arc-traceable tournaments with many arc-disjoint paths
between every pair of vertices. We also use the structure of non-arc-traceable
tournaments to determine the maximal number of non-traceable arcs in a strong
n-tournament.
In Chapter 5, we briefly consider arc-traceability for digraphs in general. We
investigate arc-traceability in two classes of digraphs that include tournametns,
semicomplete digraphs and local tournaments. We also briefly consider some
questions closely related to arc-traceability 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 out-neighborhood 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 out-degree (d+(u)) and in-degree (d~(v)) are defined as |A+(u)| and
|-/V_(u)|, respectively. Similar to graphs, we then let h+ ( degree (in-degree) and A+ (A-) be the largest out-degree (in-degree) 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 non-adjacent vertices u and v, then G is hamiltonian.
We note that for strict digraphs, an analogue of Theorem A was given by
Ghouila-Houri.
Theorem C (Ghoila-Houri [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 cut-set of D. When D[S] is
strong for all sets S with |Sj > \V\ (d 1), we say that D is d-connected and
we define k(D) to be the smallest d such that D is d-connected. Analogously,
if D' = (V, T) is not strongly connected for some T C A, then A \ T is called
an arc cut-set, 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
k-arc-connected or k-arc-strong whenever k < k'(D). The digraph in Figure 1.2
is 2-arc-strong; 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 2-connected, however, since removing the vertex x leaves no
path from u to v.
When two distinct non-adjacent vertices x and y are specified, an x,y-
separating-set is a set S of vertices such that every path from x to y contains
at least one vertex of S. Similarly, an x, y-separating-set 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 non-adjacent). In both cases, it is
easy to see that when there exist m paths from x to y that are internally vertex
disjoint (arc-disjoint) 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
non-adjacent vertices of D. The number of internally vertex disjoint paths from
7


x to y equals the size of the smallest x,y-separating set. Similarly, for any
distinct (possibly adjacent) vertices x and y, the number of arc-disjoint paths
from x to y equals the size of the smallest x, y-separating 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 n-tournament
when IV(T)! = n. It is often helpful to think of an n-tournament as an orien-
tation of the complete graph Kn. From this perspective, it is immediate that
a tournament has no self-loops 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 8-tournament 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 n-tournament 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 |A||5| 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 out-degrees 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 out-degree 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 out-degree either | or | 1. Such tournaments are
called near-regular or almost-regular.
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 non-decreasing 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 non-decreasing 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 anti-symmetric 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 non-upset arcs when these arcs are of particular interest (to highlight
non-traceable 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
non-trivial components of the tournament with large circles or ellipses, often
without specifying the internal structure of these strong components. Further-
more, using a top-to-bottom or left-to-right 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 sub-class 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
non-trivial 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 vertex-pancyclic.
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 arc-k-cyclic, and if a
tournament is arc-A-cyclic for each possible A, (in other words, for 3 < k < n),
then the tournament is called arc-pancyclic. In the special case where k = n,
we will say a tournament is arc-hamiltonian rather than arc-n-cyclic. Alspach
[1] initially showed that every regular tournament is arc-pancyclic. Jakobsen
[21] studied near-regular tournaments and found that while not necessarily arc-
pancyclic, for n > 8, such tournaments are arc-A-cyclic for each A, 4 < k <
n. In 1980, Thomassen [38] showed that every 3-connected tournament is arc-
pancyclic and that there are infinitely many 2-connected tournaments that are
not arc-hamiltonian (and hence, not arc-pancyclic). Thomassen was also able
to give a sufficient condition for almost arc-pancyclic tournaments based on
irregularity.
Theorem I. Thomassen [38] IfT is an n-tournament with i(T) < then T
is k- arc-cyclic for 4 < k < n
As regular and near-regular 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 arc-pancyclic
Figure 2.2: The two families of arc-3-cyclic tournaments that are not arc-
pancyclic.
and Jakobsen.
For k = 3, Moon [27] was able to show that nearly all tournaments are
arc-3-cyclic. This last result was then used by Tian, Wu and Zhang to aid in
characterizing arc-pancyclic tournaments. They showed the following:
Theorem J (Tian, Wu and Zhang [41]). An arc-3-cyclic tournament is
arc-pancyclic 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
non-strong 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 arc-traceable to
describe digraphs with this property. In this undirected context, it was shown
that every hamiltonian graph is edge-traceable (called totally-traceable in [2],
[3] and [4]). Since hamiltonian graphs are extensively studied, this gives a
great deal of information about edge-traceable graphs. In the directed case,
examples abound which show that hamiltonicity is not sufficient to guarantee
arc-traceability. One such example is shown in Figure 2.3.
The lack of a well known sufficient condition for a digraph to be arc-traceable
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 arc-traceable.
Theorem 2.1. If D is an arc-traceable digraph, then D*, the condensation of
D is a path.
Proof Let D be an arc-traceable 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 arc-traceable, 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 in-degree 0. Label such a
vertex v\. Now D* {u*} is also acyclic, and so this subgraph also has at least
one vertex of in-degree 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
in-degree 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 Bang-Jensen 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 arc-traceable, 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 arc-traceable 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 arc-traceable, 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 arc-traceable. However, we can use the
hamiltonicity of strong tournaments to observe that the analysis of arc-traceable
tournaments reduces to the study of arc-traceable strong tournaments.
Corollary 2.3. A tournament T with two strong components is arc-traceable
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 arc-traceable 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 arc-traceable, then each arc within these
subtournaments is also traceable in T. To conclude that T is arc-traceable, 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 in-degree
zero) to the sink (i.e. vertex of out-degree 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 n-tournament, 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 out-degree one to a vertex of in-degree 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 out-degree
one and let v and v' be vertices with in-degree 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 in-degree 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 out-degree one to a vertex of in-degree
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 n-tournament 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 n-tournament 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 out-degree 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 Arc-traceable upset tournaments
We now address the question of arc-traceability 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 non-traceable 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 Vk-i 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 VkVk-i 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 T-2 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 vk-i 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 vk-i 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 arc-traceable upset tournaments
with six or more vertices.
Corollary 3.3. An upset tournament T on n > 6 vertices is arc-traceable if
and only if for every vertex vk on the interior of the upset path, either vk-i 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 11-tournament with 10 non-traceable arcs
implies that there is no arc that is non-traceable, i.e. T is arc-traceable. 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 arc-traceable, 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 non-isomorphic 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 arc-traceable.
Next, we describe an upset tournament with many non-traceable 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 vnvn-2Vn~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 non-traceable arcs
starting at vertex Vi. Summing all possible values of j, we obtain
n 5
£(
3=0
n

- 4n + 3
non-traceable 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
non-traceable arcs among all upset n-tournaments.
Theorem 3.5. An upset n-tournament T, n > 5, has at most
n2 4n + 3 1 /n\ 3(n 1)
8 4 V2) 8
non-traceable 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 arc-traceable, 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


non-traceable 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
non-traceable in T.
All that remains is to count the non-traceable arcs of T that are not arcs
of T\. Clearly, no arc incident with the vertices u2,... ,Vi-1 is non-traceable
so any non-traceable 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
non-traceable. Let j be the largest index such that the arc v\Vj is non-traceable.
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 arc-traceability
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, arc-traceable upset tournaments have
more hamiltonian paths than non-arc-traceable 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 n-tournament 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 Vj-i to vs in T as well as on every path from vt to
Vj-1. 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 n-tournament 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 n-tournaments 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 non-arc-traceable
by Corollary 3.3.
33


i
Figure 3.2: Two 8-tournaments
We can now use the above results to show that the first 8-tournament shown
in Figure 3.2 has precisely 2(5) (5) 1 = 49 hamiltonian paths and by Corollary
3.3 is arc-traceable. Similarly, the second 8-tournament shown in Figure 3.2 is
non-arc-traceable 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 v-jv^v^vi,
which is isomorphic to the upset tournament with upset path v-jv^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 arc-traceable 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 arc-traceable upset n-tournament with k hamiltonian paths, and V
is a non-arc-traceable upset n-tournament with k! > k hamiltonian paths, then
n > 8.
We now consider the family of upset n-tournaments 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 n-tournament. We show that the the
number of hamiltonian paths of such an n-tournament 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 i-vertices 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 v-deletable 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 = pn-1 + Pn-2 +Pn-3 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 Sn-i 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
vn-i 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
Tn-2, 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 Sn-3.
show that each path P of Wnj must end with the subpath vn^vn-ivn-2vn.
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 vn-i 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
vn-2VnVn-i- 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+(vn-1) = {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 arc-traceable 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 n-tournament
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 non-arc-
traceable upset tournament T with upset path vnv^ni^vi has more distinct
hamiltonian paths than the arc-traceable upset tournament T' with upset path
vnvn_i... v\, and pt Pt> grows exponentially with n.
38


4. Arc-traceability in all strong tournaments
In this chapter we turn our attention to arc-traceability 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 arc-traceable strong
tournaments. However, we will develop a specific structure that is shared by all
non-arc-traceable strong tournaments, and we will use this structure to obtain
many sufficient conditions for strong tournaments to be arc-traceable and to
yield some extremal results for non-arc-traceable tournaments.
4.1 Observations on arc-traceability 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 non-traceable
arcs of a tournament must join two cut vertices.
Proposition 4.1. IfT is a strong tournament and v is not a cut-vertex ofT,
then every arc incident with v is on a hamiltonian path.
This gives us our first sufficient condition for arc-traceable tournaments; if
T has no cut vertices, then T has no non-traceable arcs.
Corollary 4.2. IfT is 2-connected, then T is arc-traceable.
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 n-tournament, 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\ Ui-iWi-i 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 arc-traceable.
Corollary 4.5. IfT is a strong tournament and every arc ofT is on some cycle
of length l > then T is arc-traceable.
We now consider again our observation above that every 2-connected tour-
nament is arc-traceable. If a tournament is two-connected (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 re-state 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


arc-traceable.
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 arc-traceable tournaments are closely
related, and follow from the fact that all 2-connected 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 arc-traceable.
Proof. We prove that the condition guarantees that T is 2-connected. 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 in-degree at most and a vertex with
out-degree at most Thus,
25{T) < S+(T)+5~(T) < 5+(T-v)+5-{T-v)+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 arc-traceable.
Proof. The proof is the same as for Corollary 4.9, combined with the additional
observation that the vertex u with in-degree at most in T v dominates the
vertex w with out-degree 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
arc-traceable.
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) <(n-l)-^ = ^.
4.2 The structure of non-arc-traceable tournaments
Since the results of the previous section are really based on the observa-
tion that every two-connected tournament is arc-traceable, Theorem 4.7 has
not yet proven useful in the study of arc-traceable tournaments. However, the
contrapositive of Theorem 4.7 can be used to obtain some important necessary
conditions for non-arc-traceable 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, x-separating 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 Pk-iP'k, a hamiltonian path of T containing xy. Hence, there
46


Figure 4.1: An arc-traceable 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 arc-traceable. However, such a structure is not sufficient to guarantee non-
j arc-traceability. For example, the arc-traceable tournament in Figure 4.1 has
the structure indicated in Theorem 4.12.
In an attempt to complete a characterization of arc-traceable tournaments,
| we consider whether additional structure imposed on the first and last strong
I
j components of T z is sufficient to guarantee non-arc-traceability.
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
non-arc-traceability in strong tournaments.
Corollary 4.14. Let T be a strong tournament having the structure given by
Theorem 4-12. If \N+(z) D T^\ = 1 and |jV~(z) n | = 1, then T is not
arc-traceable.
Proof. Let N+(z) D = {x} and N~(z) H = {y}. Then by Lemma 4.13,
xy is non-traceable.
Note that the converse of this corollary is false, as the tournament in Figure
4.1 is not arc-traceable.
At this point it appears we have characterized arc-traceable 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 4-12. 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 arc-traceable if and only if some other related tournaments
Rx and Rk are not arc-traceable. For this reason, we generally will find it easier
to use the incomplete results of Theorem 4.12 to produce sufficient conditions
for arc-traceable tournaments (and conversely, necessary conditions for non-arc-
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 in-degree (out-degree), 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 non-arc-traceable strong tournament, and let xy be
a non-traceable arc of T. If 5 (T) > 1, then either x is the unique vertex
of minimal in-degree in Tz or 8~(T) = 8~(TZ) for the vertex z in Theorem
4-12. Similarly, either y is the unique vertex of minimal out-degree 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 in-degree 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 in-degree 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 out-degree is y.
4.3 Applications of the structure results
Although the structure described above falls short of a complete character-
ization of non-arc-traceable tournaments, it gives a great deal of information
about such tournaments. Using this structure, we improve several of the pre-
vious sufficient conditions for arc-traceable 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 arc-traceable.
Proof. We prove the contrapositive: if T is not arc-traceable, then for some arc
xy of T, d~(x) + d+(y) < | 2. Assume that T is not arc-traceable, 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 non-empty and \TZ\ \T\ 1,
n > a+b-(-3. Choose vertices u of minimal in-degree and v of minimal out-degree
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 nearly-regular, 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 Ore-like degree conditions on a tournament that
guarantee arc-traceability. As an obvious corollary we state the result with
Dirac-like degree conditions.
Corollary 4.18. IfT is a strong n-tournament with 5 > ^ 1 > 1, then T is
arc-traceable.
As a consequence of this Dirac-like condition, we state the result in terms
of irregularity, similar to Theorem I.
Corollary 4.19. IfT is a strong n-tournament with 5 > 1 and i(T) < | + 1,
then T is arc-traceable.
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 non-arc-traceable 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 arc-traceable, 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 arc-traceable, 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 n-tournament 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 non-traceable. 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 arc-traceability 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 all-kings tournaments are arc-traceable.
Theorem 4.22. If T is an n-tournament with n or n 1 kings, then T is
arc-traceable.
Proof. Assume that T is not arc-traceable, 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 non-arc-traceable strong n-tournament with <5 > 1,
then T has at most n 3 2S+ kings.
Proof. Assume that T is non-arc-traceable, and let xy be a non-traceable 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) = n-3- <5+(T) kings in
T.
4.4 Extremal results related to arc-traceable tournaments
In this section, we use the structure of non-arc-traceable strong tournaments
to produce some extremal results. First, we fix n and consider the maximum
number of non-traceable arcs in a strong n-tournament. Later, we consider tour-
naments with m arc-disjoint paths between any two vertices, and we determine
the minimal n such that some m-arc-strong n-tournament is not arc-traceable.
In Chapter 3, we constructed an upset n-tournament 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 non-traceable 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 n-tournament T
has at most this number of non-traceable arcs with equality if and only if T is
isomorphic to Tmax.
Lemma 4.24. Let T be a strong tournament having a cut-vertex 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 2-path 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 = |X|-l.
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 4-12. The number of non-traceable 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| = |X||T| and by Lemma 4.24, |JA||y| = AtlALtll
57


Theorem 4.26. If T is a strong n-tournament, then T has at most 4k
non-traceable arcs, with equality if and only ifT is isomorphic to Tmax.
Proof For n = 3 and n 4, there is a unique strong n-tournament, and in
both cases this tournament is arc-traceable and so has at most 0 = |_4 ~F4)+3j
non-traceable arcs, and this tournament is isomorphic to Tmax.
For n > 4, assume that T is non-arc-traceable. Let xy be a non-traceable
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 non-traceable 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 non-traceable
in T is also non-traceable 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 out-degree 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 non-traceable 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) n0n-traceable arcs
from A to B. Combining and observing that a + b < n 3, the number of
non-traceable 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 non-traceable arc xy and two arc-disjoint 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 non-traceable arc xy
with m arc-disjoint 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 arc-disjoint
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 arc-disjoint 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,-2-2)V(n-3.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 7|m]
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 2-path 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 non-traceable.
61


Thus for any m, we can construct a tournament with n + 1 vertices with a
non-traceable arc xy such that there exist m arc-disjoint 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 k-tournament containing a non-traceable arc xy
such that there exist m arc-disjoint 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 non-traceable arc xy and m + 1 arc-disjoint paths from y
to x. Assume that k < 2n + 1 = 2m+2 + 1.
As xy is non-traceable, 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
arc-disjoint 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 arc-disjoint 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 non-traceable, 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 arc-disjoint paths between every two vertices.
In fact, for each rn, 7]m] contains a vertex of in-degree 1 (i>(_i)) as well as
a vertex of out-degree 1 (iq), so we have yet to produce even a 2-arc-strong
tournament that is not arc-traceable. We now seek to construct such an m-arc-
strong non-arc-traceable 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[Un-i] 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 m-arc-strong.
Proof. It suffices to show that v0 both reaches and is reached by every other
vertex of Tj'mj using m arc-disjoint 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 arc-disjoint 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 arc-disjoint walks, we use
the set of m upset paths Ui,... Um. Clearly, Lfi,..., Um are arc-disjoint 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\,... wm-i} 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 non-traceable.
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[Un-1], 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 Un-1 is a path of T[Un-1] 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 Un-1 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 7|m] with order n + 1, and hence vn-\Qvx
is hamiltonian. But this path contains vnvo, contradicting Theorem 4.7. Thus,
vnVQ is non-traceable in 7j'mj,
Finally, we conclude this chapter with a proof that Tj'TO] has the fewest ver-
tices among all non-arc-traceable m-arc-strong tournaments.
Theorem 4.31. If T is a non-arc-traceable m-arc-strong k-toumament, then
k > n + 4m 3.
Proof. For m = 1, the result is immediate by observing that all strong tourna-
ments are 1 arc-strong and that 21+1 4(1) 3 = 5 is the size of the smallest
non-arc-traceable strong tournament. So we can assume that m > 2. Let xy be
65


a non-traceable 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 arc-strong, 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 arc-disjoint 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 arc-traceability in other classes of
digraphs related to tournaments, as well as various other ways to generalize
arc-traceability. We will introduce new definitions and notation as needed. The
main result of this chapter will be a characterization of arc-traceability in the
class of strong round-decomposable locally semicomplete digraphs. These results
are intended to suggest new directions for the investigation of arc-traceable
digraphs and to propose the study of properties similar to arc-traceability 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 arc-traceable, 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 2-connected 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 2-connected semicomplete digraph is arc-traceable.
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 arc-traceable.
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, x-separating 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 2-cycles 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 non-arc-traceable 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 non-arc-traceable strong semicom-
plete digraphs in Figure 5.1. The digraph on the left has non-traceable 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-
arc-traceable strong tournaments, but with the additional arc yx. In both cases,
additional 2-cycles may be present within the components.
69


s
I
;
i
i
Figure 5.1: Two non-arc-traceable 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 arc-traceability. 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 arc-traceable.
Proof. Assume D is not arc-traceable. 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 = n-3.
5.2 Round digraphs
Another generalization of tournaments in which arc-traceability 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 arc-traceable 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 out-neighborhood 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 2-cycles 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 arc-traceable.
72


Theorem 5.8. A round digraph D with 5+ > 2 is arc-traceable.
Proof. Let D be a round digraph with 5+ > 2, and let V(D) = {u0,..., vn-i}
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
Vj-1- Since d+(vj-1) > 2, the round labeling requires that v3-1 > vj+i and we
can construct the hamiltonian path vi+\vi+2 Vj-iVj+\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 arc-traceable 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 arc-traceable 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+(vj-1) > 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 -Vj-2Vj-1} and
V2 = {vj+\Vj+2 If Vi-1 precedes a on H, then H must include some
arc vaVb with va G V2 and Vb G V\. Thus, Vi-X G N~(vb) and so d+(vi-1) > 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 Vj-X G N~(vb) and d+{vj-1) > 2.
For the converse, assume first that j = i + 1. In this case, ViVi+1 vl-X
is a hamiltonian path containing a. Next, assume that d+(vi-X) > 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 -fi-2 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 Vi-iViVj is a hamiltonian path of D for j ^ i 1 and
vi+\vi+2 Vi-2ViVj is a hamiltonian path otherwise.
We now take our characterization of traceable arcs and use it to obtain a
characterization of arc-traceable 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 arc-traceable 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
arc-traceable 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 out-degree 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
Vi-i > vi+x and Vj+1 Vi-ifi+i Vj-1 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 non-arc-traceable 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,... ,Vj-1} 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+(vj-1) > 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 Vj-1 > As 8+(D(VjVi)) + 8~(D{VjVi)) > 0, we must have
either Vj > vi+x or Vj-X > Uj. In the former case, ViVjVi+1 vu-iVq Vi-2 is
a hamiltonian path of D containing the arc vzVj. Similarly, in the latter case
Vi+\Vi+2 vn-\VQV\ Vj-iVjVj is a hamiltonian path of D containing the re-
quired arc. Consequently, ViVj is traceable and since this arc was arbitrary, D
is arc-traceable.
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 non-traceable 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 Bang-Jensen.
Theorem N (Bang-Jensen [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 arc-traceability.
Corollary 5.14. If D is a weakly connected (but not strongly connected) locally
semicomplete digraph, then D is arc-traceable if and only if each strong compo-
nent of D is an arc-traceable 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 arc-traceable semicomplete digraphs, but we do know a great
deal about the structure of non-arc-traceable strong semicomplete digraphs from
Theorem 5.5.
In the case of strong locally semicomplete digraphs, we will focus on the
sub-class 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 one-to-one 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 non-traceable if and only if for some non-traceable 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 Wi-iwi+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 arc-traceable 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 arc-traceable 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 arc-traceable locally semicomplete digraphs,
such digraphs that are not round decomposable must be considered. This case
79


remains open.
Question. Characterize arc-traceable 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
arc-traceability could be investigated, and we will consider properties similar
to arc-traceability. 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 arc-traceable 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 non-adjacent
vertices.
Question. Characterize arc-traceable digraphs whose underlying graph is Kne.
Generalizing the idea of arc-traceability 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 arc-traceable. 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 arc-traceable digraphs. One might also consider
factorizations containing the given structure that consist of both paths and
cycles. Path-cycle factorizations of semicomplete multipartite digraphs have
been studied by Bang-Jensen, 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:283-286, 1967.
[2] K. T. Balinska, M. L. Gargano, and L. V. Quintas. An edge partition
problem concerning hamilton paths. Congressus Numerantium, 152:45-54,
2001.
[3] K. T. Balinska, M. L. Gargano, L. V. Quintas, and K. T. Zwierzyhski.
Graphs with non-traceable 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 non-traceable edges. Congressus
Numerantium, 162:55-64, 2003.
[5] J. Bang-Jensen. Locally semicomplete digraphs: a generalization of tour-
naments. J. Graph Theory, 14:371-390, 1990.
[6] J. Bang-Jensen and G Gutin. Digraphs: Theory, Algorithms and Applica-
tions. Springer-Verlag, 2001.
[7] J. Bang-Jensen, G. Gutin, and J. Huang. A sufficient condition for a semi-
complete multipartite digraph to be hamiltonian. Discrete Math., 161:1-12,
1996.
[8] M.F. Bridgland and K.B. Reid. Stability of kings in tournaments. In
Progress in graph theory (Waterloo, Ont. 1982), pages 117-128. 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 129-151. 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:69-81, 1952.
82


[12] J.D. Foulkes. Directed graphs and assembly schedules. In Proc. Symp.
Appl. Math., pages 218-289. Amer. Math. Soc., 1960.
[13] A. Ghoulia-Houri. Une condition suffisante dexistence dun circuit hamil-
tonien. C. R. Adac. Sci. Paris, 156:495-497, 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:7-52, 2003.
[16] Y. Guo. Strongly Hamiltonian-connected 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:231-246, 1966.
[19] J. Huang. On the structure of local tournaments. J. Combin. Theory Ser.
B, 63:200-221, 1995.
[20] J. Huang. Which digraphs are round? Australas. J. Combin., 19:203-208,
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:143-148,
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:95-115, 1927.
[26] H. Meyniel. Une condition suffisante dexistence dun circuit hamiltonien
dans un graph oriente. J. Combin. Theory Ser. B, 14:137-147, 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:101-104, 1972.
[29] J.W. Moon. On subtournaments of a tournament. Canad. Math. Bull.,
9:297-301, 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:177-189, 2000.
[32] L. Redei. Ein kombinatorischer satz. Acta Litt. Szeged, 7:39-43, 1934.
[33] K. B. Reid. Tournaments. In J.L. Gross and J. Yellen, editors, The Hand-
book 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 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 on-line encyclopedia of integer sequences, published
electronically at http://www.research.att.com/ njas/sequences/. A000213.
[38] C. Thomassen. Hamiltonian-connected tournaments. J. Combin. Thoery
Ser. B, 28:142-163, 1980.
[39] C. Thomassen. On the number of hamiltonian cycles in tournaments. Dis-
crete Math., 31:315-323, 1980.
[40] C. Thomassen. Edge-disjoint hamiltonian paths and cycles in tournaments.
Proc. London Math. Soc. (3), 45:151-168, 1982.
[41] F. Tian, Z.S. Wu, and C.Q. Zhang. Cycles of each length in tournaments.
J. Combin. Theory Ser. B, 33:245-255, 1982.
[42] L. Volkmann. Longest paths through an arc in strong semicomplete multi-
partite digraphs. Discrete Math., 258:331-337, 2002.
84


[43] D.R. Woodall. Sufficient conditions for circuits in graphs. Proc. Load.
Math. Soc., 24:739-755, 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) Arc-traceable Tournaments Thesis directed by Professor Michael S. Jacobson ABSTRACT A tournament T is arc-traceable when each arc of the tournament i s a part of a hamiltonian path. We characterize arc-traceab l e upset tournaments and show that this property is independent of the number of hamiltonian paths in such tournaments. We show that non-arc-traceable tournaments have a specific structure, and give several sufficient conditions for strong tournaments to be arc traceable, including Dirac-like minimum degree conditions, Ore-like conditions and irregularity conditions. In each case, we show that the r es ult is best possible. Next, we give some extremal results for arc-traceable 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 k-arc -strong tournament that is not arc-traceable Finally we also consider the arc-traceable 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 Arc-traceable upset tournaments 3 2 Counting Hamiltonian Paths in Upset Tourna ments 4. Arc-traceability in all strong tournaments . 4 1 Observations on arc-traceability in tournaments 4.2 The structure of non-arc-traceable tourname nts 4.3 Applications of the structure results ... ... 4.4 Extremal r es ults r elated to arc-traceable 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 arc-pancyclic 4 6 9 13 16 1.4 2 1 2.2 2.3 The two famili es of arc-3-cyclic tournaments that are not a r c-pancy clic. 16 A hamiltoni a n digraph that is not arc-traceable. 18 3.1 An 11-tournament with 10 non-trace a bl e a rc s 3.2 Two 8-tournaments . 4 1 An arc-traceable tournament. 4 2 A tournament with non-traceable a r c xy a nd two arc-disjoint p at hs from y to x .................. . .... 5 1 Two non-arc-traceable strong semicomplete digraphs 5.2 A round loc a l tournament with cycles of l e ngth two. 5.3 A strong non-arc-trac 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 arc-traceable ; an arc-traceable 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 arc-traceability in the sub-class of digraphs known as tournaments. Tournaments have additional structure that, in many cases can be shown to guarantee arc-traceability. We use this additional structure to investigate tournaments that are not arc-traceable. 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 arc-traceable. This necessary condition is used to show that the study of arc-traceable tournaments can be restricted to studying arc-traceable strong tournaments. 1

PAGE 10

Initially, we consider the question in the context of a sub-class of strong tournaments known as upset tournaments, and in Chapter 3 we give a charac terization of arc-traceable 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 non-traceable). W e a lso develop some techniques to demonstrate that arc-traceability is independent of the number of hamiltonian paths in upset tournaments. In other words, arc-traceability in a tournament is not merely a consequence of having many hamiltonian paths. In Chapter 4, we broaden the investigation of arc-traceability to all strong tournaments. We begin with some simple observations about sufficient condi tions for a strong tournament to be arc-traceable. From these basic observa tions, we then develop some necessary conditions for a strong tournament to be non-arc-traceable. These conditions, in turn, yield many new and improved suf ficient conditions for arc-traceable tournaments, and a structure that we use to construct minimal non-arc-traceable tournaments with many arc-disjoint paths between every pair of vertices. We also use the structure of non-arc-traceable tournaments to determine the maximal number of non-traceable arcs in a strong n-tournament. In Chapter 5, we briefly consider arc-traceability for digraphs in general. We investigate arc-traceability in two classes of digraphs that include tournametns, semicomplete digraphs and local tournaments. We also briefly consider some questions closely related to arc-traceability 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 out-neighborhood 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 out-d e gree ( d+ ( v)) and in-d 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 (in-degree) and + ( be the largest out-degree (in-d 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 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 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 non-adjacent vertices u and v ) then G is hamiltonian. W e note that for strict digraphs, an analogue of Theorem A was given by Ghouila-Houri. 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) 2n-1 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 cut-set of D When D[SJ i s s trong for all sets S with [S[ [V[-(d-1), we say that Dis d-connected and we define K,(D) to b e the smallest d such that D is d-conne c ted. Analogously, if D' = (V, T) is not strongly connected for some T C A then A \ T is called an arc cut-set, 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 k-arc-connected or k-arc-strong when eve r k::; K,1(D). The digraph in Figure 1.2 is 2-arc-strong; 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 non-adjacent v e rtic es x and y are specified, an x, yseparating-set is a set S of vertices such that every path from x to y contains at least one vertex of S. Similarly an x, y-separating-set 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 non-adjacent). 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 (arc-disjoint) 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 non-adjacent vertices of D. The number of internally vertex disjoint paths from 7

PAGE 16

x to y equals the size of the smallest x, y-separating set. Similarly, for any distinct (possibly adjacent) vertices x andy, the number of arc-disjoint paths from x to y equals the size of th e smallest x, y-separating 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 n-tournament when IV(T)I = n It is often helpful to think of an n-tournament as an orientation of the complete graph Kn. From this perspective, it is immediate that a tournament has no self-loops 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 8-tournament 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 n-tournament 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 T-S 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 in-and out-degrees 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 in-and out-degree 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 out-degree either or -1. Such tournaments are ca lled near-regular or almost-regular. Proposition 1.1. i(T) = n-12c5 Proof. If ld+ ( v)-d-( v) I > n-126 for some v E V then we must have either 9

PAGE 18

d+(v) -d-(v) > n-126 or d-(v)-d+(v) > n-126. Substituting in d+(v) + d-(v) for n-1 into both equations and simplifying, we obtain either d-(v) < 6 or d+(v) < 6, a contradiction Thus, i(T) n-1 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 non-decr 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 non-decreasing 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 anti-symmetric 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) = i-1; 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 non-upset arcs when these arcs are of particular int e rest (to highlight non-traceable 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 non-trivial components of the tournament with large circles or ellipses, often without specifying the internal structure of these strong components. Further more, using a top-to-bottom or left-to-right 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 sub-class 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 non-trivial 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 vertex-pancyclic. 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 arc-k-cyclic, and if a tournament is arc-k-cyclic for each possible k (in othe r words for 3 :S k :S n), then the tournament is called arc-pancyclic. In the special case where k = n, we will say a tournament is arc-hamiltonian rather than arc-n-cyclic. Alspach [1] initially showed that every regular tournament is arc-pancyclic. Jakobsen [21] studied near-regular tournaments and found that whil e not necessarily arc pancyclic, for n 2: 8, such tournaments are arc-k-cyclic for each k 4 :S k :S n. In 1980, Thomassen [38] showed that every 3-conn ected tournament is arc pancyclic and that there are infinitely many 2-connected tournaments that are not arc-hamiltonian (and hence, not arc-pan cyclic). Thomassen was also able to give a sufficient condition for almost arc-pancyclic tournaments based on irregularity. Theorem I. Thomassen {38} IJT is ann-tournament with i(T) :S n53 then T is k arc-cyclic for 4 :S k :S n As regular and near-regular 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 arc-pancyclic Figure 2.2: The two families of arc-3-cyclic tournaments that are not arcpancy clic. and Jakobsen. For k = 3, Moon [27] was able to show that nearly all tournaments are arc-3-cyclic. This last result was then used by Tian, Wu and Zhang to aid in c haracterizing arc-pancyclic tournaments. They showed the following: Theorem J (Tian, Wu and Zhang (41]). An arc-3-cyclic tournam ent is arc-pancyclic 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 non-strong 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 arc-traceable to describe digraphs with this property. In this undirected context, it was shown that every hamiltonian graph is edge-traceable (called totally-traceable in [2], [3] and [4]). Since hamiltonian graphs are extensively studied, this gives a great deal of information about edge-traceable graphs. In the directed case, examples abound which show that hamiltonicity is not sufficient to guarantee arc-traceability. One such example is shown in Figure 2.3. The lack of a well known sufficient condition for a digraph to be arc-traceable 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 arc-traceable. Theorem 2.1. If D is an arc-traceable digraph, then D*, the condensation of D is a path. Proof. Let D be an arc-traceable 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 arc-traceable 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 in-degr ee 0. Label such a vertex viNow D* -{ vn is also acyclic and so this subgraph also has at least one vertex of in-degree 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 in-degree 0 in D* -{v1 .. Vp-d 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 Bang-Jensen 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 arc-traceable, 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 arc-traceable 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 arc-traceable, 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 arc-traceable. However, w e can us e the hamiltonicity of strong tournaments to observe that the analysis of a r c-tracea ble tournaments reduces to the study of arc-traceable strong tournaments. Corollary 2.3. A tournament T with two strong components is arc-traceable 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 arc-traceable 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 arc-traceable then each arc within these subtournaments is also traceable in T. To co nclude that T is arc-traceable, 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 in-degree zero) to the sink (i.e. vertex of out-degree 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 n-tournament, 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 out-degree one to a vertex of in-degree 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 out-degree one and let v and v' be vertices with in-degree 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 in-degre 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 out-degree one to a vertex of in-degre 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. Ann-tournament T is an upset tournament if and only if the score sequence ofT 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 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 tourna-22

PAGE 31

ment. For n > 4, letT be an-tournament 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' = T-u. 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 (n-I)-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 out-degree 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 Arc-traceable upset tournaments We now address the question of arc-traceability 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 non-traceable 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 vk-l 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 vk-l nor vk+l is on the upset path. Suppose that for some such k, Vk-1 is on the upset path, so vkvk-l is an arc of U. Then, both T1 = T[{ v1, ... vk-d] 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 Vk-l 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 vk-l 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 arc-traceable upset tournaments with six or more vertices. Corollary 3.3. An upset tournament T on n 6 vertices zs arc-traceable if and only if for ever y vertex vk on the interior of the upset path, either Vk-l 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 11-tournament with 10 non-traceable arcs implies that there is no arc that is non-traceable, i.e. T is arc-traceable. 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 arc-traceable, 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 non-isomorphic 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 arc-traceable. Next we describe an upset tournament with many non-traceable 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 n2-4n+3 1 (n) 3(n-1) upset pa o zs VnVn-2Vn_ 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 non-traceable arcs starting at vertex vi. Summing all possible values of j, we obtain n-5 (n-3 j) = (n-3) (n-3) n2 -4n + 3 2 2 2 2 8 j=O non-traceable 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 non-traceable arcs among all upset n-tournaments. Theorem 3.5. An upset n-tournament T n 2 5, has at most n2 -4n + 3 = (n) 3(n-1) 8 4 2 8 non-traceable 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 arc-traceable, 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 (n-i + 1)2 -4(n-i + 1) + 3 = n2 -4n + 3 (i 1)_2n_-_4_---'-(i_-_1--'-) 8 8 8 27

PAGE 36

non-traceable 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 non-traceable in T All that remains is to count the non-traceable arc s of T that are not arc s of TI Clearly, no arc incident with the vertices v 2 ... vi-I is non-traceable so any non-traceable 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 (n-i + 1)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 4n8I2 = arcs incident with VI ar e non-traceable. Let j be the largest index such that the arc VI Vj is non-traceable. 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 arc-traceability 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 n-1 6-4 (.639)(1.565n) distinct hamiltonian paths. It is natural to expect that, in general, arc-traceable upset tournaments have more hamiltonian paths than non-arc-traceable 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 Pr denote the number of distinct hamiltonian paths of the tournament T. Theorem 3.6. If T is an upset n-tournament 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 Vj-l to V8 in Taswell as on every path from Vt to Vj_1 Thus, we conclude that Vj-l 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 ,Vi-d. 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 + (ab-cd) = 2ab-cd 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 < i-1. 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 2n-2 + 1 hamiltonian paths. Proof. LetT be an upset n-tournament 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 ... Vn-d 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 2n-3 + 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 = 2j-2 + 1 and PT[vj, ... ,vn] = 2n-j-l + 1. Thus PT = 2n-J + 2j-2 + 2n-j-l + 1. The proof is complete by noting that the function f(x) = 2x2+2n-l-x has a global minimum at X= ntl. D We note, as a consequence of this corollary the number of hamiltonian paths in upset n-tournaments 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 non-arc-trac eablP. by Corollary 3.3. 33

PAGE 42

.... Figure 3.2: Two 8-tournaments We can now use the above results to show that the first 8-tournament shown in Figure 3.2 has precisely 2(5)(5)-1 = 49 hamiltonian paths and by Corollary 3.3 is arc-traceable. Similarly the second 8-tournament shown in Figure 3 2 is non-arc-traceable 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 arc-traceable 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 arc-traceable upset n-tournament with k hamiltonian paths, and T' is a non-arc-traceable upset n-tournament with k' > k hamiltonian paths, then n 8. We now consider the family of upset n-tournaments with upset paths of length n-1. 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 n-tournament. We show that the the number of hamiltonian paths of such ann-tournament 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 i-vertices 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 v-deletable 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 = Pn-1 + Pn-2 + Pn-3 for n 2: 3. Proof. Let Si be the set of hamiltonian paths We establish the result by showing a bijection between Sn and Sn-1 U Sn-2 U Sn-3 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) = {vn-1}, 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 Sn-3 We first show that each path P of Wn, l must end with the subpath Vn-3Vn-IVn-2Vn Since a path P of Wn,l does not end at Vn-l, and N+ ( Vn-d = { Vn-d, P must include the arc Vn-IVn_2 Furthermore becaus e P is not Vn-l deletable the vertex immediately preceding Vn-l must be dominated by Vn_2 and so must be a vertex in N+(vn-2) = { Vn-3, Vn} As P ends at Vn by definition, this vertex must be Vn-3 and the vertex immediately following Vn-2 must be Vn, the terminal vertex of P. Similarly we show that each path P of Wn,2 must end with the subpath Vn-2VnVn-1 Since P does not end at Vn and N+(vn) = {vn-I} it contains the arc VnVn-1 and since P is not Vn deletable, the vertex immediately preceding Vn on P must be in the set N+(vn-d = {vn-d Further, since this is the only vertex dominated by Vn-l, Vn-l 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 Tn-3 Conversely, any hamiltonian path H of Tn_3 can be extended to a hamiltonian path of Tn by appending the path Vn-1Vn-2Vn if H e nds at Vn-3, or appending the path Vn-2VnVn-1 if H does not end at Vn-3 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 arc-traceable 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 n-tournament 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 non-arc traceable upset tournament T with upset path VnVrntl1v1 h as more distinct hamiltonian p aths than the arc-traceable upset tournament T' with ups et path VnVn-1 ... v1, and PT-PT' grows exponentially with n. 38

PAGE 47

4. Arc-traceability in all strong tournaments In this chapter we turn our attention to arc-traceability 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 non-arc-traceable 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 non-ar c-t raceable tournaments. 4.1 Observations on arc-traceability 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 non-traceabl e arcs of a tournament must join two cut vertices. Proposition 4.1. If T is a strong tournament and v is not a cut-v ertex ofT, then ever y arc incident with v is on a hamiltonian path. This gives us our first sufficient condition for arc-traceable tournaments; if T has no cut v e rtices then T has no non-trac eab le arcs. Corollary 4.2. If T is 2-connected, then T is arc-traceable. 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 n-tournament, 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 ui-Iwi-l 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 arc-traceable Corollary 4.5. 1fT is a strong tournament and every arc ofT is on some cycle of length l > nti then T is arc-traceable. We now consider again our observation above that every 2-connected tour nament is arc-traceable. If a tournament is two-connected (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 re-state 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

arc-trac 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)I-IN+(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 arc-traceab l e tournaments are closely related and follow from the fact that all 2-connected 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 arc-traceable. Proof. We prove that the condition guarantees that T is 2-connected. 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 ofT-v respectively Then T-v must contain a vertex with in-degree at most a;l and a vertex with out-degree 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 arc-traceable. Proof. The proof is the same as for Corollary 4.9, combined with the additional observation that the vertex u with in-degree at most a;l in T-v dominates the vertex w with out-degree at most b;l in T-v. Thus we have an arc uw such that Corollary 4.11. Let T be a tournament such that i(T) < arctraceable 44 n-3 -4-. 0 Th e n T is

PAGE 53

Proof. The result follows from Corollary 4.9 and the fact that i(T) = (n-1)26. Thus, o0 > ntl implies that i(T) < (n-1 ) = 0 4.2 The structure of non-arc-traceable tournaments Since the results of the previous section are really based on the observation that every two-connected tournament is arc-traceable Theorem 4.7 has not yet proven useful in the study of arc-traceabl e tournaments. However, the contra positive of Theorem 4. 7 can be used to obtain some important necessary conditions for non-arc-traceable 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 T-z 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 T-z, so y and x are in different strong components ofT-z and this tournament is not strong establishing (i). Let T z denote T-z, 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 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 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 w-be the vertex immediately preceding w on P1 and replace the arc w-w of P1 with the path w-zw 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 z-E 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 arc-traceable tournament. is no such z+ in V(TP)). Dually, we have that there is no Uf"(z)nV(T;k-1)) = 0 establishing ( iv). This argument also shows that k-1 # 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 arc-traceable. However, such a structure is not sufficient to guarantee non arc-traceability For e xample, the arc-traceable tournament in Figure 4.1 has the structure indicated in Theorem 4.12. In an attempt to complete a characterization of arc-traceable tournaments, we consider whether additional structure imposed on the first and last strong components ofT-z is sufficient to guarantee non-arc-tra 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;k-1 ) 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 non-arc-traceability 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 arc-traceable. Proof. Let N+(z) nTP) = {x} and N-(z) = {y}. Then by L emma 4.13, xy is non-traceable. 0 Note that the converse of this corollary is false as the tournament in Figure 4.1 is not arc-traceable. At this point it appears we hav e characterized arc-traceable 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 arc-traceable if and only if some other related tournaments R1 and Rk are not arc-traceable. For this reason, we generally will find it easier to use the incomplete results of Theorem 4.12 to produce sufficient conditions for arc-traceable tournaments (and conversely necessary conditions for non-arc 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 in-degree (out-degree), 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 non-arc-traceable strong tournament, and let xy be a non-traceable arc ofT. If 6(T) > 1, then either x is the unique vertex of minimal in-degree in Tz or 6-(T) = 6-(Tz) for the vertex z in Theorem 4 12. Similarly either y is the unique vertex of minimal out-degree 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 in-degree 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 in-degree 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 out-degree is y. 0 4.3 Applications of the structure results Although the structure described above falls short of a complete characterization of non-arc-traceable tournaments, it gives a great deal of information about such tournaments. Using this structure, we improv e several of the previous sufficient conditions for arc-traceable tournaments as well as improving a result of Volkmann [42] for tournaments with <5 2: 2. Theorem 4.17. IJT is a strong n-tournament with o0 2: 2 and d-(x) +d+(y) ;:::: 2 for every xy E A(T), then T is arc-traceable. Proof. We prove the contrapositive: if T is not arc-traceable, then for some arc xy ofT, d-(x) + d+(y) < 2. Assume that Tis not arc-traceable, 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 rY-l) are distinct and non-empty and ITzl = ITI 1 n 2: a+b+3. Choose vertices u of minim a l in-degree and v of minimal out-degree 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 nearly-regular, 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+b-2 < n-S < .!! 2 completing the proof 2 2 2 0 51

PAGE 60

The above result gives Ore-like degree conditions on a tournament that guarantee arc-traceability. As an obvious corollary we state the result with Dirac-like degree conditions. Corollary 4.18. If T is a strong n-tournament with 6 2: -1 > 11 then T is arc-traceable. As a consequence of this Dirac-like condition we state the result in terms of irregularity, similar to Theorem I. Corollary 4.19. If T is a strong n-tournament with 6 > 1 and i(T) :::; + 11 then T is arc-traceable. Proof. i(T) = (n-1)26, so i(T):::; + 1 implies that (n-1)26:::; + 1. Solving for 6, we obtain 6 2: -1. 0 The structure of non-arc-traceable 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 arc-traceable then every arc ofT is on a path of length nand the result is immediate. So we may assume that T is not arc-traceable, 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 < k-1 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 + (n-1) 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 fol-lowing corollary. Corollary 4.20. IfT is a strong n-tournament 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 non-traceable. 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;k-l), 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 arc-traceability 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 all-kings tournaments are arc-traceable. Theorem 4.22. If T is an n-tournament with n or n -1 kings, th e n T zs arctrac eable. Proof. Assume that T is not arc-traceable, and hence has the structure given in Theorem 4.12. Choose v1 and v2 from r;k-l) 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 n-2 kings D When S0 > 1, similar techniques give a slightly improved result. Theorem 4.23. If T is a non-arc-traceable strong n-tournament with S0 > 1, then T has at most n-32S+ kings. Proof. Assume that T is non-arc-traceable, and let xy be a non-traceable 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;k-l) 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 n-2(2t5+(Tz) + 3) = n-2(2(t5+(T)1) + 3) = n-36+(T) kings in T. D 4.4 Extremal results related to arc-traceable tournaments In this section, we use the structure of non-arc-traceable strong tournaments to produce some extremal results. First, we fix n and consider the maximum number of non-traceable arcs in a strong n-tournament. Later we consider tour naments with m arc-disjoint paths between any two vertices, and we determine the minimal n such that some m-arc-strong n-tournament is not arc-traceable. In Chapter 3, we constructed an upset n-tournament with non traceable arcs for any odd n, and we proved that this tournament was maximal with respect to the number of non-traceable arcs. We will denote this tour nament Tmax., and recall that this tournament is obtained from the transitive tournament on the set V = {v0 ... Vn-l} where d+(vi) = i by reversing the arcs vivi+2 for each even i < n-1. We now prove that any strong n-tournament T pas at most this number of non-traceable arcs with equality if and only if T is isomorphic to T max. Lemma 4.24. Let T be a strong tournament having a cut-vertex 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 2-path 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 non-traceable 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 n-tournament, then T has at most n2-:n+3 non-traceable 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 n-tournament, a nd in both cases this tournament is arc-traceable 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 non-ar c-t raceable Let xy be a non-tracea 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;k-l). If a = x'y' is a non-tracea ble arc ofT, neither T-x' nor T-y' 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 non-tra cea ble in T is also non-traceabl 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 out-degree 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 non-traceable 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+f-2 Finally, by Corollary 4.25, there are at most non-trac e able arcs from A to B Combining and observing that a + b ::; n -3 the number of non-traceable 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(n-3) 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 non-traceable arc xy and two arc-disjoint 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 non-traceabl e arc xy with m arc-disjoint 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 arc-disjoint 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 arc-disjoint 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 2-path 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 non-traceable. D 61

PAGE 70

Thus for any m, we can construct a tournament with n + 1 vertices with a non-traceab le arc xy such that there exist marc-disjoint 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 k-tournament containing a non-traceable arc xy such that there exist m arc-disjoint 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 non-traceable arc xy and m + 1 arc-disjoint paths from y to x. Assume that k < 2n + 1 = 2m+2 + 1. As xy is non-traceable, 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 arc-disjoint 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 arc-disjoint 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 non-traceable, 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 arc-disjoint paths between e very two vertices. In fact, for each m, T[m] contains a vertex of in-degree 1 (v(n-1)) as well as a vertex of out-degree 1 ( v1 ) so we have yet to produce even a 2-arcs trong tournament that is not arc-traceabl e We now seek to construct such an m-arc strong non-arc-traceabl 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 Vn-1 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[Un-1] are regular tournaments of degree m -1, and Un-1 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 m-arc-strong. Proof. It suffices to show that v0 both reaches and is reached by every other vertex of T{mJ using m arc-disjoint 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, ... ,Um-d Clearly, W; = UU;Vo for 1 :S i :S m -1 and W m = uv0 are marc-disjoint 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 &rc-disjoint walks, we use the set of m upset paths U1 ... Um. Clearly, U1 ... Um are arc-disjoint paths from v0 to Vn To show that v0 reaches every vertex of w E Un-1 by m arc disjoint walks, let N-(w) n Un_1 = {w1 Wm-d and let W; = Uiw;w for 1 :S i :S m-1 and Wm = Umw. As above, for v : Un-1 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 non-traceable. 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 2m-1 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, vn-1Qv1 is a path of T[m] with order n + 1, and hence Vn-lQvl 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 non-arc-traceable m-arc-strong tournaments. Theorem 4.31. If T is a non-arc-traceable m-arc-strong k-toumament, then k 2:: n +4m-3. Proof. For m = 1, the result is immediate by observing that all strong tourna ments are 1 arc-strong and that 21+1 -4(1) 3 = 5 is the size of the smallest non-arc-traceable strong tournament. So we can assume that m 2:: 2 Let xy be 65

PAGE 74

a non-traceable arc ofT. Define Sx as the initial strong component ofT-x and Sy as the terminal strong component ofT-y. 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 arc-strong, ;:::: m and ;:::: m -1 for any v E V(T). Thus, 5y._x ;:::: m-1 and 5:f_y ;:::: m-1 and consequently both ISx l ;:::: 2m-1 and ISyl 2: 2m-1. 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 ofT-x, and since y :. Sx, it reaches every vertex of (T-x)-y. So z is in the terminal strong component ofT-y but the initial strong component ofT-y-x. As a result, the initial strong component ofT-y must be {x}. This requires that 5y._Y = 0 < m-1, 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 marc-disjoint 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(2m-1) = n +4m-3 vertices. D 66

PAGE 75

5. Related problems In this concluding chapter, we consider arc-traceability in other classes of digraphs related to tournaments, as well as various other ways to generalize arc-traceability. We will introduce new definitions and notation as needed. The main result of this chapter will be a characterization of arc-traceability in the class of strong round-decomposable locally semicomplete digraphs. These results are intended to suggest new directions for the investigation of arc-traceable digraphs and to propose the study of properties similar to arc-traceability 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 arc-traceable, 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 2-connected 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 2-connected semicomplete digraph is arc-traceable. 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 arc-traceable. 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, x-separating 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 2-cycles 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 non-arc-traceable 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 non-arc-traceable strong semicom plete digraphs in Figure 5.1. The digraph on the l eft has non-traceable 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 arc-traceable strong tournaments, but with the additional arc yx. In both cases additional 2-cycles may be present within the components. 69

PAGE 78

Figure 5.1: Two non-arc-traceable 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 arc-traceability. 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: n-2, then D is arc-traceable. Proof. Assume D is not arc-traceab 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) :::; b-1. 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) :::; a-1 and a vertex v with d1J (v) :::; b-1. (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=n-3. 0 5.2 Round digraphs Another generalization of tournaments in which arc-traceability 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 arc-traceable 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-j 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, ... Vn-d If d+(vi) ::; 1, then the out-neighborhood 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 arc-traceable. 72

PAGE 81

Theorem 5.8. A round digraph D with + 2 is arc-traceable Proof. Let D be a round digraph with + 2 and let V(D) = {vo, ... Vn-1} 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+(vj-d > 2, the round lab e ling r e quires that Vj-l -+ 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 non-strong 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 ... Vn-1, 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 arc-traceable 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 arc-traceable 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, ... Vn-1} An arc vivj is traceable if and only if j = i+ 1, d+(vi-1) ?: 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 v1-2v1-d and V2 = {vJ+1Vj+2 vi-2Vi-l} If v;_ 1 precedes a on H, then H must include some arc VaVb with Va E v2 and Vb E v1 Thus, Vi-1 E N-(vb) and so d+(vi-1) ?: 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+( Vj-d 2: 2. For the converse, assume first that j = i + 1. In this case, vivi+1 vi-1 is a hamiltonian path containing a. Next, assume that d+(vi_r) 2: 2. Then, 74

PAGE 83

vi-lvi+l is an arc of D and ViVjVj+ 1 vi-lvi+1vi+2 Vj-I 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 Vj-IVj+l is an arc of D and thus vi+lvi+2"'Vj-IVj+l'"Vi-IViVj i s a hamiltoni a n path of D for j =f. i -1 a nd vi+ I vi+2 vi-2vivj is a hamiltonian path othe rwise. D We now take our characterization of traceable arcs and use it to obtain a characterization of arc-traceable 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 arc-traceable 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 ... Vn-d be a round labeling of D Assum e that D is arc-traceable 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 Vj-l -+ 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 out-degree 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 Vn-IVo Vi-2 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 vi-I vi+! Vj-l is a hamiltonian path of D { x, y}. Similarly if d + (vj-d 2: 2 then vi+l Vj 1vi+1 vi-I is a hamiltoni a n path of 75

PAGE 84

Figure 5.3: A strong non-arc-traceable 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> ... Vj-d and v2 = { VJ+l, ... Vi-d, 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 Vj-1 E N-(vb) or vi-1 E N-(vb) and so d+(vj d 2: 2 or d+(vi-1) 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 Vj-1 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 Vn-IVo Vi-2 is a hamiltonian path of D containing the arc vivj. Similarly, in the latter case vi+ I vi+2 vn-1vov1 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 arc-traceable. 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 non-traceable 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 Bang-J e nsen. Theorem N (Bang-Jensen [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 arc-traceability. Corollary 5.14. If D is a weakly connected (but not strongly connected} locally semicomplete digraph then D is arc-traceable if and only if eac h $trong compo -nent of D i's an arc-traceabl 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 arc-traceable semicomplete digraphs but we do know a great deal about the structure of non-arc-trac eable strong semicomplete digraphs from Theorem 5.5 In the case of strong locally semicomplete digr a phs we will focus on the sub-class 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 one-to-one 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 non-traceable if and only if for some non-traceable 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 Hj-l 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 ... i-1} and the other is in the set { i + 1 i + 2, ... j -1 }. This forces the arc wi-lwi+l or the arc Wj-lWj+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 arc-traceable 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 arc-traceable 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 arc-traceable locally semicomplete digraphs, such digraphs that are not round decomposable must be considered. This cas e 79

PAGE 88

remains open. Question. Characterize arc-traceable 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 arc-traceability could be inv es tigated, and we will consider properties similar to arc-traceability. 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 arc-traceabZ,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 non-adjacent vertices. Question. Characterize arc-traceable digraphs whose underlying graph is Kn -e. G e neralizing the idea of arc-traceability 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 arc-traceable. 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 arc-traceable 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 Bang-Jensen, 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:283-286 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:45-54, 2001. [3] K. T. Balinska, M L Gargano, L. V. Quint a s and K. T. Zwi e rzynski. Graphs with non-traceable 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 n-traceable edg es. Con gr ess us Nume rantium, 162:55 64 2003. [5] J Bang-Jensen. Locally semicomplete digraphs: a generalization o f tourname nts. J. Graph Th e ory 14:371-390, 1990 [6] J B a ng-Jensen and G Gutin. Digraphs : Th e ory Algorithms and Appl icat i ons SpringerVerl a g 2001. [7] J. Bang-Jensen, 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 117-128 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 129-151. 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:69-81 1952. 82

PAGE 91

[12] J.D. Foulkes. Directed graphs and assembly schedules. In Proc. Symp. Appl. Math., pages 218-289. Amer. Math. Soc., 1960. [13] A. Ghoulia-Houri. Une condition suffisante d existence d un circuit hamil tonien. C. R. Adac. Sci Paris, 156:495-497, 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:7-52, 2003. [16] Y. Guo. Strongly Hamiltonian-connected 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:200-221, 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:143-148, 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 : 137-147 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:297-301, 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:39-43, 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 on-line encyclopedia of integer sequences. published electronically at http:/ jwww.research.att.com/ njas/sequences/. A000213. [38] C. Thomassen. Hamiltonian-connected tournaments. J. Combin. Thoery Ser. B, 28:142-163, 1980. (39] C. Thomassen. On the number of hamiltonian cycles in tournaments. Dis cre te Math. 31:315 323, 1980. [40] C. Thomassen. Edge-disjoint h a miltonian paths and cycles in tournaments Proc. London Math. Soc. (3), 45:151-168, 1982. [41] F. Tian, Z.S. Wu, and C.Q. Zhang. Cycles of each l ength in tournaments. J. Combin. Theory Ser. B, 33:245-255, 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:739-755 1972. 85