2012/06/13 by Deryk Osthus, Katherine Staden, Osthus, Deryk +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1206.2810
openalex publication_date 2012/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that every sufficiently large r-regular digraph G which has linear\ndegree and is a robust outexpander has an approximate decomposition into\nedge-disjoint Hamilton cycles, i.e. G contains a set of r-o(r) edge-disjoint\nHamilton cycles. Here G is a robust outexpander if for every set S which is not\ntoo small and not too large, the `robust' outneighbourhood of S is a little\nlarger than S. This generalises a result of K "uhn, Osthus and Treglown on\napproximate Hamilton decompositions of dense regular oriented graphs. It also\ngeneralises a result of Frieze and Krivelevich on approximate Hamilton\ndecompositions of quasirandom (di)graphs. In turn, our result is used as a tool\nby K "uhn and Osthus to prove that any sufficiently large r-regular digraph G\nwhich has linear degree and is a robust outexpander even has a Hamilton\ndecomposition.\n