Complementary cycles of any length in regular bipartite tournaments

DOI10.1002/JGT.22914zbMATH Open1522.05156arXiv2102.04514OpenAlexW3128440614MaRDI QIDQ6074575FDOQ6074575

Authors: Stéphane Bessy, Jocelyn Thiebaut 

Publication date: 12 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let $D$ be a $k$-regular bipartite tournament on $n$ vertices. We show that, for every $p$ with $2leplen/2-2$, $D$ has a cycle $C$ of length $2p$ such that $DsetminusC$ 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].

Full work available at URL: https://arxiv.org/abs/2102.04514

Recommendations

• Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang conjecture
• Complementary cycles in regular bipartite tournaments
• scientific article; zbMATH DE number 398963
• scientific article; zbMATH DE number 2145367
• scientific article; zbMATH DE number 123398

zbMATH Keywords

cyclecomplementary cyclesregular bipartite tournamentscycle-factor

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12) Paths and cycles (05C38)

Cites Work

• Graph theory
• Cycles and paths in bipartite tournaments with spanning configurations
• Digraphs
• Title not available (Why is that?)
• On Subtournaments of a Tournament
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Title not available (Why is that?)
• Complementary cycles containing a fixed arc in diregular bipartite tournaments
• The partition of a strong tournament
• Partitioning vertices of a tournament into independent cycles
• Complementary cycles in regular bipartite tournaments
• Title not available (Why is that?)
• Complementary cycles of all lengths in tournaments
• Cycles in digraphs– a survey
• Diregularc-partite tournaments are vertex-pancyclic whenc ? 5

Cited In (5)

• Complementary cycles in regular bipartite tournaments
• An approximate version of Jackson's conjecture
• Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Complementary cycles of any length in regular bipartite tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074575)