Conjecture on near-optimal Hamilton coverings of random graphs
Conjecture on near-optimal Hamilton coverings of random graphs
Let be the binomial random graph on vertices, and let a Hamilton covering be a collection of Hamilton cycles whose union contains every edge of . Here may depend on , and means that .
Hamilton covering conjecture. For any , the random graph a.a.s. admits a covering of its edges with at most
Hamilton cycles.
This would extend the paper's asymptotic equality between the largest Hamilton packing and smallest Hamilton covering to the full range where the random graph's minimum and maximum degrees are asymptotically equal. The authors state that the stronger lower bound used in their proof is likely only a proof artifact, and that this claim should hold whenever ; no resolution is given.
Sources & referencesView supporting material
Primary source
Roman Glebov, Michael Krivelevich and Tibor Szabó, “On covering expander graphs by Hamilton cycles”, arXiv:1111.3325 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.