Vertex-Disjoint Subtournaments of Prescribed Minimum Outdegree or Minimum Semidegree : Proof for Tournaments of a Conjecture of Stiebi

Abstract EN

It was proved (Bessy et al., 2010) that for r≥1, a tournament with minimum semidegree at least 2r−1 contains at least r vertex-disjoint directed triangles.

It was also proved (Lichiardopol, 2010) that for integers q≥3 and r≥1, every tournament with minimum semidegree at least (q−1)r−1 contains at least r vertex-disjoint directed cycles of length q.

None information was given on these directed cycles.

In this paper, we fill a little this gap.

Namely, we prove that for d≥1 and r≥1, every tournament of minimum outdegree at least ((d2+3d+2)/2)r−(d2+d+2)/2 contains at least r vertex-disjoint strongly connected subtournaments of minimum outdegree d.

Next, we prove for tournaments a conjecture of Stiebitz stating that for integers s≥1 and t≥1, there exists a least number f(s,t) such that every digraph with minimum outdegree at least f(s,t) can be vertex-partitioned into two sets inducing subdigraphs with minimum outdegree at least s and at least t, respectively.

Similar results related to the semidegree will be given.

All these results are consequences of two results concerning the maximum order of a tournament of minimum outdegree d (of minimum semidegree d) not containing proper subtournaments of minimum outdegree d (of minimum semidegree d).