Name
Abstract | ||
|---|---|---|
We determine the exact and asymptotic number of unlabeled outer planar 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) p(-n), where g approximate to 0 : 00909941 and p(-1) approximate to 7: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, the chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics. |
Year | Venue | Keywords |
|---|---|---|
2007 | ELECTRONIC JOURNAL OF COMBINATORICS | unlabeled outerplanar graphs,dissections,combinatorial enumeration,cycle index,asymptotic estimates,singularity analysis |
Field | DocType | Volume |
Analytic combinatorics,Graph,Discrete mathematics,Combinatorics,Social connectedness,Cycle index,Vertex (geometry),Chromatic scale,Enumeration,Time complexity,Mathematics | Journal | 14.0 |
Issue | ISSN | Citations |
1.0 | 1077-8926 | 8 |
PageRank | References | Authors |
0.64 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Bodirsky | 1 | 644 | 54.63 |
| Éric Fusy | 2 | 198 | 21.95 |
| Mihyun Kang | 3 | 163 | 29.18 |
| Stefan Vigerske | 4 | 119 | 10.85 |