The square of a Hamilton cycle in randomly perturbed graphs
Böttcher, J.
, Parczyk, O., Sgueglia, A. & Skokan, J.
(2021).
The square of a Hamilton cycle in randomly perturbed graphs.
In
Nešetřil, J., Perarnau, G., Rué, J. & Serra, O.
(Eds.),
Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications
(pp. 644 - 650).
Birkhäuser (Firm).
https://doi.org/10.1007/978-3-030-83823-2_103
, Parczyk, O., Sgueglia, A. & Skokan, J.
(2021).
The square of a Hamilton cycle in randomly perturbed graphs.
In
Nešetřil, J., Perarnau, G., Rué, J. & Serra, O.
(Eds.),
Extended Abstracts EuroComb 2021: European Conference on Combinatorics, Graph Theory and Applications
(pp. 644 - 650).
Birkhäuser (Firm).
https://doi.org/10.1007/978-3-030-83823-2_103
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. Our result has implications on the perturbed threshold for 2-universality, where we also fully address all open cases.