Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs

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$.