About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:2, 302-310
Volume 23, No 2, 2016, P. 5-20
UDC 519.175.3
V. A. Voblyi
Enumeration of labeled connected graphs with given order and number of edges
Abstract:
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, cactus, asymptotics.
DOI: 10.17377/daio.2016.23.501
Vitali A. Voblyi 1
1. Bauman Moscow State University,
5 2nd Baumanskaya St., 105005, Moscow, Russia
e-mail: vitvobl@yandex.ru
Received 13 July 2015
Revised 14 December 2015
References
[1] G. N. Bagaev and E. F. Dmitriev, The number of connected labeled bipartite graphs, Dokl. Akad. Nauk BSSR, 28, No. 12, 1061–1063, 1984.[2] V. A. Voblyi, Wright and Stepanov–Wright coefficients, Mat. Zametki, 42, No. 6, 854–862, 1987. Translated in Math. Notes Acad. Sci. USSR, 42, No. 6, 969–974, 1987.
[3] V. A. Voblyi, On enumeration of labelled connected graphs by the number of cutpoints, Diskretn. Mat., 20, No. 1, 52–63, 2008. Translated in Discrete Math. Appl., 18, No. 1, 57–69, 2008.
[4] V. A. Voblyi, A formula for the number of labeled connected graphs, Diskretn. Anal. Issled. Oper., 19, No. 4, 48–59, 2012.
[5] V. A. Voblyi, Enumeration of labeled connected bicyclic and tricyclic graphs without bridges, Mat. Zametki, 91, No. 2, 308–311, 2012. Translated in Math. Notes, 91, No. 1, 293–297, 2012.
[6] V. A. Voblyi, Enumeration of labeled bicyclic and tricyclic Eulerian graphs, Mat. Zametki, 92, No. 5, 678–683, 2012. Translated in Math. Notes, 92, No. 5–6, 619–623, 2012.
[7] V. A. Voblyi, Enumeration of labeled Eulerian cacti, in Materialy XI Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya” (Proc. XI Int. Seminar “Discrete Math. and Its Applications”), Moscow, Russia, Jan. 18–23, 2012, pp. 275–277, Izd. Mekh.-Mat. Fak. MGU, Moscow, 2012.
[8] V. A. Voblyi, Enumeration of labeled geodetic planar graphs, Mat. Zametki, 97, No. 3, 336–341, 2015. Translated in Math. Notes, 97, No. 3, 321–325, 2015.
[9] V. A. Voblyi and A. K. Meleshko, The number of labeled block-cactus graphs, Diskretn. Anal. Issled. Oper., 21, No. 2, 24–32, 2014. Translated in J. Appl. Indust. Math., 8, No. 3, 422427, 2014.
[10] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley & Sons, New York, 1983. Translated under the title Perechislitel’naya kombinatorika, Nauka, Moscow, 1990.
[11] A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, Integraly i ryady. T. 3: Elementarnye funktsii (Integrals and Series. Vol. 3: Elementary Functions), Nauka, Moscow, 1981.
[12] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969. Translated under the title Teoriya grafov, Mir, Moscow, 1973.
[13] F. Harary and E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973. Translated under the title Perechislenie grafov, Mir, Moscow, 1977.
[14] J. Riordan, Combinatorial Identities, John Wiley & Sons, New York, 1968. Translated under the title Kombinatornye tozhdestva, Nauka, Moscow, 1982.
[15] M. Drmota, É. Fusy, M. Kang, V. Kraus, and J. Rué, Asymptotic study of subcritical graph classes, 2010 (Cornell Univ. Libr. e-Print Archive, arXiv:1003.4699).
[16] L. Fleisher, Building chain and cactus representations of all minimum cuts from Hao–Orlin in the same asymptotic run time, J. Algorithms, 33, No. 1, 51–72, 1999.
[17] G. W. Ford and G. E. Uhlenbeck, Combinatorial problems in the theory graphs. I, Proc. Natl. Acad. Sci. USA, 42, No. 3, 122–128, 1956.
[18] G. W. Ford and G. E. Uhlenbeck, Combinatorial problems in the theory graphs. III, Proc. Natl. Acad. Sci. USA, 42, No. 8, 529–535, 1956.
[19] P. Leroux, Enumerative problems inspired by Mayer’s theory of cluster integrals, Electron. J. Comb., 11, No. R32, 1–28, 2004.
[20] F. W. J. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark, eds., NIST Handbook of Mathematical Functions, Cambridge Univ. Press, New York, 2010.
[21] R. Vicente, D. Saad, and Y. Kabashima, Error-correcting code on a cactus: A solvable model, Europhys. Lett., 51, No. 6, 698–704, 2000.
[22] E. M. Wright, The number of connected sparsely edged graphs. III. Asymptotic results, J. Graph Theory, 4, No. 4, 393–407, 1980.
