Optimal covers with Hamilton cycles in random graphs

Details Optimal covers with Hamilton cycles in random graphs Optimal covers with Hamilton cycles in random graphs

2012-03-17

arxiv.org/abs/1203.3868v1

Mathematics

Combinatorics

Scientific paper

A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in G_n,p a.a.s. has size \lfloor delta(G_n,p) /2 \rfloor. Glebov, Krivelevich and Szab\'o recently initiated research on the `dual' problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for log^{117}n / n < p < 1-n^{-1/8}, a.a.s. the edges of G_n,p can be covered by \lceil Delta(G_n,p)/2 \rceil Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szab\'o, which holds for p > n^{-1+\eps}. Our proof is based on a result of Knox, K\"uhn and Osthus on packing Hamilton cycles in pseudorandom graphs.

Affiliated with

Also associated with

No associations

Rating

Optimal covers with Hamilton cycles in random graphs 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 Optimal covers with Hamilton cycles in random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal covers with Hamilton cycles in random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-313114