Covering Random Digraphs with Hamilton Cycles

2024/10/16 by Ferber, Asaf, Sales, Marcelo, Shurman, Mason
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.12964

Abstract

A covering of a digraph D by Hamilton cycles is a collection of directed Hamilton cycles (not necessarily edge-disjoint) that together cover all the edges of D. We prove that for 1/2 ≥ p≥ \fraclog²⁰ nn, the random digraph D_n,p typically admits an optimal Hamilton cycle covering. Specifically, the edges of D_n,p can be covered by a family of t Hamilton cycles, where t is the maximum of the the in-degree and out-degree of the vertices in D_n,p. Notably, t is the best possible bound, and our assumption on p is optimal up to a polylogarithmic factor.

Related

• Packing, Counting and Covering Hamilton cycles in random directed graphs
• Packing and counting arbitrary Hamilton cycles in random digraphs
• Minimum degree edge-disjoint Hamilton cycles in random directed graphs
• Optimal covers with Hamilton cycles in random graphs
• Hamilton cycles in random digraphs with minimum degree at least one