Long paths in random Apollonian networks

Colin Cooper, Alan Frieze

We consider the length $L(n)$ of the longest path in a randomly generated Apollonian Network (ApN) ${\mathcal{A}}_n$. We show that w.h.p. $L(n)\le n{e}^{-{\log }^{c}n}$ for any constant $c<2/…