Enumeration and limit laws of series-parallel graphs

Research output: Preprint/Documentation/Report › Preprint

Contributors

  • Manuel Bodirsky - , Humboldt University of Berlin (Author)
  • Omer Gimenez - (Author)
  • Mihyun Kang - (Author)
  • Marc Noy - (Author)

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 and for graphs not containing $K_{2,3}$ as a minor.

Details

Original languageUndefined
Publication statusPublished - 19 Dec 2005
Externally publishedYes
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper

External IDs

ORCID /0000-0001-8228-3611/work/142659292

Keywords

Keywords

  • math.CO, 05A16; 05C30