Mathematics – Combinatorics
Scientific paper
2012-03-03
Mathematics
Combinatorics
Scientific paper
In a recent paper, we showed that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. The main consequence of this theorem is that every regular tournament on n vertices can be decomposed into (n-1)/2 edge-disjoint Hamilton cycles, whenever n is sufficiently large. This verified a conjecture of Kelly from 1968. In this paper, we derive a number of further consequences of our result on robust outexpanders, the main ones are the following: (i) an undirected analogue of our result on robust outexpanders; (ii) best possible bounds on the size of an optimal packing of edge-disjoint Hamilton cycles in a graph of minimum degree d for a large range of values for d. (iii) a similar result for digraphs of given minimum semidegree; (iv) an approximate version of a conjecture of Nash-Williams on Hamilton decompositions of dense regular graphs; (v) the observation that dense quasi-random graphs are robust outexpanders; (vi) a verification of the `very dense' case of a conjecture of Frieze and Krivelevich on packing edge-disjoint Hamilton cycles in random graphs; (vii) a proof of a conjecture of Erdos on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament.
Kühn Daniela
Osthus Deryk
No associations
LandOfFree
Hamilton decompositions of regular expanders: applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hamilton decompositions of regular expanders: applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hamilton decompositions of regular expanders: applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-345691