Hamilton cycles in random geometric graphs
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 \kappa\ such that almost every \kappa-connected graph has a Hamilton cycle.
Mark Walters、J¨?zsef Balogh、B¨|la Bollob¨¢s、Michael Krivelevich、Tobias M¨1ller
数学
Mark Walters,J¨?zsef Balogh,B¨|la Bollob¨¢s,Michael Krivelevich,Tobias M¨1ller.Hamilton cycles in random geometric graphs[EB/OL].(2009-05-28)[2025-08-02].https://arxiv.org/abs/0905.4650.点此复制
评论