Bridged Hamiltonian cycles in sub-critical random geometric graphs

DOI10.1007/S13171-021-00273-0zbMATH Open1519.05220arXiv2112.05641OpenAlexW4200365948WikidataQ114220233 ScholiaQ114220233MaRDI QIDQ6133739FDOQ6133739

Authors: Ghurumuruhan Ganesan 

Publication date: 21 August 2023

Published in: Sankhyā. Series A (Search for Journal in Brave)

Abstract: In this paper, we consider a random geometric graph (RGG)~(G) on~(n) nodes with adjacency distance~(r_n) just below the Hamiltonicity threshold and construct Hamiltonian cycles using additional edges called bridges. The bridges by definition do not belong to~(G) and we are interested in estimating the number of bridges and the maximum bridge length, needed for constructing a Hamiltonian cycle. In our main result, we show that with high probability, i.e. with probability converging to one as~(n ightarrow infty,) we can obtain a Hamiltonian cycle with maximum bridge length a constant multiple of~(r_n) and containing an arbitrarily small fraction of edges as bridges. We use a combination of backbone construction and iterative cycle merging to obtain the desired Hamiltonian cycle.

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

Recommendations

• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Hamilton cycles in random geometric graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• On the number of hamilton cycles in a random graph
• On two Hamilton cycle problems in random graphs

zbMATH Keywords

random geometric graphsHamiltonian cycles with bridges

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Characterization and structure theory of statistical distributions (62E10) Social networks; opinion dynamics (91D30) Combinatorial probability (60C05) Eulerian and Hamiltonian graphs (05C45) Stochastic network models in operations research (90B15)

Cites Work

• Random Geometric Graphs
• The longest edge of the random minimal spanning tree
• Hamilton cycles in random geometric graphs
• Size of the giant component in a random geometric graph
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Disjoint Hamilton cycles in the random geometric graph
• Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Cited In (1)

• Hamiltonicity of graphs perturbed by a random geometric graph

This page was built for publication: Bridged Hamiltonian cycles in sub-critical random geometric graphs

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