Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-06T19:41:20.271Z Has data issue: false hasContentIssue false
  • English
  • Français

Decomposing Random Graphs into Few Cycles and Edges

Part of: Graph theory

Published online by Cambridge University Press:  29 December 2014

DÁNIEL KORÁNDI ,
MICHAEL KRIVELEVICH  and
BENNY SUDAKOV
DÁNIEL KORÁNDI
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: daniel.korandi@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel (e-mail: krivelev@post.tau.ac.il)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: daniel.korandi@math.ethz.ch, benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Over 50 years ago, Erdő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 n → ∞. In this paper we show that for most edge probabilities G(n, p) can be decomposed into a union of n/4 + np/2 + o(n) cycles and edges w.h.p. This result is asymptotically tight.

MSC classification

Primary: 05C38: Paths and cycles
Secondary: 05C80: Random graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Issue 6 , November 2015 , pp. 857 - 872
Copyright
Copyright © Cambridge University Press 2014 

References

[1] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley.Google Scholar
[2] Bollobás, B. (2001) Random Graphs, second edition, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[3] Brandt, S., Broersma, H., Diestel, R. and Kriesell, M. (2006) Global connectivity and expansion: Long cycles and factors in f-connected graphs. Combinatorica 26 17–36.CrossRefGoogle Scholar
[4] Broder, A. Z., Frieze, A. M., Suen, S. and Upfal, E. (1996) An efficient algorithm for the vertex-disjoint paths problem in random graphs. In Proc. Seventh Annual ACM–SIAM Symposium on Discrete Algorithms: SODA '96, SIAM, pp. 261–268.Google Scholar
[5] Chung, F. and Lu, L. (2001) The diameter of sparse random graphs. Adv. Appl. Math. 26 257–279.CrossRefGoogle Scholar
[6] Conlon, D., Fox, J. and Sudakov, B. (2014) Cycle packing. Random Struct. Alg. 45 608–626.CrossRefGoogle Scholar
[7] Erdős, P. (1983) On some of my conjectures in number theory and combinatorics. In Proc. Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Boca Raton 1983), Congr. Numer. 39 3–19.Google Scholar
[8] Erdős, P., Goodman, A. W. and Pósa, L. (1966) The representation of a graph by set intersections. Canad. J. Math. 18 106–112.CrossRefGoogle Scholar
[9] Knox, F., Kühn, D. and Osthus, D. Edge-disjoint Hamilton cycles in random graphs. Random Struct. Alg., to appear.Google Scholar
[10] Pósa, L. (1976) Hamiltonian circuits in random graphs. Discrete Math. 14 359–364.Google Scholar
[11] Pyber, L. (1985) An Erdős–Gallai conjecture. Combinatorica 5 67–79.Google Scholar