Abstract
In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V 1,…V t such that for all i the subtournament T[V i] induced on T by V i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k 7 t 4) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t 5) suffices.
Original language | English |
---|---|
Pages (from-to) | 451-469 |
Number of pages | 19 |
Journal | Combinatorica |
Volume | 36 |
Issue number | 4 |
Early online date | 24 Jun 2015 |
DOIs | |
Publication status | Published - Aug 2016 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics