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)
pp. 342-386.
10.1002/rsa.21215.
Preview |
Text
2202.05215v3.pdf - Accepted Version Download (887kB) | Preview |
Abstract
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, that is, 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 two-universality, where we also fully address all open cases.
| Type: | Article |
|---|---|
| Title: | The square of a Hamilton cycle in randomly perturbed graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1002/rsa.21215 |
| Publisher version: | http://dx.doi.org/10.1002/rsa.21215 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | square of Hamilton cycle, 2-universality, thresholds, randomly perturbed graphs |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10191543 |
Archive Staff Only
 |
View Item |
