22078 articles – 15904 references  [version française]

hal-00713480, version 1

## Asymptotic enumeration and limit laws for graphs of fixed genus

Guillaume Chapuy 1, Eric Fusy () 2, Omer Giménez 3, Bojan Mohar 1, Marc Noy 3

Journal of Combinatorial Theory. Series A 118, 3 (2011) 748--777

Abstract: It is shown that the number of labelled graphs with $n$ vertices that can be embedded in the orientable surface $\mathbb{S}_g$ of genus $g$ grows asymptotically like $c^{(g)}n^{5(g-1)/2-1}\gamma^n n!$, where $c^{(g)} >0$, and $\gamma \approx 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 $\mathbb{S}_g$ has a unique 2-connected component of linear size with high probability.

• 1:  Department of Mathematics
• Simon Fraser University
• 2:  Laboratoire d'informatique de l'école polytechnique (LIX)
• CNRS : UMR7161 – Polytechnique - X
• 3:  Universitat Politècnica de Catalunya (UPC)
• Universitat Politécnica de Catalunya
• Domain : Mathematics/Combinatorics
• Internal note : http://arxiv.org/abs/1001.3628

• hal-00713480, version 1
• oai:hal.archives-ouvertes.fr:hal-00713480
• From:
• Submitted on: Sunday, 1 July 2012 17:17:56
• Updated on: Sunday, 1 July 2012 17:17:56