# Partitionning a tournament into k-strongly connected subtournaments.

 Importance: Medium ✭✭
 Author(s): Thomassen, Carsten
 Subject: Graph Theory » Directed Graphs » » Tournaments
 Keywords:
 Posted by: fhavet on: March 15th, 2013
Problem   Let be positve integer Does there exists an integer such that every -strong tournament admits a partition of its vertex set such that the subtournament induced by is a non-trivial -strong for all .

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.