Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 4, 2021, P. 61-69
UDC 519.175.3
V. A. Voblyi
Asymptotic enumeration of labeled series-parallel $k$-cyclic bridgeless graphs
Abstract:
We deduce asymptotic formulas for the number of labeled connected series-parallel $k$-cyclic graphs with given order and fixed number $k$. We prove that almost all labeled series-parallel $k$-cyclic connected graphs without bridges for a fixed number of $k$ are blocks.
Bibliogr. 17.
Keywords: enumeration, labeled graph, block, bridgeless graph, series-parallel graph, $k$-cyclic graph, asymptotics, random graph
DOI: 10.33048/daio.2021.28.715
Vitaly A. Voblyi 1
1. All-Russian Institute for Scientific and Technical Information,
20 Usievich Street, 125190 Moscow, Russia
e-mail: vitvobl@yandex.ru
Received May 10, 2021
Revised August 8, 2021
Accepted August 16, 2021
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] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969; Mir, Moscow, 1973 [Russian]).
[3] C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb. 58 (11), 96–106 (2016).
[4] S. Radhavan, Low-connectivity network design on series-parallel graphs, Networks 43 (3), 163–176 (2004).
[5] V. A. Voblyi, The second Riddel relation and its consequences, Diskretn. Anal. Issled. Oper. 26 (1), 20–32 (2019) [Russian] [J. Appl. Ind. Math. 13 (1), 168–174 (2019)].
[6] V. A. Voblyi, On the enumeration of labeled series-parallel $k$-cyclic 2-connected graphs, Diskretn. Anal. Issled. Oper. 28 (1), 5–14 (2021) [Russian] [J. Appl. Ind. Math. 15 (1), 169–174 (2021)].
[7] P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Comb. Theory, Ser. B, 33, 276–305 (1982).
[8] V. A. Voblyi, Enumeration of labeled connected bicyclic and tricyclic graphs without bridges, Mat. Zametki 91 (1), 293–297 (2012) [Russian]. English version: Journal of Applied and Industrial Mathematics 15 (4) (2021).
[9] V. A. Voblyi, On the asymptotic enumeration of labeled connected $k$-cyclic graphs without bridges, Mat. Zametki 107 (2), 304–306 (2020) [Russian].
[10] V. A. Voblyi, On the number of labeled outerplanar $k$-cyclic bridgeless Graphs, Diskretn. Anal. Issled. Oper. 27 (1), 5–16 (2020) [Russian] [J. Appl. Ind. Math. 14 (1), 205–211 (2020)].
[11] 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)].
[12] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (Wiley, New York, 1983; Nauka, Moscow, 1990).
[13] J. Riordan, Combinatorial Identities (Wiley, New York, 1968; Nauka, Moscow, 1982 [Russian]).
[14] V. A. Voblyi, On an approach to enumeration of labeled connected graphs: A review, Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh. Temat. Obz. 188, 106–118 (2020).
[15] E. C. Titchmarsh, The Theory of Functions (Oxford Univ. Press, London, 1975; Nauka, Moscow, 1980 [Russian]).
[16] P. Flajolet, Analytic Combinatorics (Cambridge, Cambridge Univ. Press, 2009).
[17] E. M. Wright, The number of connected sparsely edged graphs. IV, J. Graph Theory, 7 (2), 219–229 (1983).
