DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

On the number of series parallel and outerplanar graphs

Manuel Bodirsky, Omer Giménez, Mihyun Kang, Marc Noy

Abstract


We show that the number gn of labelled series-parallel graphs on n vertices is asymptotically gn ∼g·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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional