Covering cycles in sparse graphs. Issue 4 (27th September 2021) - Mousset, Frank; Škorić, Nemanja; Trujić, Miloš
Abstract: Let k ≥ 2 be an integer. Kouider and Lonc proved that the vertex set of every graph G with n ≥ n 0 ( k ) vertices and minimum degree at least n / k can be covered by k − 1 cycles. Our main result states that for every α > 0 and p = p ( n ) ∈ ( 0, 1 ], the same conclusion holds for graphs G with minimum degree ( 1 / k + α ) n p that are sparse in the sense that e G ( X, Y ) ≤ p | X | | Y | + o ( n p | X | | Y | / log 3 n ) ∀ X, Y ⊆ V ( G ) . In particular, this allows us to determine the local resilience of random and pseudorandom graphs with respect to having a vertex cover by a fixed number of cycles. The proof uses a version of the absorbing method in sparse expander graphs.