Hamiltonicity conjecture for randomly perturbed graphs with geometric randomness
Hamiltonicity conjecture for randomly perturbed graphs with geometric randomness
Let be an integer, let , and let be an -vertex graph with minimum degree at least . Write for the random geometric graph generated by independent uniform points in , with edges between points at distance at most . Hamiltonicity conjecture. For some constant , asymptotically almost surely,
is Hamiltonian. This would extend the known threshold for binomial random perturbations to random geometric graphs and would be best possible up to the value of ; the conjecture concerns the regime in which tends to .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Alberto Espuny Díaz, “Hamiltonicity of graphs perturbed by a random geometric graph”, arXiv:2102.02321 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.