Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs
Preprint
Abstract
We study the question of the least number of random edges that need to be added to a Pósa-Seymour graph, that is, a graph with minimum degree exceeding $\frac k{k+1}n$, to secure the existence of the $m$-th power of a Hamiltonian cycle, $m>k$. It turns out that, depending on $k$ and $m$, this quantity may be captured by two types of thresholds, with one of them, called over-threshold, becoming dominant for large $m$. Indeed, for each $k\ge2$ and $m>m_0(k)$, we establish asymptotically tight lower and upper bounds on the over-thresholds (provided they exist) and show that for infinitely many instances of $m$ the two bounds coincide. In addition, we also determine the thresholds for some small values of $k$ and $m$.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- The square of a Hamilton cycle in randomly perturbed graphsRandom Structures & Algorithms, 2024
- Powers of Hamiltonian cycles in randomly augmented Dirac graphs—The complete collectionJournal of Graph Theory, 2023
- High powers of Hamiltonian cycles in randomly augmented graphsJournal of Graph Theory, 2021
- Sprinkling a Few Random Edges Doubles the PowerSIAM Journal on Discrete Mathematics, 2021
- Powers of Hamiltonian cycles in randomly augmented graphsRandom Structures & Algorithms, 2019
- How many random edges make a dense graph hamiltonian?Random Structures & Algorithms, 2002