Bridged Hamiltonian Cycles in Sub-critical Random Geometric Graphs

Ghurumuruhan Ganesan ()
Additional contact information
Ghurumuruhan Ganesan: HBNI

Sankhya A: The Indian Journal of Statistics, 2023, vol. 85, issue 1, No 28, 706 pages

Abstract: Abstract In this paper, we consider a random geometric graph (RGG) G on n nodes with adjacency distance rn 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 →∞, we can obtain a Hamiltonian cycle with maximum bridge length a constant multiple of rn 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.

Keywords: Random geometric graphs; Hamiltonian cycles with bridges.; Primary: 60J10, 60K35; Secondary: 60C05, 62E10, 90B15, 91D30 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s13171-021-00273-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sankha:v:85:y:2023:i:1:d:10.1007_s13171-021-00273-0

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/13171

DOI: 10.1007/s13171-021-00273-0

Access Statistics for this article

Sankhya A: The Indian Journal of Statistics is currently edited by Dipak Dey

More articles in Sankhya A: The Indian Journal of Statistics from Springer, Indian Statistical Institute
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().