Spanning trees of bounded degree in random geometric graphs

Abstract

We determine the sharp threshold for the containment of all $n$-vertex trees of bounded degree in random geometric graphs with $n$ vertices. This provides a geometric counterpart of Montgomery's threshold result for binomial random graphs, and confirms a conjecture of Espuny Díaz, Lichev, Mitsche, and Wesolek. Our proof is algorithmic and adapts to other families of graphs, in particular graphs with bounded genus or tree-width.

10 pages