Disjoint cycles in tournaments and bipartite tournaments

被引:2
作者
Chen, Bin [1 ,2 ]
Chang, An [1 ]
机构
[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou, Fujian, Peoples R China
[2] Hefei Natl Lab, Hefei, Anhui, Peoples R China
基金
中国国家自然科学基金;
关键词
bipartite tournament; tournament; vertex disjoint cycle; BERMOND-THOMASSEN CONJECTURE; PROOF;
D O I
10.1002/jgt.23038
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A conjecture proposed by Bermond and Thomassen in 1981 states that every digraph with minimum out-degree at least 2k-1 contains k vertex disjoint directed cycles for any integer k >= 1, which has received substantial attention. This conjecture has been confirmed for k <= 3. In 2014, Lichiardopol raised a very related conjecture that for every integer k >= 2, there exists an integer g(k) such that every digraph with minimum out-degree at least g(k) contains k vertex disjoint directed cycles of different lengths. For a digraph D and a set of k vertex disjoint directed cycles C in D, we denote kappa(k)(C) to be the maximum number of directed cycles in C of distinct lengths. Let kappa(k)(D)=max{kappa(k)(C)vertical bar C is a set of k vertex disjoint directed cycles inD}. We define kappa(k)(D) = 0 if D has no k vertex disjoint directed cycles. In this paper, we mainly investigate vertex disjoint directed cycles in tournaments and bipartite tournaments. We first show that kappa(k)(D) >= 2 for every tournament D with minimum out-degree at least 2k - 1, where k >= 3. We further prove that for k >= 1 and gamma is an element of{1,2, ..., k}, any tournament D with minimum out-degree at least gamma(2)-2 gamma+6k-3/2 satisfies that kappa(k)(D) >= gamma. Moreover, we deduce that for any tournament D with minimum out-degree at least 7, kappa(3)(D)=3 holds. Additionally, we classify strong bipartite tournaments with minimum out-degree at least 2k-1 in which any k vertex disjoint directed cycles have the same length, where k >= 2. That is, for any strong bipartite tournament D with minimum out-degree at least 2k-1, then kappa(k)(D)=1 if and only if D is isomorphic to a member of BT(n(1),n(2), ... ,n(2)k), which is defined in the context.
引用
收藏
页码:297 / 314
页数:18
相关论文
共 18 条
[1]   Disjoint directed cycles [J].
Alon, N .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1996, 68 (02) :167-178
[2]   Vertex-disjoint cycles in bipartite tournaments [J].
Bai, Yandong ;
Li, Binlong ;
Li, Hao .
DISCRETE MATHEMATICS, 2015, 338 (08) :1307-1309
[3]   Disjoint 3-Cycles in Tournaments: A Proof of The Bermond-Thomassen Conjecture for Tournaments [J].
Bang-Jensen, Jorgen ;
Bessy, Stephane ;
Thomasse, Stephan .
JOURNAL OF GRAPH THEORY, 2014, 75 (03) :284-302
[4]  
Bang-Jensen J, 2009, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-1-84800-998-1_1
[5]  
Bensmail J, 2017, ELECTRON J COMB, V24
[6]   CYCLES IN DIGRAPHS - A SURVEY [J].
BERMOND, JC ;
THOMASSEN, C .
JOURNAL OF GRAPH THEORY, 1981, 5 (01) :1-43
[7]   Two proofs of the Bermond-Thomassen conjecture for tournaments with bounded minimum in-degree [J].
Bessy, Stephane ;
Lichiardopol, Nicolas ;
Sereni, Jean-Sebastien .
DISCRETE MATHEMATICS, 2010, 310 (03) :557-560
[8]   An improved bound for disjoint directed cycles [J].
Bucic, Matija .
DISCRETE MATHEMATICS, 2018, 341 (08) :2231-2236
[9]   VERTEX DISJOINT CYCLES OF DIFFERENT LENGTH IN DIGRAPHS [J].
Henning, Michael A. ;
Yeo, Anders .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (02) :687-694
[10]   PROOF OF A CONJECTURE OF HENNING AND YEO ON VERTEX-DISJOINT DIRECTED CYCLES [J].
Lichiardopol, Nicolas .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (03) :1618-1627