Longest paths in random Apollonian networks and largest $r$-ary subtrees of random $d$-ary recursive trees

Andrea Collevecchio, Abbas Mehrabian, Nick Wormald

Let $r$ and $d$ be positive integers with $r<d$. Consider a random $d$-ary tree constructed as follows. Start with a single vertex, and in each time-step choose a uniformly random…