High powers of Hamiltonian cycles in randomly augmented graphs
Preprint
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 $k\geq1$, $r\geq 0$, and $\ell\geq (r+1)r$, and for any $\alpha>\frac{k}{k+1}$ we show that adding $O(n^{2-2/\ell})$ random edges to an $n$-vertex graph $G$ with minimum degree at least $\alpha n$ yields, with probability close to one, the existence of the $(k\ell+r)$-th power of a Hamiltonian cycle. In particular, for $r=1$ and $\ell=2$ this implies that adding $O(n)$ random edges to such a graph $G$ already ensures the $(2k+1)$-st power of a Hamiltonian cycle (proved independently by Nenadov and Truji\'c). In this instance and for several other choices of $k$, $\ell$, and $r$ we can show that our result is asymptotically optimal.
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Sprinkling a Few Random Edges Doubles the PowerSIAM Journal on Discrete Mathematics, 2021
- Powers of Hamiltonian cycles in randomly augmented graphsRandom Structures & Algorithms, 2019
- Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphsRandom Structures & Algorithms, 2018
- Ramsey Properties of Random k-Partite, k-Uniform HypergraphsSIAM Journal on Discrete Mathematics, 2007
- 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