Sharp threshold for hamiltonicity of random geometric graphs

2006/07/07 by J. Diaz, Diaz, J., D. Mitsche +3 · 2 citations
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0607023

10 pages, 2 figures

arxiv created 2006/07/07 · arxiv updated 2009/12/01

Abstract

We show for an arbitrary ℓ_p norm that the property that a random geometric graph \mathcal G(n,r) contains a Hamiltonian cycle exhibits a sharp threshold at r=r(n)=√((log n)/(α_p n)), where α_p is the area of the unit disk in the ℓ_p norm. The proof is constructive and yields a linear time algorithm for finding a Hamiltonian cycle of \RG a.a.s., provided r=r(n)≥√((log n)/((α_p -ε)n)) for some fixed ε> 0.

Cited by

• Sharp thresholds, hitting times and the power of choice for random geometric graphs
• Spanning trees of bounded degree in random geometric graphs

Related

• Square of Hamilton cycle in a random graph
• The threshold for the square of a Hamilton cycle
• Square of a Hamilton cycle in a random graph
• Hamiltonicity of the random geometric graph
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs