Enumeration and limit laws of series-parallel graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g\cdot n^{-5/2} γ^n n!$, where $γ$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing $K_{2,3}$ as a minor.
14 pages

Keywords

Combinatorics, 05A16; 05C30

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/106300

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0512435
 http://arxiv.org/abs/math/0512435

Collections

arXiv