An approximate version of Jackson's conjecture

DOI10.1017/S0963548320000152MaRDI QIDQ4993113zbMATH OpenOpenAlexWikidataFDO

Authors Anita Liebenau, Yanitsa Pehova

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

diregular bipartite tournamentHamilton cycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Graph designs and isomorphic decomposition (05C51) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 1981 Jackson showed that the diregular bipartite tournament (a complete bipartite graph whose edges are oriented so that every vertex has the same in- and outdegree) contains a Hamilton cycle, and conjectured that in fact the edge set of it can be partitioned into Hamilton cycles. We prove an approximate version of this conjecture: For every $c>1/2$ and $varepsilon>0$ there exists $n_0$ such that every $cn$-regular bipartite digraph on $2ngeq{n}_0$ vertices contains $(1-varepsilon)cn$ edge-disjoint Hamilton cycles.

Recommendations

• scientific article; zbMATH DE number 54800
• Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang conjecture
• Hamilton decompositions of regular tournaments
• scientific article; zbMATH DE number 29720
• Complementary cycles of any length in regular bipartite tournaments

Cites work

• An exact minimum degree condition for Hamilton cycles in oriented graphs
• Counting Hamilton decompositions of oriented graphs
• Hamilton Cycles in Oriented Graphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Hamilton decompositions of regular tournaments
• Hamiltonian decomposition of complete regular multipartite digraphs
• Hamiltonian decompositions of complete graphs
• scientific article; zbMATH DE number 4173021 (Why is no real title available?)
• scientific article; zbMATH DE number 3149611 (Why is no real title available?)
• scientific article; zbMATH DE number 3349889 (Why is no real title available?)
• scientific article; zbMATH DE number 3353327 (Why is no real title available?)
• Introduction to Random Graphs
• Long paths and cycles in oriented graphs
• Note on Hamilton Circuits
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Some Theorems on Abstract Graphs
• The probabilistic method
• The wonderful Walecki construction

Cited in

(3)

• scientific article; zbMATH DE number 5524994 (Why is no real title available?)
• Hamiltonicity, pancyclicity, and full cycle extendability in multipartite tournaments
• Hamiltonian degree sequences in digraphs

This page was built for publication: An approximate version of Jackson's conjecture

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