Manuel Bodirsky ; Omer Gimenez ; Mihyun Kang ; Marc Noy - On the number of series parallel and outerplanar graphs

dmtcs:3451 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3451
On the number of series parallel and outerplanar graphsArticle

Authors: Manuel Bodirsky 1; Omer Gimenez 2; Mihyun Kang 1; Marc Noy 2

  • 1 Department of Computer Science [Berlin]
  • 2 Departament de Matemàtica Aplicada II

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} \gamma^n n!$, where $\gamma$ 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: analytic combinatorics,normal law,Series parallel graph,outerplanar graph,random graph,asymptotic enumeration,limit law,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

9 Documents citing this article

Consultation statistics

This page has been seen 185 times.
This article's PDF has been downloaded 184 times.