Enumeration of labelled 4-regular planar graphs

DOI10.1112/PLMS.12234MaRDI QIDQ5237371zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

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)