Hamiltonicity of graphs perturbed by a random geometric graph

Abstract

We study Hamiltonicity in graphs obtained as the union of a deterministic $n$-vertex graph $H$ with linear degrees and a $d$-dimensional random geometric graph $G^d(n,r)$, for any $d\ge 1$. We obtain an asymptotically optimal bound on the minimum $r$ for which a.a.s. $H\cup G^d(n,r)$ is Hamiltonian. Our proof provides a linear time algorithm to find a Hamilton cycle in such graphs.

To appear in Journal of Graph Theory

References in corpus (1)

• Triangles in randomly perturbed graphs

Cited by in corpus (1)

• Rainbow trees in uniformly edge-coloured graphs