Geodesic
Enumeration of labeled connected graphs with given order and number of edges
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 5-20.

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

We deduce a new formula for the number of labeled connected graphs with a given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number. Tab. 1, bibliogr. 22.
Keywords: enumeration, labeled graph, block, asymptotics.
Mots-clés : cactus 
@article{DA_2016_23_2_a0,
     author = {V. A. Voblyi},
     title = {Enumeration of labeled connected graphs with given order and number of edges},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--20},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_2_a0/}
}
TY  - JOUR
AU  - V. A. Voblyi
TI  - Enumeration of labeled connected graphs with given order and number of edges
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 5
EP  - 20
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_2_a0/
LA  - ru
ID  - DA_2016_23_2_a0
ER  - 
%0 Journal Article
%A V. A. Voblyi
%T Enumeration of labeled connected graphs with given order and number of edges
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 5-20
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_2_a0/
%G ru
%F DA_2016_23_2_a0
V. A. Voblyi. Enumeration of labeled connected graphs with given order and number of edges. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 2, pp. 5-20. http://geodesic.mathdoc.fr/item/DA_2016_23_2_a0/

[1] G. N. Bagaev, E. F. Dmitriev, “The number of connected labeled bipartite graphs”, Dokl. Akad. Nauk BSSR, 28:12 (1984), 1061–1063 | MR | Zbl

[2] V. A. Voblyi, “Wright and Stepanov–Wright coefficients”, Math. Notes Acad. Sci. USSR, 42:6 (1987), 969–974 | DOI | MR | Zbl

[3] V. A. Voblyi, “On enumeration of labelled connected graphs by the number of cutpoints”, Discrete Math. Appl., 18:1 (2008), 57–69 | DOI | DOI | MR | Zbl

[4] V. A. Voblyi, “A formula for the number of labeled connected graphs”, Diskretn. Anal. Issled. Oper., 19:4 (2012), 48–59 | MR | Zbl

[5] V. A. Voblyi, “Enumeration of labeled connected bicyclic and tricyclic graphs without bridges”, Math. Notes, 91:1 (2012), 293–297 | DOI | DOI | MR | Zbl

[6] V. A. Voblyi, “Enumeration of labeled bicyclic and tricyclic Eulerian graphs”, Math. Notes, 92:5–6 (2012), 619–623 | DOI | DOI | MR | Zbl

[7] V. A. Voblyi, “Enumeration of labeled Eulerian cacti”, Proc. XI Int. Seminar “Discrete Math. and Its Applications” (Moscow, Russia, Jan. 18–23, 2012), Izd. Mekh.-Mat. Fak. MGU, Moscow, 2012, 275–277

[8] V. A. Voblyi, “Enumeration of labeled geodetic planar graphs”, Math. Notes, 97:3 (2015), 321–325 | DOI | DOI | MR | Zbl

[9] V. A. Voblyi, A. K. Meleshko, “The number of labeled block-cactus graphs”, J. Appl. Indust. Math., 8:3 (2014), 422–427 | DOI | MR | Zbl

[10] I. P. Goulden, D. M. Jackson, Combinatorial Enumeration, John Wiley Sons, New York, 1983 | MR | MR | Zbl

[11] A. P. Prudnikov, Yu. A. Brychkov, O. I. Marichev, Integrals and Series, v. 1, Elementary Functions, Nauka, Moscow, 1981 | MR

[12] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969 | MR | MR | Zbl

[13] F. Harary, E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973 | MR | MR | Zbl

[14] J. Riordan, Combinatorial Identities, John Wiley Sons, New York, 1968 | MR | MR | Zbl

[15] Drmota M., Fusy E., Kang M., Kraus V., Rue J., Asymptotic study of subcritical graph classes, 24 Mar. 2010, arXiv: 1003.4699v1[math.CO] | MR

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

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

[18] Ford G. W., Uhlenbeck G. E., “Combinatorial problems in the theory of graphs, III”, Proc. Nat. Acad. Sci. USA, 42:8 (1956), 529–535 | DOI | MR | Zbl

[19] Leroux P., “Enumerative problems inspired by Mayer's theory of cluster integrals”, Electron. J. Comb., 11:R32 (2004), 1–28 | MR | Zbl

[20] Olver F. W. J., Lozier D. W., Boisvert R. F., Clark C. W., NIST. Handbook of mathematical functions, Cambridge Univ. Press, New York, 2010, 951 pp. | MR | Zbl

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

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