High powers of Hamiltonian cycles in randomly augmented graphs
- 21 June 2021
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 98 (2) , 255-284
Abstract
We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers , and , and for any we show that adding random edges to an -vertex graph with minimum degree at least yields, with probability close to one, the existence of the -th power of a Hamiltonian cycle. In particular, for and this implies that adding random edges to such a graph already ensures the -st power of a Hamiltonian cycle (proved independently by Nenadov and Trujić). In this instance and for several other choices of , and we can show that our result is asymptotically optimal.
Keywords
All Related Versions
Funding Information
- Simons Foundation (522400)
- European Research Council (PEPCo 724903)
- Narodowe Centrum Nauki (2018/29/B/ST1/00426)
This publication has 10 references indexed in Scilit:
- EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHSMathematika, 2020
- Powers of Hamiltonian cycles in randomly augmented graphsRandom Structures & Algorithms, 2019
- Ramsey Properties of Random k-Partite, k-Uniform HypergraphsSIAM Journal on Discrete Mathematics, 2007
- How many random edges make a dense graph hamiltonian?Random Structures & Algorithms, 2002
- Wiley‐Interscience Series in Discrete Mathematics and Optimization2000
- On the P sa-Seymour conjectureJournal of Graph Theory, 1998
- H-Factors in Dense GraphsJournal of Combinatorial Theory, Series B, 1996
- Supersaturated graphs and hypergraphsCombinatorica, 1983
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964
- Some Theorems on Abstract GraphsProceedings of the London Mathematical Society, 1952