Premium
On longest paths and diameter in random apollonian networks
Author(s) -
Ebrahimzadeh Ehsan,
Farczadi Linda,
Gao Pu,
Mehrabian Abbas,
Sato Cristiane M.,
Wormald Nick,
Zung Jonathan
Publication year - 2014
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20538
Subject(s) - combinatorics , vertex (graph theory) , mathematics , planar graph , random graph , bounded function , conjecture , path (computing) , random walk , plane (geometry) , triangulation , graph , discrete mathematics , geometry , computer science , mathematical analysis , statistics , programming language
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