Skip to Main content Skip to Navigation
Conference papers

On the number of series parallel and outerplanar graphs

Abstract : 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.
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184440
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 2:59:00 PM
Last modification on : Monday, June 15, 2020 - 12:00:33 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:12:39 AM

File

dmAE0174.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184440, version 1

Collections

Citation

Manuel Bodirsky, Omer Gimenez, Mihyun Kang, Marc Noy. On the number of series parallel and outerplanar graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.383-388. ⟨hal-01184440⟩

Share

Metrics

Record views

382

Files downloads

576