  We study 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. It follows from the theorems of Dirac and of Koml\'os, Sark\"ozy, and
Szemer\'edi that for every $k\geq 1$ and sufficiently large $n$ already the
minimum degree $\delta(G)\ge\tfrac{k}{k+1}n$ for an $n$-vertex graph $G$ alone
suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. Here
we show that under essentially the same degree assumption the addition of just
$O(n)$ random edges ensures the presence of the $(k+1)$-st power of a
Hamiltonian cycle with probability close to one.
