Geodesic
Enumeration of labeled outerplanar bicyclic and tricyclic graphs
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 18-31

Voir la notice de l'article provenant de la source Math-Net.Ru

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with $n$ vertices and also obtain asymptotics for the number of these graphs for large $n$. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic $n$-vertex blocks and deduce the corresponding asymptotics for large $n$. Tab. 1, illustr. 4, bibliogr. 15.
Keywords: enumeration, labeled graph, outerplanar graph, bicyclic graph, tricyclic graph, asymptotics. 
@article{DA_2017_24_2_a1,
     author = {V. A. Voblyi and A. K. Meleshko},
     title = {Enumeration of labeled outerplanar bicyclic and tricyclic graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {18--31},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_2_a1/}
}
TY  - JOUR
AU  - V. A. Voblyi
AU  - A. K. Meleshko
TI  - Enumeration of labeled outerplanar bicyclic and tricyclic graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 18
EP  - 31
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_2_a1/
LA  - ru
ID  - DA_2017_24_2_a1
ER  - 
%0 Journal Article
%A V. A. Voblyi
%A A. K. Meleshko
%T Enumeration of labeled outerplanar bicyclic and tricyclic graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 18-31
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_2_a1/
%G ru
%F DA_2017_24_2_a1
V. A. Voblyi; A. K. Meleshko. Enumeration of labeled outerplanar bicyclic and tricyclic graphs. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 18-31. http://geodesic.mathdoc.fr/item/DA_2017_24_2_a1/