Hamilton cycles in random geometric graphs

József Balogh; Béla Bollobás; Michael Krivelevich; Tobias Müller; Mark Walters

doi:10.1214/10-AAP718

Hamilton cycles in random geometric graphs

József Balogh, Béla Bollobás, Michael Krivelevich, Tobias Müller, Mark Walters

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

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 κ-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.

Original language	English (US)
Pages (from-to)	1053-1072
Number of pages	20
Journal	Annals of Applied Probability
Volume	21
Issue number	3
DOIs	https://doi.org/10.1214/10-AAP718
State	Published - Jun 2011

Keywords

Hamilton cycles
Random geometric graphs

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Online availability

10.1214/10-AAP718

Library availability

Discover UIUC Full Text

Cite this

@article{32731b8787f545bb937fdee64a51e057,

title = "Hamilton cycles in random geometric graphs",

abstract = "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 κ-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.",

keywords = "Hamilton cycles, Random geometric graphs",

author = "J{\'o}zsef Balogh and B{\'e}la Bollob{\'a}s and Michael Krivelevich and Tobias M{\"u}ller and Mark Walters",

year = "2011",

month = jun,

doi = "10.1214/10-AAP718",

language = "English (US)",

volume = "21",

pages = "1053--1072",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "3",

}

TY - JOUR

T1 - Hamilton cycles in random geometric graphs

AU - Balogh, József

AU - Bollobás, Béla

AU - Krivelevich, Michael

AU - Müller, Tobias

AU - Walters, Mark

PY - 2011/6

Y1 - 2011/6

N2 - 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 κ-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.

AB - 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 κ-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.

KW - Hamilton cycles

KW - Random geometric graphs

UR - http://www.scopus.com/inward/record.url?scp=79958241864&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79958241864&partnerID=8YFLogxK

U2 - 10.1214/10-AAP718

DO - 10.1214/10-AAP718

M3 - Article

AN - SCOPUS:79958241864

SN - 1050-5164

VL - 21

SP - 1053

EP - 1072

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 3

ER -

Hamilton cycles in random geometric graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this