Covering cycles in sparse graphs. Issue 4 (27th September 2021)

• Record Type: Journal Article
• Authors: Mousset, Frank; Škorić, Nemanja; Trujić, Miloš
• Is Part Of: Random structures & algorithms. Volume 60:Issue 4(2022)
• Page Start: 716
• Page End: 748
• Publication Date: 2021-09-27
• Subjects: absorbing method -- covering cycles -- pseudo‐random graphs -- random graphs -- resilience; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21045
• Languages: English
• ISSNs: 1042-9832

Abstract

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.