Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:1, 168-174
Volume 26, No 1, 2019, P. 20-32
UDC 519.175.3
V. A. Voblyi
The second Riddel relation and its consequences
Abstract:
The second Riddell relation relates the generating functions for the number of labeled connected graphs and the number of labeled blocks. We consider the conditions under which this relation is true for a subclass of connected graphs. Under these conditions, the formulas are valid that express the number of graphs from a subclass of labeled connected graphs trough the generating function of their blocks. By way of application, we obtain expressions for the numbers of labeled connected and 2-connected series-parallel graphs.
Bibliogr. 22.
Keywords: enumeration, labeled graph, connected graph, 2-connected graph, generating function, block-stable class, series-parallel graph.
DOI: 10.33048/daio.2019.26.615
Vitaly A. Voblyi 1
1. All-Russian Institute for Scientific and Technical Information RAS,
20 Usievicha St., 125190 Moscow, Russia
e-mail: vitvobl@yandex.ru
Received April 3, 2018
Revised October 1, 2018
Accepted November 28, 2018
References
[1] V. A. Voblyi, On enumeration of labelled connected graphs by the number of cutpoints, Diskretn. Mat., 20, No. 1, 52–63, 2008 [Russian]. Translated in Discrete Math. Appl., 18, No. 1, 57–69, 2008.[2] V. A. Voblyi, A formula for the number of labeled connected graphs, Diskretn. Anal. Issled. Oper., 19, No. 4, 48–59, 2012 [Russian].
[3] V. A. Voblyi, Enumeration of labeled connected graphs with given order and size, Diskretn. Anal. Issled. Oper., 23, No. 2, 5–20, 2016 [Russian]. Translated in J. Appl. Ind. Math., 10, No. 2, 302–310, 2016.
[4] V. A. Voblyi and A. K. Meleshko, Enumeration of labeled block-cactus graphs, Diskretn. Anal. Issled. Oper., 21, No. 2, 24–32, 2014 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 3, 422–427, 2014.
[5] 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 [Russian].
[6] V. N. Sachkov, An Introduction to Combinatorial Methods of Discrete Mathematics, MTsNMO, Moscow, 2004 [Russian].
[7] F. Harary and E. M. Palmer, Graphical Enumeration, Acad. Press, New York, 1973. Translated under the title Perechislenie grafov, Mir, Moscow, 1977 [Russian].
[8] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. Univ. Press, Cambridge, 1998.
[9] M. Bodirsky, O. Gimenez, M. Kang, and M. Noy, Enumeration and limit laws of series-parallel graph, Eur. J. Comb., 28, 2091–2105, 2007.
[10] M. Drmota, Random Trees: An Interplay between Combinatorics and Probability, Springer, Wien, 2009.
[11] G. W. Ford and G. E. Uhlenbeck, Combinatorial problems in the theory of graphs. I, Proc. Natl. Acad. Sci. USA, 42, No. 3, 122–128, 1956.
[12] C. McDiarmid and A. Scott, Random graphs from a block stable class, Eur. J. Comb., 58, 96–106, 2016.
[13] G. Labelle, P. Leroux, and M. G. Ducharme, Graph weights arising from Mayer’s theory cluster integrals, Sémin. Lothar. Comb., 54, Art. B54m, 2007.
[14] A. Meir and J. W. Moon, On nodes of degree two in random trees, Mathematika, 15, No. 2, 188–192, 1968.
[15] M. Noy, Random planar graphs and beyond, Proc. Int. Congr. Math., Seoul, Korea, Aug. 13–21, 2014, Vol. IV, pp. 407–430, ICM 2014 Organ. Comm., Seoul, 2014.
[16] S. Radhavan, Low-connectivity network design on series-parallel graphs, Networks, 43, No. 3, 163–176, 2004.
[17] R. J. Riddell, Jr. and G. E. Uhlenbeck, On the theory of the virial development of the equation of state of monoatomic gases, J. Chem. Phys., 21, No. 11, 2056–2063, 1953.
[18] J. G. Stemple and M. E. Watkins, On planar geodetic graphs, J. Comb. Theory, 4, No. 2, 101–117, 1968.
[19] K. Takamizawa, T. Nishezeki, and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, No. 3, 623–641, 1982.
[20] S. Tazawa, Enumeration of labeled 2-connected Euler graphs, J. Comb. Inf. Syst. Sci., 23, No. 1–4, 407–414, 1998.
[21] The On-Line Encyclopedia of Integer Sequences. Available at http://oeis.org (accessed Nov. 5, 2018).
[22] H. Whitney, Non-separable and planar graphs, Trans. Am. Math. Soc., 34, No. 2, 339–362, 1932.
