Hamiltonicity of graphs perturbed by a random geometric graph

DOI10.1002/JGT.22901zbMATH Open1522.05260arXiv2102.02321MaRDI QIDQ6094050FDOQ6094050

Authors: Alberto Espuny Díaz 

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/2102.02321

Recommendations

• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Hamilton cycles in random geometric graphs
• Random perturbation of sparse graphs
• Hamiltonicity in randomly perturbed hypergraphs
• Bridged Hamiltonian cycles in sub-critical random geometric graphs

zbMATH Keywords

random geometric graphsHamiltonicityabsorptionrandomly perturbed graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Spanning trees in randomly perturbed graphs
• Hamilton cycles in random geometric graphs
• How many random edges make a dense graph hamiltonian?
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• Universality for bounded degree spanning trees in randomly perturbed graphs
• Triangles in randomly perturbed graphs
• Bounded-Degree Spanning Trees in Randomly Perturbed Graphs
• Lectures on random geometric graphs
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Tilings in randomly perturbed dense graphs
• Hamilton \(\ell\)-cycles in randomly perturbed hypergraphs
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Hamiltonicity in randomly perturbed hypergraphs
• Random perturbation of sparse graphs
• Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
• Powers of Hamiltonian cycles in randomly augmented graphs
• Sprinkling a few random edges doubles the power
• Disjoint Hamilton cycles in the random geometric graph
• Hamiltonicity of graphs perturbed by a random regular graph
• High powers of Hamiltonian cycles in randomly augmented graphs

Cited In (8)

• On Hamiltonicity of uniform random intersection graphs
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Disjoint Hamilton cycles in the random geometric graph
• Hamilton cycles in random geometric graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Random perturbation of sparse graphs
• Hamiltonicity of graphs perturbed by a random regular graph
• Bridged Hamiltonian cycles in sub-critical random geometric graphs

This page was built for publication: Hamiltonicity of graphs perturbed by a random geometric graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6094050)