Asymptotic enumeration of labelled graphs by genus

MaRDI QIDQ625375zbMATH OpenFDO

Authors Edward A. Bender, Zhicheng Gao

Publication date 17 February 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/227897, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p13.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

asymptotic formulaface widthlabelled graphsorientable genusorientable surfacesurface map

Mathematics Subject Classification ID

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

Review text

Summary: We obtain asymptotic formulas for the number of rooted 2-connected and 3- connected surface maps on an orientable surface of genus \(g\) with respect to vertices and edges simultaneously. We also derive the bivariate version of the large facewidth result for random 3-connected maps. These results are then used to derive asymptotic formulas for the number of labelled \(k\)-connected graphs of orientable genus \(g\) for \(k \leq 3\).

Recommendations

• Asymptotic enumeration and limit laws for graphs of fixed genus
• scientific article; zbMATH DE number 892539
• The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces
• The asymptotic number of rooted 2-connected triangular maps on a surface
• The asymptotic number of labeled connected graphs with a given number of vertices and edges

Cited in

(13)

• Cubic graphs and related triangulations on orientable surfaces
• Logical limit laws for minor-closed classes of graphs
• The number of labeled 2-connected planar graphs
• On the sum of digits of some sequences of integers
• Genus polynomials of ladder-like sequences of graphs
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Graph classes with given 3-connected components: asymptotic enumeration and random graphs
• Enumeration of cubic multigraphs on orientable surfaces
• Random graphs from a weighted minor-closed class
• scientific article; zbMATH DE number 892539 (Why is no real title available?)
• Classes of graphs embeddable in order-dependent surfaces
• An asymptotics for the number of labelled planar tetracyclic and pentacyclic graphs
• The genus distribution of cubic graphs and asymptotic number of rooted cubic maps with high genus

This page was built for publication: Asymptotic enumeration of labelled graphs by genus

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