A tournament is an orientation of the complete graph.Tournaments form perhaps the most interesting class of digraphs and it has a great potential for application.Tournaments provide a model of the statistical techniqu...A tournament is an orientation of the complete graph.Tournaments form perhaps the most interesting class of digraphs and it has a great potential for application.Tournaments provide a model of the statistical technique called the method of paired comparisons and they have also been studied in connection with sociometric relations in small groups.In this paper,we investigate disjoint cycles of the same length in tournaments.In 2010,Lichiardopol conjectured that for given integers l≥3 and k≥1,any tournament with minimum out-degree at least(l-1)k-1 contains k disjoint l-cycles,where an l-cycle is a cycle of order l.Bang-Jensen et al.verified the conjecture for l=3 and Ma et al.proved that it also holds for l≥10.This paper provides a proof of the conjecture for the case of 9≥l≥4.展开更多
We prove that ifG is a graph of order at least 2k with k≥9 and the minimum degree of G is at least k + 1,then G contains two vertex-disjoint cycles of order at least k.Moreover,the condition on the minimum degree is ...We prove that ifG is a graph of order at least 2k with k≥9 and the minimum degree of G is at least k + 1,then G contains two vertex-disjoint cycles of order at least k.Moreover,the condition on the minimum degree is sharp.展开更多
基金supported by the National Natural Science Foundation of China(Nos.12071260,11671232)。
文摘A tournament is an orientation of the complete graph.Tournaments form perhaps the most interesting class of digraphs and it has a great potential for application.Tournaments provide a model of the statistical technique called the method of paired comparisons and they have also been studied in connection with sociometric relations in small groups.In this paper,we investigate disjoint cycles of the same length in tournaments.In 2010,Lichiardopol conjectured that for given integers l≥3 and k≥1,any tournament with minimum out-degree at least(l-1)k-1 contains k disjoint l-cycles,where an l-cycle is a cycle of order l.Bang-Jensen et al.verified the conjecture for l=3 and Ma et al.proved that it also holds for l≥10.This paper provides a proof of the conjecture for the case of 9≥l≥4.
基金supported by National Security Agent of USA(Grant No.H98230-08-10098)
文摘We prove that ifG is a graph of order at least 2k with k≥9 and the minimum degree of G is at least k + 1,then G contains two vertex-disjoint cycles of order at least k.Moreover,the condition on the minimum degree is sharp.
