Approximate Hamilton decompositions of robustly expanding regular digraphs

DOI10.1137/120880951MaRDI QIDQ2870512zbMATH OpenOpenAlexFDO

Authors Deryk Osthus, Katherine Staden

Publication date 21 January 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.2810, http://pure-oai.bham.ac.uk/ws/files/12291391/88095.pdf

zbMATH Keywords

Hamilton cyclesHamilton decompositionsrobust expansion

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Generalized Ramsey theory (05C55)

Abstract: We show that every sufficiently large r-regular digraph G which has linear degree and is a robust outexpander has an approximate decomposition into edge-disjoint Hamilton cycles, i.e. G contains a set of r-o(r) edge-disjoint Hamilton cycles. Here G is a robust outexpander if for every set S which is not too small and not too large, the `robust' outneighbourhood of S is a little larger than S. This generalises a result of K"uhn, Osthus and Treglown on approximate Hamilton decompositions of dense regular oriented graphs. It also generalises a result of Frieze and Krivelevich on approximate Hamilton decompositions of quasirandom (di)graphs. In turn, our result is used as a tool by K"uhn and Osthus to prove that any sufficiently large r-regular digraph G which has linear degree and is a robust outexpander even has a Hamilton decomposition.

Recommendations

• Hamilton decompositions of regular expanders: applications
• A survey on Hamilton cycles in directed graphs
• Hamilton cycles in sparse robustly expanding digraphs
• Finding Hamilton cycles in robustly expanding digraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments

Cited in

(10)

• Hamilton cycles in sparse robustly expanding digraphs
• Hamilton decompositions of regular expanders: applications
• The robust component structure of dense regular graphs and applications
• Finding Hamilton cycles in robustly expanding digraphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• A survey on Hamilton cycles in directed graphs
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• The robust component structure of dense regular graphs
• Path decompositions of tournaments
• A note on Hamilton decompositions of even-regular multigraphs

This page was built for publication: Approximate Hamilton decompositions of robustly expanding regular digraphs

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