Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz
Summary: It was proved \textit{S. Bessy}, \textit{N. Lichiardopol} and \textit{J.-S. Sereni} [``Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree, Discrete Math. 310, No. 3, 557--560 (2010; Zbl 1188.05072)] that for \(r \geq 1\), a tournament with minimum semidegree at least \(2r - 1\) contains at least \(r\) vertex-disjoint directed triangles. It was also proved \textit{N. Lichiardopol} [Discrete Math. 310, No. 19, 2567--2570 (2010; Zbl 1227.05157)] that for integers \(q \geq 3\) and \(r \geq 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 this gap a little. Namely, we prove that for \(d \geq 1\) and \(r \geq 1\), every tournament of minimum outdegree at least \(((d^2 + 3d + 2)/2)r - (d^2 + 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 \geq 1\) and \(t \geq 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\)).
- Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree
- Vertex-disjoint cycles in regular tournaments
- Vertex-disjoint cycles in bipartite tournaments
- Vertex-disjoint cycles of prescribed length on tournaments
- Disjoint 3-cycles in tournaments: a proof of the Bermond-Thomassen conjecture for tournaments
- scientific article; zbMATH DE number 3914352 (Why is no real title available?)
- scientific article; zbMATH DE number 1498519 (Why is no real title available?)
- Splitting digraphs
- Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree
- Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree
- On splitting digraphs
- Degree constrained 2-partitions of semicomplete digraphs
- On the parameterized complexity of 2-partitions
- On 1-factors with prescribed lengths in tournaments
- Highly linked tournaments with large minimum out-degree
- Finding good 2-partitions of digraphs. II. Enumerable properties
- Partition and disjoint cycles in digraphs
- Finding good 2-partitions of digraphs. I. Hereditary properties
- Tournaments and Semicomplete Digraphs
- scientific article; zbMATH DE number 2192120 (Why is no real title available?)
- Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree
- On the number of non-critical vertices in strong tournaments of order \(N\) with minimum out-degree \(\delta ^{+}\) and in-degree \(\delta ^{ - }\)
This page was built for publication: Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q666527)
