Degree distribution in random planar graphs

DOI10.1016/J.JCTA.2011.04.010MaRDI QIDQ549258zbMATHOpenAlexFDO

Authors Michael Drmota, Omer Giménez, Marc Noy

Publication date 7 July 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.4331

zbMATH Keywords

planar graphsdegree distributionanalytic combinatorics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Abstract: We prove that for each $kge0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, so that the expected number of vertices of degree $k$ is asymptotically $d_{k}n$, and moreover that $su{m}_k{d}_k=1$. The proof uses the tools developed by Gimenez 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 the generating functions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=su{m}_k{d}_k{w}^k$. From this we can compute the $d_k$ to any degree of accuracy, and derive the asymptotic estimate $d_{k}simccdot{k}^{-1/2}{q}^k$ for large values of $k$, where $qapprox0.67$ is a constant defined analytically.

Recommendations

• Degree distribution in random planar graphs
• On the degree distribution of random planar graphs
• Asymptotic enumeration and limit laws of planar graphs
• The maximum degree of random planar graphs
• The maximum degree of random planar graphs

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 1146225 (Why is no real title available?)
• A Generalisation of Stirling's Formula.
• A pattern of asymptotic vertex valency distributions in planar maps
• Analytic combinatorics
• Asymptotic Methods in Enumeration
• Asymptotic enumeration and limit laws of planar graphs
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Counting planar graphs and related families of graphs
• Enumeration and limit laws for series-parallel graphs
• Face sizes of 3-polytopes
• Graph classes with given 3-connected components: asymptotic counting and critical phenomena
• On random planar graphs, the number of planar graphs and their triangulations
• On the Enumeration of Rooted Non-Separable Planar Maps
• On the Number of Edges in Random Planar Graphs
• Planar graphs, via well-orderly maps and trees
• Random graphs on surfaces
• Random planar graphs
• Random planar graphs and the number of planar graphs
• Singularity Analysis of Generating Functions
• The asymptotic enumeration of rooted convex polyhedra
• The degree sequence of random graphs from subcritical classes
• The enumeration of c-nets via quadrangulations
• The maximum degree of random planar graphs
• The number of labeled 2-connected planar graphs
• Uniform random sampling of planar graphs in linear time
• Vertices of given degree in series-parallel graphs

Cited in

(19)

• Maximum degree in minor-closed classes of graphs
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• The maximum degree of random planar graphs
• Random planar maps and graphs with minimum degree two and three
• The Evolution of Random Graphs on Surfaces
• Phase transitions in graphs on orientable surfaces
• Random graphs from a weighted minor-closed class
• Degree distribution in random planar graphs
• A central limit theorem for the number of degree-\(k\) vertices in random maps
• Local convergence of random planar graphs
• The evolution of random graphs on surfaces
• On the degree distribution of random planar graphs
• Extremal statistics on non-crossing configurations
• The maximum degree of random planar graphs
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Concentration of maximum degree in random planar graphs
• The maximum degree of series-parallel graphs
• Local convergence of random planar graphs
• Limits of random tree-like discrete structures

This page was built for publication: Degree distribution in random planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549258)