HAMILTON CYCLES IN RANDOM GEOMETRIC GRAPHS

• 成果类型: Article
• 署名作者: Balogh, Jozsef; Bollobas, Bela; Krivelevich, Michael; Muller, Tobias; Walters, Mark
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; Tel Aviv University; University of Cambridge; University of London
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10-AAP718
• 发表日期: 2011
• 页码: 1053-1072
• 关键词: connectivity

摘要

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 kappa-connected graph has a Hamilton cycle.