Bridged Hamiltonian cycles in sub-critical random geometric graphs

DOI10.1007/S13171-021-00273-0MaRDI QIDQ6133739zbMATH OpenOpenAlexWikidataFDO

Authors Ghurumuruhan Ganesan

Publication date 21 August 2023

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

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

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)

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.

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

Cites work

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

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)