Skip to Main content Skip to Navigation
Conference papers

Distances in random Apollonian network structures

Olivier Bodini 1 Alexis Darrasse 1 Michèle Soria 1
1 APR - Algorithmes, Programmes et Résolution
LIP6 - Laboratoire d'Informatique de Paris 6
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 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}$.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/hal-00345749
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 19, 2015 - 11:44:10 AM
Last modification on : Friday, January 8, 2021 - 5:32:06 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:45:23 AM

File

dmAJ0127.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00345749, version 1

Citation

Olivier Bodini, Alexis Darrasse, Michèle Soria. Distances in random Apollonian network structures. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), Jun 2008, Viña del Mar, Chile. pp.307-318. ⟨hal-00345749⟩

Share

Metrics

Record views

294

Files downloads

586