
Partitionning a tournament into k-strongly connected subtournaments.








If for
, then
exists and is at most
. This follows by an easy induction on
, by taking
to be a set inducing a directed
-cycle.
The following example shows that if it exists . Set
. For
, let
be a tournament on
vertices having a set
of
vertices such that
a transitive tournament of order
with hamiltonian path
, and
dominates
and is dominated by
. It easy to check that
is
-strongly connected. However, every (non-trivial)
-strong tournament of
must contain at least
vertices of
. Hence
does not have a partition
of its vertex set such that the subtournament induced by
is a non-trivial
-strong for all
.
Some small examples give better lower bound. For example, the Paley tournament on 7 vertices which is 3-strong cannot be partionned into two strong subtournaments. However, there are only finitely many known such tournaments. Chen, Gould, and Li [CGL] showed that every -strongly connected tournament with at least
vertices has a partition into
strongly connected tournaments.
The existence of is still open.
Bibliography
[CGL] G. Chen, R.J. Gould, and H. Li, Partitioning vertices of a tournament into independent cycles, J. combin. Theory Ser B, Vol 83, no. 2 (2001) 213-220.
*[R] K.B. Reid, Three problems on tournaments, Graph Theory and Its Applications, East. and West. Ann. New York Acad. Sci. 576 (1989), 466-473.
* indicates original appearance(s) of problem.