Enumeration and limit laws of series-parallel graphs

Simple item page
dc.creatorBodirsky, Manuel
dc.creatorGimenez, Omer
dc.creatorKang, Mihyun
dc.creatorNoy, Marc
dc.date2005-12-19
dc.date.accessioned2026-07-07T06:55:30Z
dc.date.available2026-07-07T06:55:30Z
dc.descriptionWe 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.
dc.description14 pages
dc.identifierhttps://arxiv.org/abs/math/0512435
dc.identifierhttp://arxiv.org/abs/math/0512435
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/106300
dc.subjectCombinatorics
dc.subject05A16; 05C30
dc.titleEnumeration and limit laws of series-parallel graphs
dc.typetext

Files

Collections

arXiv