Covering cycles in sparse graphs

DOI10.1002/RSA.21045MaRDI QIDQ6074700zbMATH OpenOpenAlexFDO

Authors Frank Mousset, Nemanja Škorić, Miloš Trujić

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.03311

zbMATH Keywords

absorbing methodcovering cyclespseudo-random graphsrandom graphsresilience

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $kgeq2$ be an integer. Kouider and Lonc proved that the vertex set of every graph $G$ with $ngeq{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 $alpha>0$ and $p=p(n)in(0,1]$, the same conclusion holds for graphs $G$ with minimum degree $(1/k+alpha)np$ that are sparse in the sense that [ e_G(X,Y) leq p|X||Y| + o(npsqrt{|X||Y|}/log^3 n) qquad forall X,Ysubseteq 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.

Recommendations

• Stability for vertex cycle covers
• Covering a graph with cycles
• Degree Sums and Covering Cycles
• Covering vertices by cycles
• Coverings of the vertices of a graph by small cycles

Cites work

• A condition for matchability in hypergraphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Almost all Steiner triple systems have perfect matchings
• Combinatorial theorems relative to a random set
• Corrádi and Hajnal's theorem for sparse random graphs
• Covering cycles and \(k\)-term degree sums
• Decompositions into isomorphic rainbow spanning trees
• Dirac's theorem for random graphs
• Hamiltonicity in random directed graphs is born resilient
• Hamiltonicity in random graphs is born resilient
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• scientific article; zbMATH DE number 4191728 (Why is no real title available?)
• scientific article; zbMATH DE number 7225155 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Large-scale structures in random graphs
• Local resilience of almost spanning trees in random graphs
• Local resilience of an almost spanning k‐cycle in random graphs
• Local resilience of graphs
• Long cycles in subgraphs of (pseudo)random directed graphs
• On Komlós' tiling theorem in random graphs
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Proof of the Seymour conjecture for large graphs
• Pseudo-random graphs
• Pósa's conjecture for graphs of order at least 2 × 10⁸
• Resilience of perfect matchings and Hamiltonicity in random graph processes
• Robust Hamiltonicity of random directed graphs
• Robustness of graph properties
• Small subsets inherit sparse \(\varepsilon\)-regularity
• Some Theorems on Abstract Graphs
• Spanning trees in random graphs
• Stability for vertex cycle covers
• Szemerédi's regularity Lemma for matrices and sparse graphs
• The bandwidth theorem in sparse graphs
• Triangle Factors in Random Graphs
• Vertex coverings by monochromatic cycles and trees

Cited in

(3)

• Stability for vertex cycle covers
• Improved sparse covers for graphs excluding a fixed minor
• A Lower Bound on Cycle-Finding in Sparse Digraphs

This page was built for publication: Covering cycles in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074700)