Том 23, номер 2, 2016 г., Стр. 5-20

УДК 519.175.3
Воблый В. А.
О перечислении помеченных связных графов с заданными числами вершин и рёбер

Аннотация:
Получена новая формула, выражающая число помеченных связных графов с заданными числами вершин и рёбер через производящую функцию их блоков. В качестве приложения перечисляются точно и асимптотически кактусы с заданными числом вершин и цикломатическим числом.
Табл. 1, библиогр. 22.

Ключевые слова: перечисление, помеченный граф, блок, кактус, асимптотика.

DOI: 10.17377/daio.2016.23.501

Воблый Виталий Антониевич ¹
1. Московский гос. техн. университет им. Н. Э. Баумана,
2-я Бауманская ул., 5, стр. 1, 105005 Москва, Россия
е-mail: vitvobl@yandex.ru

Статья поступила 13 июля 2015 г.
Исправленный вариант — 14 декабря 2015 г.

Литература

[1] Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных отмеченных двудольных графов // Докл. АН БССР. 1984. T. 28, № 12. C. 1061–1063.

[2] Воблый В. А. О коэффициентах Райта и Степанова — Райта // Мат. заметки. 1987. T. 42, вып. 6.
C. 854–862.

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

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

[5] Воблый В. А. Перечисление помеченных бициклических и трициклических графов без мостов // Мат. заметки. 2012. T. 91, вып. 2. C. 308–311.

[6] Воблый В. А. Перечисление помеченных связных бициклических и трициклических эйлеровых графов // Мат. заметки. 2012. Т. 92, вып. 5. C. 678–683.

[7] Воблый В. А. Перечисление помеченных эйлеровых кактусов // Мат. XI Междунар. семинара «Дискретная математика и её приложения» (Москва, 18–23 янв. 2012 г.). М.: МГУ, 2012. C. 275–277.

[8] Воблый В. А. Перечисление помеченных геодезических планарных графов // Мат. заметки. 2015. T. 97, вып. 3. C. 336–341.

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

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

[11] Прудников А. П. и др. Интегралы и ряды. T. 1. М.: Наука, ГРФМЛ, 1981. 800 с.

[12] Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

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

[14] Риордан Дж. Комбинаторные тождества. М.: Наука, 1982. 256 с.

[15] Drmota M., Fusy É., Kang M., Kraus V., Rué J. Asymptotic study of subcritical graph classes // arXiv:1003.4699v1 [math.CO] 24 Mar. 2010.

[16] Fleisher L. Building chain and cactus representations of all minimum cuts from Hao–Orlin in the same asymptotic run time // J. Algorithms. 1999. Vol. 33, No. 1. P. 51–72.

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

[18] Ford G. W., Uhlenbeck G. E. Combinatorial problems in the theory of graphs, III // Proc. Nat. Acad. Sci. USA. 1956. Vol. 42, No. 8. P. 529–535.

[19] Leroux P. Enumerative problems inspired by Mayer’s theory of cluster integrals // Electron. J. Comb. 2004. Vol. 11, No. R32. P. 1–28.

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

[21] Vicente R., Saad D., Kabashima Y. Error-correcting code on a cactus: a solvable model // Europhys. Lett. 2000. Vol. 51, No. 6. P. 698–704.

[22] Wright E. M. The number of connected sparsely edged graphs. III // J. Graph Theory. 1980. Vol. 4, No. 4. P. 393–407.