Degree distribution in random planar graphs

Abstract : We prove that for each $k \geq 0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, and moreover that $\sum_k d_k =1$. The proof uses the tools developed by Gimènez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=\sum_k d_k w^k$. From the explicit expression for $p(w)$ we can compute the $d_k$ to any degree of accuracy, and derive asymptotic estimates for large values of $k$.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.163-178, 2008, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01194677
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:51:00
Dernière modification le : mercredi 10 mai 2017 - 17:41:06
Document(s) archivé(s) le : mardi 8 décembre 2015 - 12:58:10

Fichier

dmAI0109.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194677, version 1

Collections

Citation

Michael Drmota, Omer Gimenez, Marc Noy. Degree distribution in random planar graphs. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.163-178, 2008, DMTCS Proceedings. 〈hal-01194677〉

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

220