Further results on random cubic planar graphs

DOI10.1002/RSA.20893MaRDI QIDQ5113961zbMATH OpenOpenAlexWikidataFDO

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

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

generating functionsplanar graphsanalytic combinatorics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

Abstract: We provide precise asymptotic estimates for the number of several classes of labelled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky et al. (Random Structures Algorithms 2007). We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.

Recommendations

• Random cubic planar graphs revisited
• Random cubic planar graphs
• Triangles in random cubic planar graphs
• Random cubic planar maps
• Random planar graphs

Cited in

(22)

• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Tropically planar graphs
• Random cubic planar graphs revisited
• The distribution of the number of small cuts in a random planar triangulation
• Counting embeddings of rooted trees into families of rooted trees
• The expected number of perfect matchings in cubic planar graphs
• First-passage percolation on random simple triangulations
• The scaling limit of random cubic planar graphs
• Enumeration of labelled 4-regular planar graphs. II: Asymptotics
• scientific article; zbMATH DE number 4112650 (Why is no real title available?)
• Enumeration of rooted 3-connected bipartite planar maps
• On the expected number of perfect matchings in cubic planar graphs
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
• Triangles in random cubic planar graphs
• Concentration of maximum degree in random planar graphs
• scientific article; zbMATH DE number 125468 (Why is no real title available?)
• Random cubic planar graphs
• The uniform infinite cubic planar graph
• Local convergence of random planar graphs
• Random cubic planar graphs converge to the Brownian sphere
• Random cubic planar maps

This page was built for publication: Further results on random cubic planar graphs

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