On the Strong n-partite Tournaments with Exactly Two Cycles of Length n-1  

作　　者：Qiao-ping GUO Yu-bao GUO Sheng-jia LI Chun-fang LI 

机构地区：[1]School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China [2]Lehrstuhl C fiir Mathematik, RWTH Aachen, Templergraben 55, 52062 Aachen, Germany

出　　处：《Acta Mathematicae Applicatae Sinica》2018年第4期710-717,共8页应用数学学报（英文版）

基　　金：supported by the Natural Science Young Foundation of China(No.11701349);by the Natural Science Foundation of Shanxi Province,China(No.201601D011005);by Shanxi Scholarship Council of China(2017-018)

摘　　要：Gutin and Rafiey（Australas J. Combin. 34（2006）, 17-21） provided an example of an n-partite tournament with exactly n-m ＋ 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n-m ＋ 1 cycles of length m for two values of m？ In the same paper,they showed that this question has a negative answer for two values n-1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n-1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n-1 and any l with 3 ≤ l ≤ n and l ≠n-1.Gutin and Rafiey（Australas J. Combin. 34（2006）, 17-21） provided an example of an n-partite tournament with exactly n-m ＋ 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n-m ＋ 1 cycles of length m for two values of m？ In the same paper,they showed that this question has a negative answer for two values n-1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n-1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n-1 and any l with 3 ≤ l ≤ n and l ≠n-1.

关 键 词：nmltipartite tournaments TOURNAMENTS cycles 

分 类 号：O156[理学—数学]