Sharp threshold for hamiltonicity of random geometric graphs

Simple item page
dc.creatorDiaz, J.
dc.creatorMitsche, D.
dc.creatorPerez, X.
dc.date2006-07-07
dc.date.accessioned2026-07-07T07:16:16Z
dc.date.available2026-07-07T07:16:16Z
dc.descriptionWe 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}{α_p n}}$, where $α_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}{(α_p -ε)n}}$ for some fixed $ε> 0$.
dc.description10 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/cs/0607023
dc.identifierhttp://arxiv.org/abs/cs/0607023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/113531
dc.subjectDiscrete Mathematics
dc.titleSharp threshold for hamiltonicity of random geometric graphs
dc.typetext

Files

Collections

arXiv