Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
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
Abstract:
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
References
[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.
