Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz.

*(English)*Zbl 1236.05095Summary: It was proved S. Bessy, N. Lichiardopol and 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 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\)).

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\)).

##### MSC:

05C20 | Directed graphs (digraphs), tournaments |

PDF
BibTeX
XML
Cite

\textit{N. Lichiardopol}, Int. J. Comb. 2012, Article ID 273416, 9 p. (2012; Zbl 1236.05095)

Full Text:
DOI

##### References:

[1] | J. Bang-Jensen and G. Gutin, Digraphs, Springer Monographs in Mathematics, Springer, New York, NY, USA, 2001. · Zbl 0958.05002 |

[2] | S. Bessy, N. Lichiardopol, and J.-S. Sereni, “Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree,” Discrete Mathematics, vol. 310, no. 3, pp. 557-560, 2010. · Zbl 1188.05072 · doi:10.1016/j.disc.2009.03.039 |

[3] | N. Lichiardopol, “Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree,” Discrete Mathematics, vol. 310, no. 19, pp. 2567-2570, 2010. · Zbl 1227.05157 · doi:10.1016/j.disc.2010.06.024 |

[4] | M. Stiebitz, “Decompositions of graphs and digraphs,” KAM Series in Discrete Mathematics-Combinatorics-Operation Research 95-309, 56-59. |

[5] | N. Alon, “Splitting digraphs,” Combinatorics, Probability and Computing, vol. 15, no. 6, pp. 933-937, 2006. · Zbl 1116.05033 · doi:10.1017/S0963548306008042 |

[6] | K. B. Reid, “Two complementary circuits in two-connected tournaments,” in Cycles in Graphs (Burnaby, B.C., 1982), vol. 115 of North-Holland Math. Stud., pp. 321-334, North-Holland, Amsterdam, The Netherlands, 1985. · Zbl 0573.05031 · doi:10.1016/S0304-0208(08)73025-1 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.