On covering expander graphs by hamilton cycles. Issue 2 (10th August 2012) - Glebov, Roman; Krivelevich, Michael; Szabó, Tibor
Abstract The problem of packing Hamilton cycles in random and pseudorandom graphs has been studied extensively. In this paper, we look at the dual question of covering all edges of a graph by Hamilton cycles and prove that if a graph with maximum degree Δ satisfies some basic expansion properties and contains a family of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2rngd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1−o(1))Δ/2</alternatives> edge disjoint Hamilton cycles, then there also exists a covering of its edges by <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2rnhz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1+o(1))Δ/2</alternatives> Hamilton cycles. This implies that for every α > 0 and every <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2rnjh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p≥nα−1</alternatives> there exists a covering of all edges of G(n, p) by <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2rnk2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1+o(1))np/2</alternatives> Hamilton cycles asymptotically almost surely, which is nearly optimal.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 183‐200, 2014