Hamiltonicity of Randomly Perturbed Graphs

The theory of randomly perturbed graphs deals with the properties of graphs obtained as the union of a deterministic graph H and a random graph G. We study Hamiltonicity in two distinct settings. In both of them, we assume H is some deterministic graph with minimum degree at least \(\alpha n\), for some \(\alpha \) (possibly depending on n). We first consider the case when G is a random geometric graph, and obtain an asymptotically optimal result. We then consider the case when G is a random regular graph, and obtain different results depending on the regularity.