  Let $G$ be an $n$-vertex graph, where $\delta(G) \geq \delta n$ for some
$\delta := \delta(n)$. A result of Bohman, Frieze and Martin from 2003 asserts
that if $\alpha(G) = O \left(\delta^2 n \right)$, then perturbing $G$ via the
addition of $\omega \left(\frac{\log(1/\delta)}{\delta^3} \right)$ random
edges, asymptotically almost surely (a.a.s. hereafter) results in a Hamiltonian
graph. This bound on the size of the random perturbation is only tight when
$\delta$ is independent of $n$ and deteriorates as to become uninformative when
$\delta = \Omega \left(n^{-1/3} \right)$.
  We prove several improvements and extensions of the aforementioned result.
First, keeping the bound on $\alpha(G)$ as above and allowing for $\delta =
\Omega(n^{-1/3})$, we determine the correct order of magnitude of the number of
random edges whose addition to $G$ a.a.s. results in a pancyclic graph. Our
second result ventures into significantly sparser graphs $G$; it delivers an
almost tight bound on the size of the random perturbation required to ensure
pancyclicity a.a.s., assuming $\delta(G) = \Omega \left((\alpha(G) \log n)^2
\right)$ and $\alpha(G) \delta(G) = O(n)$.
  Assuming the correctness of Chv\'atal's toughness conjecture, allows for the
mitigation of the condition $\alpha(G) = O \left(\delta^2 n \right)$ imposed
above, by requiring $\alpha(G) = O(\delta(G))$ instead; our third result
determines, for a wide range of values of $\delta(G)$, the correct order of
magnitude of the size of the random perturbation required to ensure the a.a.s.
pancyclicity of $G$.
  For the emergence of nearly spanning cycles, our fourth result determines,
under milder conditions, the correct order of magnitude of the size of the
random perturbation required to ensure that a.a.s. $G$ contains such a cycle.
