Complementary cycles of any length in regular bipartite tournaments

02/08/2021

∙

by   Stéphane Bessy, et al.

∙

0

∙

share

Let D be a k-regular bipartite tournament on n vertices. We show that, for every p with 2 ≤ p ≤ n/2-2, D has a cycle C of length 2p such that D ∖ C is hamiltonian unless D is isomorphic to the special digraph F_4k. This statement was conjectured by Manoussakis, Song and Zhang [K. Zhang, Y. Manoussakis, and Z. Song. Complementary cycles containing a fixed arc in diregular bipartite tournaments. Discrete Mathematics, 133(1-3):325–328,1994]. In the same paper, the conjecture was proved for p=2 and more recently Bai, Li and He gave a proof for p=3 [Y. Bai, H. Li, and W. He. Complementary cycles in regular bipartite tournaments. Discrete Mathematics, 333:14–27, 2014].