Hamiltonicity of graphs perturbed by a random geometric graph

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\geq1\). We obtain an asymptotically optimal bound on the minimum \(r\) for which a.a.s. \(H\cup G^d(n,r)\) i...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-09
Main Author: Alberto Espuny Díaz
Format: Article
Language:English
Subjects:
Algorithms
Graphs
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\)-vertex graph \(H\) with linear degrees and a \(d\)-dimensional random geometric graph \(G^d(n,r)\), for any \(d\geq1\). 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.
ISSN:2331-8422
DOI:10.48550/arxiv.2102.02321