Sharp threshold for hamiltonicity of random geometric graphs

Details Sharp threshold for hamiltonicity of random geometric graphs Sharp threshold for hamiltonicity of random geometric graphs

2006-07-07

arxiv.org/abs/cs/0607023v1

Computer Science

Discrete Mathematics

10 pages, 2 figures

Scientific paper

We show for an arbitrary $\ell_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)=\sqrt{\frac{\log n}{\alpha_p n}}$, where $\alpha_p$ is the area of the unit disk in the $\ell_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)\ge\sqrt{\frac{\log n}{(\alpha_p -\epsilon)n}}$ for some fixed $\epsilon > 0$.

Affiliated with

Also associated with

No associations

Rating

Sharp threshold for hamiltonicity of random geometric graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp threshold for hamiltonicity of random geometric graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp threshold for hamiltonicity of random geometric graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96430