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/

[1] V. A. Voblyi, Asymptotic enumeration of graphs of some types, Cand. Sci. Dissertation, VTs AN SSSR, Moscow, 1985 (Russian)

[2] V. A. Voblyi, “A formula for the number of labeled connected graphs”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 48–59 (Russian) | MR | Zbl

[3] V. A. Voblyi, A. K. Meleshko, “Enumeration of labeled rose graphs”, Proc. XVI Int. Sci. Tech. Seminar “Combinatorial Configurations and Its Applications” (Kirovograd, Ukraine, Apr. 11–12, 2014), Kirovograd Natl. Tech. Univ., Kirovograd, 2014, 27–29 (Russian)

[4] E. F. Dmitriev, Enumeration of labeled two-colored connected graphs with small cyclomatic number, Depos. Manuscr., Deposited in VINITI, No 4559-85 (Russian)

[5] A. P. Prudnikov, Yu. A. Brychkov, O. I. Marichev, Integrals and Series: Elementary Functions, Nauka, Moscow, 1981 (Russian) | MR

[6] V. E. Stepanov, “On some features of the structure of a random graph near a critical point”, Theory Probab. Appl., 32:4 (1987), 573–594 | DOI | MR | Zbl | Zbl

[7] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969 | MR | MR | Zbl

[8] F. Harary, E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973 | MR | MR | Zbl

[9] Bodirsky M., Kang M., “Generating outerplanar graphs uniformly at random”, Comb. Probab. Computing, 15:3 (2006), 333–343 | DOI | MR | Zbl

[10] Bodirsky M., Gimenez O., Kang M., Noy M., “Enumeration and limit laws of series-parallel graphs”, Eur. J. Comb., 28:8 (2007), 2091–2105 | DOI | MR | Zbl

[11] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in the theory of graphs. IV”, Proc. Nat. Acad. Sci. USA, 43:1 (1957), 163–167 | DOI | MR

[12] Knuth D. E., Pittel B., “A recurrence related to trees”, Proc. Amer. Math. Soc., 105:2 (1989), 335–349 | DOI | MR | Zbl

[13] Read R. C., “Some unusual enumeration problems”, Ann. New York Acad. Sci., 175 (1970), 314–326 | DOI | MR | Zbl

[14] Wright E. M., “The number of connected sparsely edged graphs”, J. Graph Theory, 1:4 (1977), 317–330 | DOI | MR | Zbl

[15] Wright E. M., “The number of connected sparsely edged graphs. II”, J. Graph Theory, 2:4 (1978), 299–305 | DOI | MR | Zbl