The square of a Hamilton cycle in randomly perturbed graphs
Böttcher, Julia
; Parczyk, Olaf; Sgueglia, Amedeo; and Skokan, Jozef
(2021)
The square of a Hamilton cycle in randomly perturbed graphs
In:
Extended Abstracts EuroComb 2021:European Conference on Combinatorics, Graph Theory and Applications.
Research Perspectives CRM Barcelona
.
Birkhäuser (Firm), Cham, CH, 644 - 650.
ISBN 9783030838225
; Parczyk, Olaf; Sgueglia, Amedeo; and Skokan, Jozef
(2021)
The square of a Hamilton cycle in randomly perturbed graphs
In:
Extended Abstracts EuroComb 2021:European Conference on Combinatorics, Graph Theory and Applications.
Research Perspectives CRM Barcelona
.
Birkhäuser (Firm), Cham, CH, 644 - 650.
ISBN 9783030838225
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.
-
picture_as_pdf -
subject - Accepted Version
Downloads