DMTCS Proceedings, Fifth Colloquium on Mathematics and Computer Science

Font Size:  Small  Medium  Large

Degree distribution in random planar graphs

Michael Drmota, Omer Giménez, Marc Noy

Abstract


We prove that for each k≥0, the probability that a root vertex in a random planar graph has degree k tends to a computable constant dk, and moreover that Σk dk =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)=Σk dk wk. From the explicit expression for p(w) we can compute the dk to any degree of accuracy, and derive asymptotic estimates for large values of k.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional