Distances in random Apollonian network structures

2007/12/13 by Olivier Bodini, Bodini, Olivier, Alexis Darrasse +3
Mathematics · Physics and Astronomy · #05A16 #05C12 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.0712.2129

openalex publication_date 2007/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the distribution of distances in random Apollonian network structures (RANS), a family of graphs which has a one-to-one correspondence with planar ternary trees. Using multivariate generating functions that express all information on distances, and singularity analysis for evaluating the coefficients of these functions, we describe the distribution of distances to an outermost vertex, and show that the average value of the distance between any pair of vertices in a RANS of order n is asymptotically square root of n.

Related

• On the Longest Paths and the Diameter in Random Apollonian Networks
• Parallel Random Apollonian Networks
• Typical distances in a geometric model for complex networks
• The Degree Sequence of Random Apollonian Networks
• Longest paths in random Apollonian networks and largest r-ary subtrees of random d-ary recursive trees