Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-25T18:14:09.306Z Has data issue: false hasContentIssue false

Decomposing Random Graphs into Few Cycles and Edges

Published online by Cambridge University Press:  29 December 2014

DÁNIEL KORÁNDI
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: [email protected], [email protected])
MICHAEL KRIVELEVICH
Affiliation:
School of Mathematical Sciences, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 6997801, Israel (e-mail: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, Rämistrasse 101, 8092 Zurich, Switzerland (e-mail: [email protected], [email protected])

Abstract

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

Type
Paper
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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 1736.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 257279.CrossRefGoogle Scholar
[6] Conlon, D., Fox, J. and Sudakov, B. (2014) Cycle packing. Random Struct. Alg. 45 608626.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 319.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 106112.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 359364.Google Scholar
[11] Pyber, L. (1985) An Erdős–Gallai conjecture. Combinatorica 5 6779.Google Scholar