Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:1, 205-211
Volume 27, No 1, 2020, P. 5-16
UDC 519.175.3
V. A. Voblyi
On the number of labeled outerplanar k-cyclic bridgeless graphs
Abstract:
We obtain an explicit formula for the number of labeled connected outerplanar k-cyclic n-vertex bridgeless graphs. We find asymptotics for the number of those graphs for a large number of vertices and fixed k. As a consequence, we prove that, for k fixed, almost all labeled connected outerplanar k-cyclic graphs have bridges.
Tab. 1, bibliogr. 14.
Keywords: enumeration, labeled graph, outerplanar graph, bridgeless graph, k-cyclic graph, asymptotics.
DOI: 10.33048/daio.2020.27.653
Vitaly A. Voblyi 1
1. Russian Institute for Scientific and Technical Information RAS
20 Usievich Street, 125190 Moscow, Russia
e-mail: vitvobl@yandex.ru
Received March 21, 2019
Revised October 9, 2019
Accepted November 27, 2019
References
[1] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969; Mir, Moscow, 1973).[2] M. Bodirsky and M. Kang, Generating outerplanar graphs uniformly at random, Comb. Probab. Comput. 15 (3), 333–343 (2006).
[3] 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).
[4] M. Drmota, E. Fusy, M. Kang, V. Kraus, and J. Rue, Asymptotic study of subcritical graph classes, SIAM J. Discrete Math. 25 (4), 1615–1651 (2011).
[5] V. A. Voblyi, Number of labeled outerplanar k-cyclic graphs, Mat. Zametki 103 (5), 657–666 (2018).
[6] V. A. Voblyi, A simple formula for the number of labeled outerplanar k-cyclic blocks and their asymptotic counting, in Proc. XII Int. Workshop “Discrete Mathematics and Its Applications”, Moscow, Russia, June 20–25, 2016 (Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., Moscow, 2016), pp. 285–287.
[7] P. Hanlon and R. W. Robinson, Counting bridgeless graphs, J. Comb. Theory, Ser. B, 33 (3), 276–305 (1982).
[8] V. A. Voblyi, Enumeration of labeled connected graphs with given order and size, Diskretn. Anal. Issled. Oper. 23 (2), 5–20 (2016). [J. Appl. Ind. Math. 10 (2), 302–310 (2016)].
[9] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration (J. Wiley & Sons, New York, 1983; Nauka, Moscow, 1990).
[10] V. A. Voblyi, The second Riddell relation and its consequences, Diskretn. Anal. Issled. Oper. 26 (1), 20–32 (2019) [J. Appl. Ind. Math. 13 (1), 168–174 (2019)].
[11] C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb. 58, 96–106 (2016).
[12] M. Noy, Random planar graphs and beyond, in Proc. Int. Congr. of Mathematicians, Seoul, Korea, Aug. 13–21, 2014, Vol. IV (ICM 2014 Organ. Comm., Seoul, 2014), pp. 407–431.
[13] F. Harary and E. M. Palmer, Graphical Enumeration (Acad. Press, New York, 1973; Mir, Moscow, 1977).
[14] V. A. Voblyi, Enumeration of labeled Euler cactuses, in Proc. XI Int. Workshop “Discrete Mathematics and Its Applications”, Moscow, Russia, Jan. 18–23, 2012 (Izd. Mekh.-Mat. Fak. Mosk. Gos. Univ., Moscow, 2012), pp. 275–277.
