A note on spanning Kr-cycles in random graphs

Alan Frieze; Alan Frieze

doi:10.3934/math.2020309

AIMS Mathematics

2020, Volume 5, Issue 5: 4849-4852. doi: 10.3934/math.2020309

Previous Article Next Article

Letter Special Issues

A note on spanning K_r-cycles in random graphs

Alan Frieze ^,

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh PA 15213, USA

Received: 28 May 2020 Accepted: 02 June 2020 Published: 03 June 2020
MSC : 05C80, 05C38

We find a threshold for the existence of a collection of edge disjoint copies of K_r that form a cyclic structure and span all vertices of G_{n, p}. We use a recent result of Riordan to give a two line proof of the main result.
- spanning,
- K_r-cycle,
- threshold
Citation: Alan Frieze. A note on spanning Kr-cycles in random graphs[J]. AIMS Mathematics, 2020, 5(5): 4849-4852. doi: 10.3934/math.2020309

Related Papers:

Abstract

We find a threshold for the existence of a collection of edge disjoint copies of K_r that form a cyclic structure and span all vertices of G_{n, p}. We use a recent result of Riordan to give a two line proof of the main result.

References

[1]	A. Dudek and A. M. Frieze, Loose Hamilton Cycles in Random k-Uniform Hypergraphs, Electronic J. Comb., 18 (2011), 48.
[2]	A. Dudek, A. M. Frieze, P. Loh, et al. Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs, Electronic J. Comb., 19 (2012), 44.
[3]	K. Frankston, J. Kahn, B. Narayanan, et al. Thresholds versus fractional expectation thresholds, 2019. Available from: https://arxiv.org/pdf/1910.13433.pdf.
[4]	A. M. Frieze, Loose Hamilton Cycles in Random 3-Uniform Hypergraphs, Electronic J. Comb., 17 (2010).
[5]	A. Heckel, Random triangles in random graphs, 2018. Available from: https://arxiv.org/pdf/1802.08472.pdf.
[6]	A. Johansson, J. Kahn and V. Vu, Factors in random graphs, Random Structures and Algorithms, 33 (2008), 1-28. doi: 10.1002/rsa.20224
[7]	O. Riordan, Random cliques in random graphs, 2018. Available from: https://arxiv.org/pdf/1802.01948.pdf.

Reader Comments

Your name:*

Email:*
© 2020 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)