English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 296-303

Volume 24, No 2, 2017, P. 18-31

UDC 519.175.3
V. A. Voblyi and A. K. Meleshko
Enumeration of labeled outerplanar bicyclic and tricyclic graphs

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.

DOI: 10.17377/daio.2017.24.544

Vitaly A. Voblyi 1
Anna K. Meleshko 1

1. Bauman Moscow State University,
5 Bld. 1 Vtoraya Baumanskaya St., 105005 Moscow, Russia
e-mail: vitvobl@yandex.ru, bakmeleshko@gmail.com

Received 10 May 2016
Revised 11 October 2016


[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, No. 4, 48–59, 2012 [Russian].

[3] V. A. Voblyi and A. K. Meleshko, Enumeration of labeled rose graphs, in Materialy XVI Mezhdunarodnogo nauchno-technicheskogo seminara “Kombinatornye konfiguratsii i ikh prilozheniya” (Proc. XVI Int. Sci. Tech. Seminar “Combinatorial Configurations and Its Applications”), Kirovograd, Ukraine, Apr. 11–12, 2014, pp. 27–29, Kirovograd Natl. Tech. Univ., Kirovograd, 2014 [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, and O. I. Marichev, Integraly i ryady: Elementarnye funktsii (Integrals and Series: Elementary Functions), Nauka, Moscow, 1981 [Russian].

[6] V. E. Stepanov, On some features of the structure of a random graph near a critical point, Teor. Veroyatn. Primen., 32, No. 4, 633–657, 1987 [Russian]. Translated in Theory Probab. Appl., 32, No. 4, 573–594, 1987.

[7] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969. Translated under the title Teoriya grafov, Mir, Moscow, 1973 [Russian].

[8] F. Harary and E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973. Translated under the title Perechislenie grafov, Mir, Moscow, 1977 [Russian].

[9] M. Bodirsky and M. Kang, Generating outerplanar graphs uniformly at random, Comb. Probab. Comput., 15, 333–343, 2006.

[10] M. Bodirsky, O. Gimenez, M. Kang, and M. Noy, Enumeration and limit laws of series-parallel graph, Eur. J. Comb., 28, 2091–2105, 2007.

[11] G. W. Ford and G. E. Uhlenbeck, Combinatorial problems in the theory of graphs. IV, Proc. Natl. Acad. Sci. USA, 43, No. 1, 163–167, 1957.

[12] D. E. Knuth and B. Pittel, A recurrence related to trees, Proc. Am. Math. Soc. 105, No. 2, 335–349, 1989.

[13] R. C. Read, Some unusual enumeration problems, Ann. N. Y. Acad. Sci. 175, 314–326, 1970.

[14] E. M. Wright, The number of connected sparsely edged graphs, J. Graph Theory, 1, No. 4, 317–330, 1977.

[15] E. M. Wright, The number of connected sparsely edged graphs. II. Smooth graphs and blocks, J. Graph Theory, 2, No. 4, 299–305, 1978.
 © Sobolev Institute of Mathematics, 2015