Hamilton cycles in random geometric graphs
Copyright policy )Hamilton cycles in random geometric graphs
We prove that, in the Gilbert model for a random geometric graph, almost every graph becomes Hamiltonian exactly when it first becomes 2-connected. This answers a question of Penrose. We also show that in the k-nearest neighbor model, there is a constant �� such that almost every ��-connected graph has a Hamilton cycle.
Published in at http://dx.doi.org/10.1214/10-AAP718 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
- University of Cambridge United Kingdom
- Tel Aviv University Israel
- University College London United Kingdom
- University of Memphis United States
- University of Illinois System United States
05C80, Probability (math.PR), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 60D05, Hamilton cycles, 05C45, Mathematics - Probability, random geometric graphs
05C80, Probability (math.PR), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), 60D05, Hamilton cycles, 05C45, Mathematics - Probability, random geometric graphs
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).23 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!