Olivier Bodini ; Alexis Darrasse ; Michèle Soria - Distances in random Apollonian network structures

dmtcs:3641 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3641
Distances in random Apollonian network structuresArticle

Authors: Olivier Bodini ORCID1; Alexis Darrasse 1; Michèle Soria 1

  • 1 Algorithmes, Programmes et Résolution

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 prove a Rayleigh limit distribution for 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 $\sqrt{n}$.


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: formal power series,random networks,distance,singularity analysis,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

5 Documents citing this article

Consultation statistics

This page has been seen 202 times.
This article's PDF has been downloaded 171 times.