Long paths in random Apollonian networks

2014/02/07 by Cooper, Colin, Frieze, Alan
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1403.1472

Abstract

We consider the length L(n) of the longest path in a randomly generated Apollonian Network (ApN) \cal A_n. We show that w.h.p. L(n)≤ ne^-logcn for any constant c<2/3.

Related

• Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees
• On the Longest Paths and the Diameter in Random Apollonian Networks
• The Degree Sequence of Random Apollonian Networks
• Distances in random Apollonian network structures
• Parallel Random Apollonian Networks