On an approach to enumeration of labeled connected graphs: A review

V. A. Voblyi

Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Differential Equations and Mathematical Modeling, Tome 188 (2020), pp. 106-118

Résumé

The classical functional Riddell equation connects the generating functions of labeled connected graphs and their blocks. Using the Lagrange inversion theorem, the author obtained from this equation a formula, which is a convenient tool for the exact and asymptotic enumeration of labeled graphs in the case where the generating function of their blocks is known. This formula is valid for block-stable graph classes. A review of enumerative results obtained by using this approach for cacti, block-cactus graphs, Eulerian graphs, geodesic graphs, planar graphs, and series-parallel graphs is presented.

Détail

Keywords: enumeration, labeled graph, connected graph, block.

Bibliographie

[1] Voblyi V. A., “O koeffitsientakh Raita i Stepanova—Raita”, Mat. zametki., 42:6 (1987), 854–862

[2] Voblyi V. A., “O perechislenii pomechennykh svyaznykh grafov po chislu tochek sochleneniya”, Diskr. mat., 20:1 (2008), 52–63 | Zbl

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

[4] Voblyi V. A., “Perechislenie pomechennykh eilerovykh kaktusov”, Mat. XI Mezhdunar. semin. «Diskretnaya matematika i ee prilozheniya», MGU, M., 2012, 275–277

[5] Voblyi V. A. Perechislenie pomechennykh geodezicheskikh planarnykh grafov, Mat. zametki., 97:3 (2015), 336–341 | MR | Zbl

[6] Voblyi V. A., “Vyrazhenie chisla pomechennykh svyaznykh grafov cherez chislo pomechennykh blokov s pomoschyu mnogochlenov razbienii”, Tez. dokl. Mezhdunar. nauch. konf. «Diskretnaya matematika, algebra i ikh prilozheniya» (14-18 sentyabrya 2015 g. Minsk, Belarus), Minsk, 2015, 95–96

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

[8] Voblyi V. A., “Perechislenie pomechennykh geodezicheskikh grafov s malym tsiklomaticheskim chislom”, Mat. zametki., 101:5 (2017), 684–689 | MR | Zbl

[9] Voblyi V. A., “Chislo pomechennykh vneshneplanarnykh $k$-tsiklicheskikh grafov”, Mat. zametki., 103:5 (2018), 657–666 | MR | Zbl

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

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

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

[13] Voblyi V. A., “Perechislenie pomechennykh posledovatelno-parallelnykh tritsiklicheskikh grafov//”, Itogi nauki tekhn. Ser. Sovr. mat. prilozh. Temat. obzory., 177 (2020), 132–136

[14] Voblyi V. A. Asimptoticheskoe perechislenie pomechennykh posledovatelno-parallelnykh tetratsiklicheskikh grafov, Itogi nauki tekhn. Ser. Sovr. mat. prilozh. Temat. obzory., 187 (2020), 31–35

[15] Voblyi V. A., “Perechislenie pomechennykh eilerovykh pentatsiklicheskikh grafov”, Prikl. diskr. mat., 2020, no. 50, 87–92

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

[17] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh eilerovykh polnoblochnykh grafov”, Mat. XV Mezhdunar. semin. «Kombinatornye konfiguratsii i ikh prilozheniya», Kirovograd, 2013, 15–28

[18] 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, 2013, 9–11

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

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

[21] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh dvudolnykh kaktusov”, Mat. IX Mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem», M., 2015, 57–58

[22] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh planarnykh polnoblochno-kaktusnykh grafov”, Mat. XX Mezhdunar. semin. «Diskretnaya matematika i ee prilozheniya», M., 2016, 287–290

[23] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh kaktusov bez treugolnikov”, Mat. XIX Mezhdunar. semin. «Kombinatornye konfiguratsii i ikh prilozheniya», Kropivnitskii, 2017, 17–19

[24] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh dvudolnykh $k$-tsiklicheskikh kaktusov”, Tr. X Mezhdunar. konf. «Diskretnye modeli v teorii upravlyayuschikh sistem», M., 2018, 86–88

[25] Voblyi V. A., Meleshko A. K., “Perechislenie pomechennykh eilerovykh kaktusov bez treugolnikov”, Mat. XV Mezhdunar. konf. «Algebra, teoriya chisel i diskretnaya geometriya. Sovremennye problemy i prilozheniya», Tula, 2018, 165–168

[26] Gulden Ya., Dzhekson D., Perechislitelnaya kombinatorika, Nauka, M., 1990 | MR

[27] Ivanchik I. I., “Problemy teorii grafov v statisticheskoi fizike”, Tr. Fiz. in-ta AN SSSR., 106 (1979), 3–89 | MR

[28] Kalmykov G. I., Drevesnaya klassifikatsiya pomechennykh grafov, Fizmatlit, M., 2003

[29] Kalmykov G. I., Karkasnaya klassifikatsiya pomechennykh grafov, Fizmatlit, M., 2006

[30] Riordan Dzh., Kombinatornye tozhdestva, Nauka, M., 1982 | MR

[31] Stenli R., Perechislitelnaya kombinatorika. Derevya, proizvodyaschie funktsii i simmetricheskie funktsii, Mir, M., 2005

[32] Sachkov V. N., Vvedenie v kombinatornye metody diskretnoi matematiki, MTsNMO, M., 2004

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

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

[35] Amudha P., Sagayaraj A. C. C., Sheela A. C. S., “An application of graph theory in cryptography”, Int. J. Pure Appl. Math., 119:13 (2018), 375–383

[36] Bergeron F., Labelle G., Leroux P., Combinatorial Species and Tree-Like Structures, Cambridge Univ. Press, Cambridge, 1998 | MR | Zbl

[37] Bodirsky M., Kang M., “Generating outerplanar graphs uniformly at random”, Combin. Probab. Comput., 15:3 (2006), 333–343 | DOI | MR | Zbl

[38] 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

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

[40] Drmota M., Random Trees, Springer, Wien–NewYork, 2009 | MR | Zbl

[41] Drmota M., Fusy E., Kang M., Kraus V., Rue J., “Asymptotic study of subcritical graph classes”, SIAM J. Discr. Math., 25:4 (2011), 1615–1651 | DOI | MR | Zbl

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

[43] Fleisher L., “Building chain and cactus representations of all minimum cuts from Hao–Orlin in the same asymptotic run time”, J. Algorithms., 33:5 (1999 *s 51–72) | MR

[44] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in the theory of graphs, I”, Proc. Natl. Acad. Sci. U.S.A., 42:3 (1956), 122–128 | DOI | MR | Zbl

[45] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in theory graphs, III”, Proc. Natl. Acad. Sci. U.S.A., 42 (1956), 529–535 | DOI | MR | Zbl

[46] Frasser C. E., “$k$-Geodetic graphs and their application to the topological design of computer networks”, Proc. Argentinian Workshop on Theoretical Computer Science (28 JAIIO-WAIT'99), 1999, 187–203

[47] Kumar A., “A study on Euler graph and its applications”, Int. J. Math. Trends Technol., 43:1 (2017), 9–14 | DOI | MR

[48] Labelle G., Leroux P., Ducharme M. G., “Graph weights arising from Mayer's theory cluster integrals”, Sém. Lothar. Combin., 54 (2007), B54m | MR

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

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

[51] Moon J., Counting Labelled Trees, Can. Math. Congr., Montreal, 1970 | MR | Zbl

[52] NIST Handbook of Mathematical Gunctions, Cambridge Univ. Press, New York, 2010

[53] Noy M., “Random planar graphs and beyond”, Proc. Int. Congr. Math., Seoul, 2014, 407–431 | MR

[54] Noy M., “Graphs”, Handbook of Enumerative Combinatorics, CRC Press, 403–442 | MR

[55] Pancoska P., Moravek Z., Moll U. M., “Rational design of DNA sequences for nanotechnology, microarrays and molecular computers using Eulerian graphs”, Nucl. Acids Res., 32:15 (2004), 4630–4645 | DOI

[56] Percus J. M., Combinatorial Methods, Springer, New York–Heidelberg–Berlin, 1971 | MR | Zbl

[57] Radhavan S., “Low-connectivity network design on series-parallel graphs”, Networks., 43:3 (2004), 163–176 | DOI | MR

[58] Randerath B., Volkmann L., “A characterization of well covered block-cactus graphs”, Australas. J. Combin., 9 (1994), 307–314 | MR | Zbl

[59] Read R. C., “Euler graphs on labelled nodes”, Can. J. Math., 14 (1962), 482–486 | DOI | MR | Zbl

[60] Riddell R. J., “On the theory of the virial development of the equation of state of monoatomic gases”, J. Chem. Phys., 11:11 (1953), 2056–2064 | DOI | MR

[61] Stemple J. G., Watkins M. E., “On planar geodetic graphs”, J. Combin. Theory., 4 (1968), 101–117 | DOI | MR | Zbl

[62] Takamizawa K., Nishezeki T., Saito N., “Linear-time computability of combinatorial problems on series-parallel graphs”, J. ACM., 29:3 (1982), 623–641 | DOI | MR | Zbl

[63] Tazawa S., “Enumeration of labeled 2-connected Euler graphs”, J. Combin. Inform. System Sci., 23:1-4 (1998), 407–414 | MR | Zbl

[64] Vicente R., Saad D., Kabashima Y., “Error-correcting code on a cactus: a solvable model”, Europhys. Lett., 51:6 (2000), 698–704 | DOI

[65] Whitney H., “Non-separable and planar graphs”, Trans. Am. Math. Soc., 34 (1932), 339–362 | DOI | MR

[66] Wright E. M., “The number of connected sparsely edged graphs, III”, J. Graph Theory., 4:4 (1980), 393–407 | DOI | MR | Zbl

[67] Wright E. M., “The number of connected sparsely edged graphs, IV”, J. Graph Theory., 7:2 (1983), 219–229 | DOI | MR | Zbl