Volume 29, No 4, 2022, P. 5-14

UDC 519.175.3
V. A. Voblyi
On asymptotic enumeration of labeled series-parallel $k$-cyclic graphs

Abstract:
We deduce an asymptotic formula for the number of labeled connected series-parallel $k$-cyclic graphs with given order and fixed number $k$. Under uniform probability distribution, we find the probability that a random labeled connected $n$-vertex $k$-cyclic graph with a fixed $k$ and $n \to \infty$ is a series-parallel graph. In addition, we determine the probability that, under uniform probability distribution, a random labeled connected series-parallel $n$-vertex $k$-cyclic graph with a fixed $k$ and $n \to \infty$ is a cactus.
Bibliogr. 16.

Keywords: enumeration, labeled graph, block, series-parallel graph, $k$-cyclic graph, asymptotics, random graph.

DOI: 10.33048/daio.2022.29.732

Vitaly A. Voblyi¹
1. All-Russian Institute for Scientific and Technical Information,
20 Usievich Street, 125190 Moscow, Russia
e-mail: vitvobl@yandex.ru

Received February 7, 2022
Revised April 17, 2022
Accepted April 19, 2022

References

[1] F. Harary, Graph Theory (Addison-Wesley, London, 1969; Mir, Moscow, 1973 [Russian]).

[2] 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).

[3] C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb. 58, 96–106 (2016).

[4] S. Raghavan, Low-connectivity network design on series-parallel graphs, Networks 43 (3), 163–176 (2004).

[5] K. Takamizawa, T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM 29 (3), 623–641 (1982).

[6] V. A. Voblyi, Enumeration of labeled series-parallel tricyclic graphs, Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 177 (VINITI RAN, Moscow, 2020), pp. 132–136 [Russian]. English version: Journal of Applied and Industrial Mathematics 16 (4) (2022).

[7] V. A. Voblyi, Asymptotical enumeration of labeled series-parallel tetracyclic graphs, Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz., Vol. 187 (VINITI RAN, Moscow, 2020), pp. 31–35 [Russian].

[8] NIST Handbook of Mathematical Functions (Cambridge Univ. Press, New York, 2010).

[9] V. A. Voblyi, Enumeration of labeled connected graphs with given order and size, Diskretn. Anal. Issled. Oper. 23 (2), 5–20 (2016) [Russian] [J. Appl. Ind. Math. 10 (2), 302–310 (2016)].

[10] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (John Wiley Sons, New York, 1983; Nauka, Moscow, 1990 [Russian]).

[11] J. Riordan, Combinatorial Identities (John Wiley Sons, New York, 1968; Nauka, Moscow, 1982 [Russian]).

[12] 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)].

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

[14] E. M. Wright, The number of connected sparsely edged graphs. II, J. Graph Theory 2 (4), 299–305 (1978).

[15] V. A. Voblyi, Asymptotical enumeration of labeled series-parallel $k$-cyclic bridgeless graphs, Diskretn. Anal. Issled. Oper. 28 (4), 61–69 (2021) [Russian] [J. Appl. Ind. Math. 15 (4) (2019)].

[16] E. M. Wright, The number of connected sparsely edged graphs. III, J. Graph Theory 4 (4), 393–407 (1980).