Enumeration of Unlabeled Outerplanar Graphs
Publikation: Vorabdruck/Dokumentation/Bericht › Vorabdruck (Preprint)
Beitragende
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
Originalsprache | Undefiniert |
---|---|
Publikationsstatus | Veröffentlicht - 16 Nov. 2005 |
Extern publiziert | Ja |
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