Abstract
The study of arc-pancyclicity of tournaments has a long history. Let T be a regular c-partite tournament with partite sets \(V_1,V_2,\ldots ,V_c\). Alspach proved that every arc of a regular tournament is in a k-cycle for each \(k\in \{3,4,\ldots , n \}\). In this paper, we extend the concept of arc-pancyclicity of regular tournaments to regular multipartite tournaments. We prove that for any regular c-partite (\(c\ge 3\)) tournament T, if \([V_i,V_j]\ne \emptyset \), then there is a \((V_j, V_i)\)-path in T that transverses exactly k partite sets for each \(k\in \{4, \ldots , c\}\). This theorem is best possible in some sense and it confirms a conjecture proposed by Guo.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alspach, B.: Cycles of each length in regular tournaments. Can. Math. Bull. 10, 283–286 (1967)
Bang-Jensen, J., Gutin, G.: Classes of Directed Graphs. Springer Monographs in Mathematics (2018)
Bang-Jensen, J., Maddaloni, A., Simonsen, S.: Quasi-Hamiltonian paths in semicomplete multipartite digraphs. Discrete Appl. Math. 161, 889–898 (2013)
Guo, Y., Volkmann, L.: Cycles in multipartite tournaments. J. Comb. Theory Ser. B 62, 363–366 (1994)
Guo, Y., Kwak, J.: The cycle structure of regular multipartite tournaments. Discrete Appl. Math. 120, 109–116 (2002)
Guo, Y.: Extensions of Alspach’s theorem to regular multipartite tournaments (2022)
Volkmann, L.: Multipartite tournaments: a survey. Eur. J. Comb. 307, 3097–3129 (2007)
Zhou, G., Zhang, K.: Cycles containing a given arc in regular multipartite tournaments. Acta Math. Appl. Sin. 18, 681–684 (2002)
Acknowledgements
We would like to thank all reviewers for their careful reading of the manuscript and detailed comments that significantly improved the presentation of the paper.
Funding
The authors have not disclosed any funding.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by NSFC (12071351, 11571258) and NSFSPD (ZR2020MA043).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Cai, J., Xia, W. & Yan, G. \(Quasi _{\textrm{ps}}\)-Pancyclicity of Regular Multipartite Tournament. Graphs and Combinatorics 39, 91 (2023). https://doi.org/10.1007/s00373-023-02689-x
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02689-x