Vertex-disjoint directed cycles of prescribed length in tournaments with given minimum out-degree and in-degree |
| |
Authors: | Nicolas Lichiardopol |
| |
Institution: | IUT Salon, Univ. Aix-Marseille III, France |
| |
Abstract: | In a recent paper, Bessy, Sereni and the author (see 3]) have proved that for r≥1, a tournament with minimum out-degree and in-degree both greater than or equal to 2r−1 contains at least r vertex-disjoint directed triangles. In this paper, we generalize this result; more precisely, we prove that for given integers q≥3 and r≥1, a tournament with minimum out-degree and in-degree both greater than or equal to (q−1)r−1 contains at least r vertex-disjoint directed cycles of length q. We will use an auxiliary result established in 3], concerning a union of sets contained in another union of sets. We finish by giving a lower bound on the maximum number of vertex-disjoint directed cycles of length q when only the minimum out-degree is supposed to be greater than or equal to (q−1)r−1. |
| |
Keywords: | Tournament Cycle Vertex-disjoint cycles |
本文献已被 ScienceDirect 等数据库收录! |
|