Hamiltonicity of graphs perturbed by a random geometric graph

DOI10.1002/JGT.22901MaRDI QIDQ6094050zbMATH OpenFDO

Authors Alberto Espuny Díaz

Publication date 9 October 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(8)

• On Hamiltonicity of uniform random intersection graphs
• Bridged Hamiltonian cycles in sub-critical random geometric 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

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)