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

It was proved (Bessy et al., 2010) that for , a tournament with minimum semidegree at least contains at least r vertex-disjoint directed triangles. It was also proved (Lichiardopol, 2010) that for integers and , every tournament with minimum semidegree at least ( ) contains at least r vertex-disjoint directed cycles of length . None information was given on these directed cycles. In this paper, we fill a little this gap. Namely, we prove that for and , every tournament of minimum outdegree at least contains at least vertex-disjoint strongly connected subtournaments of minimum outdegree . Next, we prove for tournaments a conjecture of Stiebitz stating that for integers and , there exists a least number such that every digraph with minimum outdegree at least can be vertex-partitioned into two sets inducing subdigraphs with minimum outdegree at least and at least , 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 (of minimum semidegree ) not containing proper subtournaments of minimum outdegree (of minimum semidegree ). 1. Introduction and Definitions The definitions which follow are those of [1]. Let be a digraph. is the vertex set of and the order of is the cardinality of . is the set of the arcs of . Two vertices and of are adjacent, if at least one of the ordered pairs and is an arc of . We say that a vertex is an outneighbor of a vertex (inneighbour of ) if (resp. ) is an arc of . is the set of the outneighbors of and is the set of the in-neighbors of . The cardinality of is the outdegree of and the cardinality of is the indegree of . When no confusion is possible, we omit the subscript . We denote by the minimum outdegree of and by the minimum indegree of . The minimum semidegree of is . An oriented graph, is a digraph such that for any two distinct vertices and of , at most one of the couples and is an arc of . A tournament is an oriented graph such that any two distinct vertices and of are adjacent. If and are subsets of , an arc from to is an arc with and . We denote by the number of the arcs from to . It is known and easy to prove that if is the order of , then and for every vertex of . For a subset of , is the subtournament induced by the vertices of . For a vertex of , is the subtournament induced by the vertices of distinct from . For , a regular tournament of degree is a tournament with for every vertex of . It is known and easy to prove that the order of is . A path or a cycle of a tournament always means