Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments

DOI10.1112/plms/pdu019zbMath1302.05069arXiv1303.4213OpenAlexW2133832791WikidataQ123082537 ScholiaQ123082537MaRDI QIDQ2922881

Viresh Patel, Daniela Kühn, Deryk Osthus, John Lapinskas

Publication date: 15 October 2014

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton cycleThomassen's conjecturestrongly connected tournamentstrongly \(f(k)\)-connected tournament

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items (14)

Every \((13k - 6)\)-strong tournament with minimum out-degree at least \(28k - 13\) is \(k\)-linked ⋮ Bipartitions of highly connected tournaments ⋮ Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths ⋮ Sparse Spanning $k$-Connected Subgraphs in Tournaments ⋮ Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs ⋮ Improved results on linkage problems ⋮ Highly linked tournaments ⋮ An improved linear connectivity bound for tournaments to be highly linked ⋮ On 1-factors with prescribed lengths in tournaments ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ \((2k+1)\)-connected tournaments with large minimum out-degree are \(k\)-linked ⋮ Tournaments and Semicomplete Digraphs ⋮ Highly linked tournaments with large minimum out-degree ⋮ Tight bounds for powers of Hamilton cycles in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• A survey on Hamilton cycles in directed graphs
• Improved sorting networks with O(log N) depth
• Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
• Sorting in \(c \log n\) parallel steps
• The directed subgraph homeomorphism problem
• Highly connected non-2-linked digraphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• An improved linear edge bound for graph linkages
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hamilton decompositions of regular expanders: applications
• Highly linked graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Triangle Factors in Random Graphs
• Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree
• On Subtournaments of a Tournament

This page was built for publication: Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments