Asymptotic enumeration and limit laws for graphs of fixed genus

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

doi:10.1016/j.jcta.2010.11.014

Asymptotic enumeration and limit laws for graphs of fixed genus

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

Simon Fraser University
Laboratoire d'Informatique (LIX)
Universidad Politecnica de Catalunia

Research output: Contribution to journal › Article › peer-review

36 Citations (Scopus)

Abstract

It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface Sg of genus g grows asymptotically like. c(g)n5(g-1)/2-1αnn! where c(g)>0, and α≈27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Giménez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in Sg has a unique 2-connected component of linear size with high probability.

Original language	English
Pages (from-to)	748-777
Number of pages	30
Journal	Journal of Combinatorial Theory. Series A
Volume	118
Issue number	3
DOIs	https://doi.org/10.1016/j.jcta.2010.11.014
Publication status	Published - 1 Apr 2011
Externally published	Yes

Keywords

Enumeration
Generating functions
Graph embeddings
Limit

Access to Document

10.1016/j.jcta.2010.11.014

Cite this

@article{5ec3f3c8cb7c412493feaff40f89afc0,

title = "Asymptotic enumeration and limit laws for graphs of fixed genus",

abstract = "It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface Sg of genus g grows asymptotically like. c(g)n5(g-1)/2-1αnn! where c(g)>0, and α≈27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gim{\'e}nez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in Sg has a unique 2-connected component of linear size with high probability.",

keywords = "Enumeration, Generating functions, Graph embeddings, Limit",

author = "Guillaume Chapuy and {\'E}ric Fusy and Omer Gim{\'e}nez and Bojan Mohar and Marc Noy",

year = "2011",

month = apr,

day = "1",

doi = "10.1016/j.jcta.2010.11.014",

language = "English",

volume = "118",

pages = "748--777",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - Asymptotic enumeration and limit laws for graphs of fixed genus

AU - Chapuy, Guillaume

AU - Fusy, Éric

AU - Giménez, Omer

AU - Mohar, Bojan

AU - Noy, Marc

PY - 2011/4/1

Y1 - 2011/4/1

N2 - It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface Sg of genus g grows asymptotically like. c(g)n5(g-1)/2-1αnn! where c(g)>0, and α≈27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Giménez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in Sg has a unique 2-connected component of linear size with high probability.

AB - It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface Sg of genus g grows asymptotically like. c(g)n5(g-1)/2-1αnn! where c(g)>0, and α≈27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Giménez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in Sg has a unique 2-connected component of linear size with high probability.

KW - Enumeration

KW - Generating functions

KW - Graph embeddings

KW - Limit

UR - https://www.scopus.com/pages/publications/78751560076

U2 - 10.1016/j.jcta.2010.11.014

DO - 10.1016/j.jcta.2010.11.014

M3 - Article

AN - SCOPUS:78751560076

SN - 0097-3165

VL - 118

SP - 748

EP - 777

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 3

ER -

Asymptotic enumeration and limit laws for graphs of fixed genus

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this