Enumeration of Unlabeled Outerplanar Graphs

Publikation: Vorabdruck/Dokumentation/BerichtVorabdruck (Preprint)

Beitragende

  • Manuel Bodirsky - , Humboldt-Universität zu Berlin (Autor:in)
  • Eric Fusy - (Autor:in)
  • Mihyun Kang - (Autor:in)
  • Stefan Vigerske - (Autor:in)

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

OriginalspracheUndefiniert
PublikationsstatusVeröffentlicht - 16 Nov. 2005
Extern publiziertJa
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper

Externe IDs

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

Schlagworte

Schlagwörter

  • math.CO, 05A16; 05C30