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....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.展开更多
基金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.
