The square of a Hamilton cycle in randomly perturbed graphs
Böttcher, J.
, Parczyk, O., Sgueglia, A. & Skokan, J.
(2024).
The square of a Hamilton cycle in randomly perturbed graphs.
Random Structures and Algorithms,
65(2), 342 - 386.
https://doi.org/10.1002/rsa.21215
, Parczyk, O., Sgueglia, A. & Skokan, J.
(2024).
The square of a Hamilton cycle in randomly perturbed graphs.
Random Structures and Algorithms,
65(2), 342 - 386.
https://doi.org/10.1002/rsa.21215
We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given α ∈ (0, 1), the union of any n-vertex graph with minimum degree αn and the binomial random graph G(n, p). This is known when α > 1/2 and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each α ≤ 1/2. We demonstrate that, as α ranges over the interval (0, 1), the threshold performs a countably infinite number of ‘jumps’. Our result has implications on the perturbed threshold for 2-universality, where we also fully address all open cases.