Enumeration of labelled 4-regular planar graphs

DOI10.1112/PLMS.12234zbMATH Open1422.05053arXiv1709.04678OpenAlexW3104343140WikidataQ128417576 ScholiaQ128417576MaRDI QIDQ5237371FDOQ5237371

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

Publication date: 17 October 2019

Published in: Proceedings of the London Mathematical Society (Search for Journal in Brave)

Abstract: We present the first combinatorial scheme for counting labelled 4-regular planar graphs through a complete recursive decomposition. More precisely, we show that the exponential generating function of labelled 4-regular planar graphs can be computed effectively as the solution of a system of equations, from which the coefficients can be extracted. As a byproduct, we also enumerate labelled 3-connected 4-regular planar graphs, and simple 4-regular rooted maps.

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

Recommendations

• Enumeration of labeled 4-regular planar graphs
• Enumeration of labelled 4-regular planar graphs. II: Asymptotics
• Enumeration of 2-connected loopless 4-regular maps on the plane
• The enumeration of rooted 4-regular unicursal planar maps
• Enumerating near-4-regular maps on the sphere and the torus

zbMATH Keywords

exponential generating function

Mathematics Subject Classification ID

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

Cited In (8)

• Enumeration of rooted 3-connected bipartite planar maps
• Enumeration of labeled 4-regular planar graphs
• Enumeration of labelled 4-regular planar graphs. II: Asymptotics
• Random cubic planar maps
• On the expected number of perfect matchings in cubic planar graphs
• ASYMPTOTIC NUMBERS OF GENERAL 4-REGULAR GRAPHS WITH GIVEN CONNECTIVITIES
• Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems
• Structure and enumeration of \(K_4\)-minor-free links and link-diagrams

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

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