Enumeration of labelled 4-regular planar graphs II: asymptotics

DOI10.1016/J.EJC.2022.103661MaRDI QIDQ6332989arXivFDO

Authors Marc Noy, Clément Requilé, Juanjo Rué

Publication date 16 January 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.EJC.2022.103661

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

arXiv classification

math.CO

Abstract: This work is a follow-up of the article [Proc. London Math. Soc. 119(2):358--378, 2019], where the authors solved the problem of counting labelled 4-regular planar graphs. In this paper, we obtain a precise asymptotic estimate for the number $g_n$ of labelled 4-regular planar graphs on $n$ vertices. Our estimate is of the form $g_{n}simgcdot{n}^{-7/2}h{o}^{-n}n!$, where $g>0$ is a constant and $hoapprox0.24377$ is the radius of convergence of the generating function $su{m}_{nge0}{g}_n{x}^n/n!$, and conforms to the universal pattern obtained previously in the enumeration of several classes of planar graphs. In addition to analytic methods, our solution needs intensive use of computer algebra in order to deal with large systems of multivariate polynomial equations. We also obtain asymptotic estimates for the number of 2- and 3-connected 4-regular planar graphs, and for the number of 4-regular simple maps, both connected and 2-connected.

This page was built for publication: Enumeration of labelled 4-regular planar graphs II: asymptotics

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