Enumeration of Unlabeled Outerplanar Graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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}ρ^{-n}$, where $g\approx0.00909941$ and $ρ^{-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.
25 pages, 5 figures

Keywords

Combinatorics, 05A16; 05C30

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/104957

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0511422
 http://arxiv.org/abs/math/0511422

Collections

arXiv