Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2021, 15:1, 169-174
Volume 28, No 1, 2021, P. 5-14
UDC 519.175.3
V. A. Voblyi
On the enumeration of labeled series-parallel $k$-cyclic 2-connected graphs
Abstract:
We deduce an explicit formula for the number of labeled series-parallel $k$-cyclic $n$-vertex 2-connected graphs and find the corresponding asymptotics for a large number of vertices and a fixed $k$. Under the uniform probability distribution, an asymptotic formula is obtained for the probability that a random $n$-vertex $k$-cyclic 2-connected graph with a large number of vertices and a fixed $k$ is a series-parallel graph.
Tab. 1, bibliogr. 11.
Keywords: enumeration, labeled graph, series-parallel graph, $k$-cyclic graph, asymptotics, random graph.
DOI: 10.33048/daio.2021.28.693
Vitaly A. Voblyi 1
1. All-Russian Institute for Scientific and Technical Information of RAS
20 Usievich Street, 125190 Moscow, Russia
e-mail: vitvobl@yandex.ru
Received June 11, 2020
Revised October 20, 2020
Accepted October 22, 2020
References
[1] M. Bodirsky, O. Gimenez, M. Kang, and M. Noy, Enumeration and limit laws of series-parallel graphs, Eur. J. Comb. 28 (8), 2091–2105 (2007).[2] S. Radhavan, Low-connectivity network design on series-parallel graphs, Networks 43 (3), 163–176 (2004).
[3] V. A. Voblyi, The second Riddell relation and its consequences, Diskretn. Anal. Issled. Oper. 26 (1), 20–32 (2019) [Russian] [J. Appl. Ind. Math. 13 (1), 168–174 (2019)].
[4] V. A. Voblyi and A. M. Meleshko, On the number of labeled series-parallel tricyclic blocks, in Proc. XV Int. Conf. ”Algebra, number theory, and discrete geometry. Current problems and applications,” Tula, Russia, May 28-31, 2018, (Izd. TGPU, Tula, 2018), pp. 168–170 [Russian].
[5] V. A. Voblyi, The number of labeled tetracyclic series-parallel blocks, Prikl. Diskretn. Mat., No. 47, 57–61 (2020) [Russian].
[6] M. A. Lavrentyev and B. V. Shabat, Methods of the theory of functions of a complex variable (Nauka, Moscow, 1965) [Russian].
[7] V. A. Voblyi, Explicit formula for the number of labeled series-parallel $k$-cyclic blocks, Mat. Zametki 108 (4), 622-624 (2020) [Russian] [Math. Notes 108 (4), 608-610 (2020)].
[8] The on-line encyclopedia of integer sequences, (The OEIS Foundation, Highland Park, NJ, 2020). Available at http://oeis.org (accessed Oct. 27, 2020).
[9] C. A. Charalambides, Enumerative combinatorics (CRC Press, Boca Raton, FL, 2002).
[10] Yu. I. Medvedev and G. I. Ivchenko, Asymptotic representations of finite differences of a power function at an arbitrary point, Teor. Veroyatn. Primen., 10 (1), 151–156 (1965) [Russian] [Theory Probab. Appl., 10 (1), 139–144 (1965)].
[11] E. M. Wright, The number of connected sparsely edged graphs. IV, J. Graph Theory 7 (2), 219–229 (1983).
