Decomposing random graphs into few cycles and edges

DOI10.1017/S0963548314000844MaRDI QIDQ5364258zbMATH OpenOpenAlexFDO

Authors Dániel Korándi, Michael Krivelevich, Benny Sudakov

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Paths and cycles (05C38) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Over 50 years ago, ErdH{o}s and Gallai conjectured that the edges of every graph on $n$ vertices can be decomposed into $O(n)$ cycles and edges. Among other results, Conlon, Fox and Sudakov recently proved that this holds for the random graph $G(n,p)$ with probability approaching 1 as $nightarrowinfty$. In this paper we show that for most edge probabilities $G(n,p)$ can be decomposed into a union of $fracn4+fracnp2+o(n)$ cycles and edges whp. This result is asymptotically tight.

Recommendations

• Cycle packing
• Path and cycle decompositions of dense graphs
• Approximate Hamilton decompositions of random graphs

Cites work

• An Erdős-Gallai conjecture
• Cycle packing
• Edge-disjoint Hamilton cycles in random graphs
• Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs
• Hamiltonian circuits in random graphs
• scientific article; zbMATH DE number 3857112 (Why is no real title available?)
• scientific article; zbMATH DE number 871922 (Why is no real title available?)
• Paths in graphs
• The diameter of sparse random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Representation of a Graph by Set Intersections

Cited in

(11)

• Partitioning random graphs into large cycles
• Decomposing toroidal graphs into circuits and edges
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Path and cycle decompositions of dense graphs
• Cycles and Unicyclic Components in Random Graphs
• Decomposing graphs into edges and triangles
• Cycle packing
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Towards the Erdős-Gallai cycle decomposition conjecture
• Towards the Erdős-Gallai cycle decomposition conjecture
• Path decompositions of Eulerian graphs

This page was built for publication: Decomposing random graphs into few cycles and edges

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