On longest paths and diameter in random apollonian networks1. Issue 4 (6th February 2015)

• Record Type: Journal Article
• Authors: Ebrahimzadeh, Ehsan; Farczadi, Linda; Gao, Pu; Mehrabian, Abbas; Sato, Cristiane M.; Wormald, Nick; Zung, Jonathan
• Is Part Of: Random structures & algorithms. Volume 45:Issue 4(2014)
• Page Start: 703
• Page End: 725
• Publication Date: 2015-02-06
• Subjects: random apollonian networks -- random plane graphs -- height of random trees -- longest paths -- diameters of power‐law graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20538
• Languages: English
• ISSNs: 1042-9832

Abstract

ABSTRACT: We consider the following iterative construction of a random planar triangulation. Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After n – 3 steps, we obtain a random triangulated plane graph with n vertices, which is called a Random Apollonian Network (RAN). We show that asymptotically almost surely (a.a.s.) a longest path in a RAN has length o ( n ), refuting a conjecture of Frieze and Tsourakakis. We also show that a RAN always has a cycle (and thus a path) of length ( 2 n − 5 ) log ⁡ 2 / log ⁡ 3, and that the expected length of its longest cycles (and paths) is Ω ( n 0.88 ) . Finally, we prove that a.a.s. the diameter of a RAN is asymptotic to c log ⁡ n, where c ≈ 1.668 is the solution of an explicit equation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 703–725, 2014