A characterization of rich c-partite (c ≥ 8) tournaments without (c + 2)-cycles

被引：0
作者：
Zhang J. [1 ]
Wang Z. [1 ]
Yan J. [1 ]
机构：
[1] School of Mathematics, Shandong University, Jinan
来源：
Discrete Mathematics and Theoretical Computer Science | 2023年 / 252卷
基金：
中国国家自然科学基金;
关键词：
cycles; Multipartite tournaments; strong;
D O I：
10.46298/DMTCS.9732
中图分类号：
学科分类号：
摘要：
Let c be an integer. A c-partite tournament is an orientation of a complete c-partite graph. A c-partite tournament is rich if it is strong and each partite set has at least two vertices. In 1996, Guo and Volkmann characterized the structure of all rich c-partite tournaments without (c + 1)-cycles, which solved a problem by Bondy. They also put forward a problem that what the structure of rich c-partite tournaments without (c + k)-cycles for some k ≥ 2 is. In this paper, we answer the question of Guo and Volkmann for k = 2. © 2023 by the author(s).
引用
收藏
相关论文
共 10 条
  • [1] Balakrishnan R., Paulraja P., Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs, J. Graph Theory, 8, 3, pp. 423-426, (1984)
  • [2] Bang-Jensen J., Gutin G., Generalizations of tournaments: a survey, J. Graph Theory, 28, 4, pp. 171-202, (1998)
  • [3] Bang-Jensen J., Gutin G., Digraphs: Theory, algorithms and applications, Springer Monographs in Mathematics, (2001)
  • [4] Bang-Jensen J., Gutin G., Classes of directed graphs, Springer Monographs in Mathematics, (2018)
  • [5] Beineke L. W., Reid K. B., Tournaments, Selected topics in graph theory, (1978)
  • [6] Bondy J. A., Diconnected orientations and a conjecture of Las Vergnas, J. London Math. Soc. (2), 14, 2, pp. 277-282, (1976)
  • [7] Guo Y., Volkmann L., A complete solution of a problem of Bondy concerning multipartite tournaments, J. Combin. Theory Ser. B, 66, 1, pp. 140-145, (1996)
  • [8] Gutin G., On cycles in complete n-partite digraphs, Depon. in VINITI, (1982)
  • [9] Gutin G., Cycles in strong n-partite tournaments, Vestsı̄ Akad. Navuk BSSR Ser. Fı̄z.-Mat. Navuk, 5, pp. 105-106, (1984)
  • [10] Volkmann L., Multipartite tournaments: a survey, Discrete Math, 307, 24, pp. 3097-3129, (2007)
1