Sharp Threshold for Hamiltonicity of Random Geometric Graphs

Abstract: We show for an arbitrary

e l l_{p}

norm that the property that a random geometric graph

m a t h c a l G (n, r)

contains a Hamiltonian cycle exhibits a sharp threshold at

r = r (n) = s q r t f r a c l o g n a l p h a_{p} n

, where

a l p h a_{p}

is the area of the unit disk in the

e l l_{p}

norm. The proof is constructive and yields a linear time algorithm for finding a Hamiltonian cycle of

R G

a.a.s., provided

r = r (n) g e s q r t f r a c l o g n (a l p h a_{p} - e p s i l o n) n

for some fixed

e p s i l o n > 0

.

Recommendations

Cited in

(14)

This page was built for publication: Sharp Threshold for Hamiltonicity of Random Geometric Graphs