Decomposing random graphs into few cycles and edges

DOI10.1017/S0963548314000844zbMATH Open1371.05150arXiv1404.3306OpenAlexW2151710412MaRDI QIDQ5364258FDOQ5364258

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)

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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