Том 26, номер 1, 2019 г., Стр. 20-32

УДК 519.175.3
Воблый В. А.
Второе соотношение Риддела и следствия из него

Аннотация:
Второе соотношение Риддела связывает производящие функции для числа помеченных связных графов и числа помеченных блоков. Рассматриваются условия, при которых это соотношение верно для подкласса связных графов. При этих условиях справедливы формулы, выражающие число графов из подкласса связных графов через производящую функцию их блоков. В качестве приложения получены выражения для чисел помеченных связных и 2-связных последовательно-параллельных графов.
Библиогр. 22.

Ключевые слова: перечисление, помеченный граф, связный граф, 2-связный граф, производящая функция, блочно-устойчивый класс, параллельно-последовательный граф.

DOI: 10.33048/daio.2019.26.615

Воблый Виталий Антониевич ¹
1. Всероссийский институт научной и технической информации РАН,
ул. Усиевича, 20, 125190 Москва, Россия
е-mail: vitvobl@yandex.ru

Статья поступила 3 апреля 2018 г.
После доработки — 1 октября 2018 г.
Принята к публикации 28 ноября 2018 г.

Литература

[1] Воблый В. А. О перечислении помеченных связных графов по числу точек сочленения. // Дискрет. математика. 2008. Т. 20, № 1. С. 52–63.

[2] Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 4. С. 48–59.

[3] Воблый В. А. О перечислении помеченных связных графов с заданными числами вершин и рёбер // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 2. С. 5–20.

[4] Воблый В. А., Мелешко А. К. Перечисление помеченных полноблочно-кактусных графов // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 2. С. 24–32.

[5] Гульден Я., Джексон Д. Перечислительная комбинаторика. М.: Наука, 1990. 504 с.

[6] Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: МЦНМО, 2004. 421 с.

[7] Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.

[8] Bergeron F., Labelle G., Leroux P. Combinatorial species and tree-like structures. Cambridge: Camb. Univ. Press., 1998. 457 p.

[9] Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Comb. 2007. Vol. 28, No. 8. P. 2091–2105.

[10] Drmota M. Random trees. Wien; NewYork: Springer, 2009. 458 p.

[11] Ford G. W., Uhlenbeck G. E. Combinatorial problems in the theory graphs, I // Proc. Nat. Acad. Sci. USA. 1956. Vol. 42, No. 3. P. 122–128.

[12] McDiarmid C., Scott A. Random graphs from a block stable class // Eur. J. Comb. 2016. Vol. 58. P. 96–106.

[13] Labelle G., Leroux P., Ducharme M. G. Graph weights arising from Mayer’s theory cluster integrals // Sémin. Lothar. Comb. 2007. Vol. 54, Art. B54m.

[14] Meir A., Moon J. W. On nodes of degree two in random trees // Mathe?matika. 1968. Vol. 15, No. 2. P. 188–192.

[15] Noy M. Random planar graphs and beyond // Proc. Int. Congr. Math. (Seoul, Korea, Aug. 13–21, 2014). Seoul, 2014. Vol. IV. P. 407–431.

[16] Radhavan S. Low-connectivity network design on series-parallel graphs // Networks. 2004. Vol. 43, No. 3. P. 163–176.

[17] Riddell R. J., Jr., Uhlenbeck G. E. On the theory of the virial development of the equation of state of monoatomic gases // J. Chem. Phys. 1953. Vol. 21, No. 11. P. 2056–2064.

[18] Stemple J. G., Watkins M. E. On planar geodetic graphs // J. Comb. Theory. 1968. Vol. 4, No. 2. P. 101–117.

[19] Takamizawa K., Nishezeki T., Saito N. Linear-time computability of combinatorial problems on series-parallel graphs // J. ACM. 1982. Vol. 29, No. 3. P. 623–641.

[20] Tazawa S. Enumeration of labeled 2-connected Euler graphs // J. Comb. Inform. Syst. Sci. 1998. Vol. 23, No. 1–4. P. 407–414.

[21] The on-line encyclopedia of integer sequences (http://oeis.org).

[22] Whitney H. Non-separable and planar graphs // Trans. Amer. Math. Soc. 1932. Vol. 34, No. 2. P. 339–362.