Geodesic
Enumeration and asymptotic properties of unlabeled outerplanar graphs
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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, the chromatic number, and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics.
DOI : 10.37236/984
Classification : 05C30, 05C10, 05C80
Mots-clés : asymptotic number, random unlabeled outerplanar graphs 
Manuel Bodirsky; Éric Fusy; Mihyun Kang; Stefan Vigerske. Enumeration and asymptotic properties of unlabeled outerplanar graphs. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/984
@article{10_37236_984,
     author = {Manuel Bodirsky and \'Eric Fusy and Mihyun Kang and Stefan Vigerske},
     title = {Enumeration and asymptotic properties of unlabeled outerplanar graphs},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/984},
     zbl = {1158.05320},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/984/}
}
TY  - JOUR
AU  - Manuel Bodirsky
AU  - Éric Fusy
AU  - Mihyun Kang
AU  - Stefan Vigerske
TI  - Enumeration and asymptotic properties of unlabeled outerplanar graphs
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/984/
DO  - 10.37236/984
ID  - 10_37236_984
ER  - 
%0 Journal Article
%A Manuel Bodirsky
%A Éric Fusy
%A Mihyun Kang
%A Stefan Vigerske
%T Enumeration and asymptotic properties of unlabeled outerplanar graphs
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/984/
%R 10.37236/984
%F 10_37236_984

Cité par Sources :