Name
Abstract | ||
|---|---|---|
It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S"g of genus g grows asymptotically likec^(^g^)n^5^(^g^-^1^)^/^2^-^1@c^nn! where c^(^g^)0, and @c~27.23 is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gimenez 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 S"g has a unique 2-connected component of linear size with high probability. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jcta.2010.11.014 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
generating functions,planar case g,planar case,labelled graph,high probability,enumeration,limit laws,fixed genus,exponential growth rate,analogous result,genus g,planar graph,asymptotic enumeration,asymptotically likec,limit law,graph embeddings,2-connected component,connected component,generating function,random graph,exponential growth,graph embedding | Random regular graph,Discrete mathematics,Outerplanar graph,Combinatorics,Forbidden graph characterization,Book embedding,Pathwidth,Universal graph,1-planar graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
118 | 3 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
13 | 1.05 | 23 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillaume Chapuy | 1 | 73 | 11.25 |
| íric Fusy | 2 | 51 | 4.32 |
| Omer Giménez | 3 | 231 | 18.10 |
| Bojan Mohar | 4 | 1523 | 192.05 |
| M. Noy | 5 | 369 | 33.94 |