Enumeration of Unlabeled Outerplanar Graphs
| dc.creator | Bodirsky, Manuel | |
| dc.creator | Fusy, Eric | |
| dc.creator | Kang, Mihyun | |
| dc.creator | Vigerske, Stefan | |
| dc.date | 2005-11-16 | |
| dc.date | 2006-01-25 | |
| dc.date.accessioned | 2026-07-07T06:51:21Z | |
| dc.date.available | 2026-07-07T06:51:21Z | |
| dc.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. | |
| dc.description | 25 pages, 5 figures | |
| dc.identifier | https://arxiv.org/abs/math/0511422 | |
| dc.identifier | http://arxiv.org/abs/math/0511422 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104957 | |
| dc.subject | Combinatorics | |
| dc.subject | 05A16; 05C30 | |
| dc.title | Enumeration of Unlabeled Outerplanar Graphs | |
| dc.type | text |