Asymptotic enumeration and limit laws for graphs of fixed genus

DOI10.1016/j.jcta.2010.11.014zbMath1231.05179arXiv1001.3628OpenAlexW1999694424MaRDI QIDQ2431243

Marc Noy, Omer Giménez, Bojan Mohar, Guillaume Chapuy, Éric Fusy

Publication date: 11 April 2011

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

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

zbMATH Keywords

generating functionsenumerationlimit lawsgraph embeddings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (24)

A character approach to directed genus distribution of graphs: the bipartite single-black-vertex case ⋮ Classes of graphs embeddable in order-dependent surfaces ⋮ Connectivity for Bridge-Addable Monotone Graph Classes ⋮ Triangles in random cubic planar graphs ⋮ Enumeration of cubic multigraphs on orientable surfaces ⋮ Part Sizes of Smooth Supercritical Compositional Structures ⋮ Concentration of maximum degree in random planar graphs ⋮ Random graphs from a weighted minor-closed class ⋮ On the sum of digits of some sequences of integers ⋮ Longest and shortest cycles in random planar graphs ⋮ The evolution of random graphs on surfaces ⋮ Evolution of the giant component in graphs on orientable surfaces ⋮ Unnamed Item ⋮ Cubic graphs and related triangulations on orientable surfaces ⋮ The Evolution of Random Graphs on Surfaces ⋮ Enumeration of labelled 4-regular planar graphs. II: Asymptotics ⋮ Phase transitions in graphs on orientable surfaces ⋮ Enumeration of unlabeled uniform hypergraphs ⋮ Logical limit laws for minor-closed classes of graphs ⋮ A bijection for essentially 3-connected toroidal maps ⋮ Encoding and avoiding 2-connected patterns in polygon dissections and outerplanar graphs ⋮ Two critical periods in the evolution of random planar graphs ⋮ Graph classes with given 3-connected components: Asymptotic enumeration and random graphs ⋮ On the probability of planarity of a random graph near the critical point

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic enumeration of rooted convex polyhedra
• A formula for the bivariate map asymptotics constants in terms of the univariate map asymptotics constants
• List colourings of planar graphs
• Random graphs on surfaces
• Locally planar graphs are 5-choosable
• A complete grammar for decomposing a family of graphs into 3-connected components
• The asymptotic number of rooted maps on a surface
• Relations fonctionnelles et dénombrement des cartes pointées sur le tore. (Functional relations and the enumeration of rooted genus one maps)
• Counting labelled three-connected and homeomorphically irreducible two- connected graphs
• Five-coloring maps on surfaces
• Root vertex valency distributions of rooted maps and rooted triangulations
• Counting rooted maps on an orientable surface of any genus by a function of the numbers of vertices and faces
• Counting rooted maps on a surface
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The number of labeled 2-connected planar graphs
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Graph classes with given 3-connected components: Asymptotic enumeration and random graphs
• Vertices of given degree in series-parallel graphs
• Asymptotic enumeration and limit laws of planar graphs
• Combinatorial Local Planarity and the Width of Graph Embeddings
• Almost all rooted maps have large representativity
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps

This page was built for publication: Asymptotic enumeration and limit laws for graphs of fixed genus