VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Asymptotic enumeration and limit laws for graphs of fixed genus
    Chapuy, Guillaume ...
    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 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 ▫${\mathbb S}_g$▫ has a unique 2-connected component of linear size with high probability.
    Vir: Journal of combinatorial theory. Series A. - ISSN 0097-3165 (Vol. 118, iss. 3, 2011, str. 748-777)
    Vrsta gradiva - članek, sestavni del
    Leto - 2011
    Jezik - angleški
    COBISS.SI-ID - 15875673

    Povezava(-e):

    http://dx.doi.org/10.1016/j.jcta.2010.11.014

Vnos na polico