Enumeration of Unlabeled Outerplanar Graphs

Research output: Preprint/documentation/report › Preprint

Contributors

  • Manuel Bodirsky - , Humboldt University of Berlin (Author)
  • Eric Fusy - (Author)
  • Mihyun Kang - (Author)
  • Stefan Vigerske - (Author)

Abstract

We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number g_n of unlabeled outerplanar graphs on n vertices can be computed in polynomial time, and g_n is asymptotically $g n^{-5/2}\rho^{-n}$, where $g\approx0.00909941$ and $\rho^{-1}\approx7.50360$ can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on n vertices, for instance concerning connectedness, chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics.

Details

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

External IDs

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

Keywords

Keywords

  • math.CO, 05A16; 05C30