Degree distribution in random planar graphs

DOI10.1016/J.JCTA.2011.04.010zbMATH Open1230.05103arXiv0911.4331OpenAlexW1981036944MaRDI QIDQ549258FDOQ549258

Marc Noy, Michael Drmota, Omer Giménez

Publication date: 7 July 2011

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

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.

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

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

zbMATH Keywords

planar graphsdegree distributionanalytic combinatorics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

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

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)