Hamiltonicity of graphs perturbed by a random geometric graph

We study Hamiltonicity in graphs obtained as the union of a deterministic n $n$‐vertex graph H $H$ with linear degrees and a d $d$‐dimensional random geometric graph G d ( n , r ) ${G}^{d}(n,r)$, for any d ≥ 1 $d\ge 1$. We obtain an asymptotically optimal bound on the minimum r $r$ for which a.a.s....

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2023-05, Vol.103 (1), p.12-22
Main Author: Espuny Díaz, Alberto
Format: Article
Language:English
Subjects:
absorption
Algorithms
Gadolinium
Graphs
Hamiltonicity
random geometric graphs
randomly perturbed graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study Hamiltonicity in graphs obtained as the union of a deterministic n $n$‐vertex graph H $H$ with linear degrees and a d $d$‐dimensional random geometric graph G d ( n , r ) ${G}^{d}(n,r)$, for any d ≥ 1 $d\ge 1$. We obtain an asymptotically optimal bound on the minimum r $r$ for which a.a.s. H ∪ G d ( n , r ) $H\cup {G}^{d}(n,r)$ is Hamiltonian. Our proof provides a linear time algorithm to find a Hamilton cycle in such graphs.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22901