Geodesic
On enumeration of labeled connected bridgeless graphs
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the International Conference «Classical and Modern Geometry» dedicated to the 100th anniversary of the birth of Professor Levon Sergeyevich Atanasyan (July 15, 1921—July 5, 1998). Moscow, November 1–4, 2021. Part 4, Tome 223 (2023), pp. 138-147.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we obtain explicit formulas and asymptotics for some classes of bridgeless labeled graphs: cacti, block graphs, block-cactus graphs, and series-parallel graphs. We prove that, under a uniform probability distribution, almost all graphs from the classes considered have bridges.
Keywords: enumeration, labeled graph, $k$-cyclic graph, block, bridge, bridgeless graph, Eulerian graph, series-parallel graph, asymptotics, random graph. 
@article{INTO_2023_223_a13,
     author = {V. A. Voblyi},
     title = {On enumeration of labeled connected bridgeless graphs},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {138--147},
     publisher = {mathdoc},
     volume = {223},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2023_223_a13/}
}
TY  - JOUR
AU  - V. A. Voblyi
TI  - On enumeration of labeled connected bridgeless graphs
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2023
SP  - 138
EP  - 147
VL  - 223
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2023_223_a13/
LA  - ru
ID  - INTO_2023_223_a13
ER  - 
%0 Journal Article
%A V. A. Voblyi
%T On enumeration of labeled connected bridgeless graphs
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2023
%P 138-147
%V 223
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2023_223_a13/
%G ru
%F INTO_2023_223_a13
V. A. Voblyi. On enumeration of labeled connected bridgeless graphs. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the International Conference «Classical and Modern Geometry» dedicated to the 100th anniversary of the birth of Professor Levon Sergeyevich Atanasyan (July 15, 1921—July 5, 1998). Moscow, November 1–4, 2021. Part 4, Tome 223 (2023), pp. 138-147. http://geodesic.mathdoc.fr/item/INTO_2023_223_a13/

[1] Voblyi V. A., “Ob odnoi formule dlya chisla pomechennykh svyaznykh grafov”, Diskret. anal. issl. oper., 19:4 (2012), 48–59 | MR | Zbl

[2] Voblyi V. A., “Perechislenie pomechennykh eilerovykh kaktusov”, Mat. XI Mezhdunar. semin. «Diskretnaya matematika i ee prilozheniya» (Moskva, 18–23 iyunya 2012 g.), MGU, M., 2012, 275–277

[3] Voblyi V. A., “O perechislenii pomechennykh svyaznykh bitsiklicheskikh i tritsiklicheskikh grafov bez mostov”, Mat. zametki., 91:2 (2012), 308–311 | DOI | MR | Zbl

[4] Voblyi V. A., “O perechislenii pomechennykh svyaznykh grafov s zadannymi chislami vershin i reber”, Diskr. anal. issl. oper., 23:2 (2016), 5–20 | MR | Zbl

[5] Voblyi V. A., “Vtoroe sootnoshenie Riddela i sledstviya iz nego”, Diskr. anal. issl. oper., 26:1 (2019), 20–32 | Zbl

[6] Voblyi V. A., “O chisle pomechennykh vneshneplanarnykh $k$-tsiklicheskikh grafov bez mostov”, Diskr. anal. issl. oper., 27:1 (2020), 5–16 | MR | Zbl

[7] Voblyi V. A., “Ob asimptoticheskom perechislenii pomechennykh svyaznykh $k$-tsiklicheskikh grafov bez mostov”, Mat. zametki., 107:2 (2020), 304–306 | DOI | Zbl

[8] Voblyi V. A., “Asimptoticheskoe perechislenie pomechennykh posledovatelno-parallelnykh $k$-tsiklicheskikh grafov bez mostov”, Diskr. anal. issl. oper., 28:4 (2021), 61–69 | Zbl

[9] Voblyi V. A., “Utochnenie asimptotiki dlya chisla pomechennykh posledovatelno-parallelnykh grafov”, Mat. zametki., 109:6 (2021), 944–947 | DOI | Zbl

[10] Voblyi V. A., Meleshko A. K., “Novaya formula dlya chisla pomechennykh kaktusov s zadannym chislom vershin”, Tez. dokl. Mezhdunar. nauch. konf.«Diskretnaya matematika, teoriya grafov i ikh prilozheniya» (Minsk, 11–14 noyabrya 2013 g.), Minsk, 2013, 9–11

[11] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh polnoblochno-kaktusnykh grafov”, Diskr. anal. issl. oper., 21 (2014), 24–32 | MR | Zbl

[12] Voblyi V. A., Meleshko A. K., “Asimptoticheskoe perechislenie pomechennykh eilerovykh kaktusov”, Mat. XVII Mezhdunar. konf. «Problemy teoreticheskoi kibernetiki» (Kazan, 16-20 iyulya 2014 g.), Kazan, 2014, 58–60

[13] Gulden Ya., Dzhekson D., Perechislitelnaya kombinatorika, Nauka, M., 1990

[14] Prudnikov A. P. i dr., Integraly i ryady. T. 1, Nauka, M., 1981 | MR

[15] Kharari F., Teoriya grafov, Mir, M., 1973

[16] Kharari F., Palmer E., Perechislenie grafov, Mir, M., 1977

[17] Bodirsky M., Gimenez O., Kang M., Noy M., “Enumeration and limit laws of series-parallel graphs”, Eur. J. Combin., 28:8 (2007), 2091–2105 | DOI | MR | Zbl

[18] Carlitz L., “Single variable Bell polynomials”, Collect. Math., 14 (1962), 13–25 | MR | Zbl

[19] Flajolet P., Sedgewick G. E., Analytic Combinatorics, Cambridge Univ. Press, Cambridge, 2009 | MR | Zbl

[20] Hanlon P., Robinson R. W., “Counting bridgeless graphs”, J. Combin. Theory. Ser. B., 33:1 (1982), 276–305 | DOI | MR | Zbl

[21] Leroux P., “Enumerative problems inspired by Mayer's theory of cluster integrals”, Electron. J. Combin., 11 (2004), R32 | DOI | MR | Zbl

[22] McDiarmid C., Scott A., “Random graphs from a block stable class”, Eur. J. Combin., 58 (2016), 96–106 | DOI | MR | Zbl