Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Distances in random ...
Conference paper

Distances in random Apollonian network structures

Olivier Bodini ORCID (1), Alexis Darrasse (1), Michèle Soria (1)
(1) Algorithmes, Programmes et Résolution
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2007
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Proceedings
DOI
10.46298/dmtcs.3641
License
https://about.hal.science/hal-authorisation-v1
Indicators
654
Views
485
Downloads

Distances in random Apollonian network structures

Olivier Bodini ORCID (1), Alexis Darrasse (1), Michèle Soria (1)
(1) Algorithmes, Programmes et Résolution
Abstract
English
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}$.
French
Nous étudions dans ce papier la distribution des distances dans les structures des réseaux apolloniens aléatoires (RANS), une famille de graphes en bijection avec les arbres ternaires planaires. En s'appuyant sur l'utilisation de séries génératrices multivariées pour décrire toute l'information sur les distances, ainsi que sur l'analyse de singularités pour évaluer les coefficients de ces séries, nous prouvons une distribution limite de Rayleigh pour les distances vers un sommet externe du RANS et montrons que la distance moyenne entre deux sommets quelconques d'un RANS d'ordre $n$ est asymptotiquement $\sqrt{n}$.
Keywords
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • singularity analysis
  • random networks
  • distance
  • formal power series
Cited by

Source: OpenCitations

  • A characterization of some graphs with metric dimension two

    arXiv (Cornell University)

    Authors : Ali Behtoei, Akbar Davoodi ORCID, Mohsen Jannesari, Behnaz Omoomi

    Journal reference : Volume 09, 2017, pp. 1750027

    DOI : 10.1142/s1793830917500276
  • Characterizing several properties of high-dimensional random Apollonian networks

    Journal of Complex Networks

    Authors : Panpan Zhang ORCID

    Journal reference : Volume 8, 2020, pp.

    DOI : 10.1093/comnet/cnaa038
  • Some families of increasing planar maps

    Electronic Journal of Probability

    Authors : Marie Albenque ORCID, Jean-Francois Marckert

    Journal reference : Volume 13, 2008, pp.

    DOI : 10.1214/ejp.v13-563
  • Limiting Distribution for Distances in k-Trees

    Lecture notes in computer science

    Authors : Alexis Darrasse, Michèle Soria

    Journal reference : Volume , 2009, pp. 170-182

    DOI : 10.1007/978-3-642-10217-2_19
  • Heavy subtrees of Galton-Watson trees with an application to Apollonian networks

    Electronic Journal of Probability

    Authors : Luc Devroye ORCID, Cecilia Holmgren ORCID, Henning Sulzbach

    Journal reference : Volume 24, 2019, pp.

    DOI : 10.1214/19-ejp263
Preview
Loading PDF preview...