Disjoint Hamilton cycles in the random geometric graph

DOI10.1002/JGT.20560MaRDI QIDQ3106267zbMATH OpenOpenAlexWikidataFDO

Authors Tobias Müller, Xavier Pérez-Giménez, Nicholas Wormald

Publication date 20 December 2011

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.4459

zbMATH Keywords

Hamilton cyclerandom geometric graph processthreshold function

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove a conjecture of Penrose about the standard random geometric graph process, in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of lengths taken in the l_p norm. We show that the first edge that makes the random geometric graph Hamiltonian is a.a.s. exactly the same one that gives 2-connectivity. We also extend this result to arbitrary connectivity, by proving that the first edge in the process that creates a k-connected graph coincides a.a.s. with the first edge that causes the graph to contain k/2 pairwise edge-disjoint Hamilton cycles (for even k), or (k-1)/2 Hamilton cycles plus one perfect matching, all of them pairwise edge-disjoint (for odd k).

Recommendations

• Hamilton cycles in random geometric graphs
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Edge-disjoint Hamilton cycles in random graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Edge disjoint Hamilton cycles in sparse random graphs of minimum degree at leastk

Cites work

• scientific article; zbMATH DE number 1340281 (Why is no real title available?)
• Random Geometric Graphs
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs

Cited in

(13)

• Almost Eulerian compatible spanning circuits in edge-colored graphs
• The acquaintance time of (percolated) random geometric graphs
• Recent advances on the Hamiltonian problem: survey III
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• On the treewidth of random geometric graphs and percolated grids
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• Hamilton cycles in random geometric graphs
• Hamiltonicity of graphs perturbed by a random geometric graph
• Bridged Hamiltonian cycles in sub-critical random geometric graphs
• Sharp threshold for embedding balanced spanning trees in random geometric graphs
• Hamiltonicity of randomly perturbed graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Hamilton cycles and perfect matchings in the KPKVB model

This page was built for publication: Disjoint Hamilton cycles in the random geometric graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3106267)