Hamiltonicity of graphs perturbed by a random geometric graph

GND
1229848681
VIAF
359161696233716120001
Affiliation
Institut für Mathematik Technische Universität Ilmenau Ilmenau Germany
Espuny Díaz, Alberto

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 ≥ 1. We obtain an asymptotically optimal bound on the minimum r for which a.a.s. H ∪ G d (n, r) is Hamiltonian. Our proof provides a linear time algorithm to find a Hamilton cycle in such graphs.

Cite

Citation style:
Could not load citation form.

Rights

License Holder: © 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.

Use and reproduction: