首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号