Том 21, номер 2, 2014 г., Стр. 24–32
УДК 519.175.3
Воблый В. А., Мелешко А. К.
Перечисление помеченных полноблочно-кактусных графов
Аннотация:
Получены точные и асимптотические формулы для числа помеченных полноблочно-кактусных графов, а также для числа помеченных эйлеровых полноблочно-кактусных графов с заданным количеством вершин.
Табл. 1, библиогр. 15.
Ключевые слова: перечисление, полноблочный граф, кактус, полноблочнокактусный граф, асимптотика.
Воблый Виталий Антониевич 1
Мелешко Анна Константиновна 1
1. МГТУ им. Н. Э. Баумана,
2-я Бауманская ул., 5, 119333 Москва, Россия
е-mail: vitvobl@yandex.ru, konstantin_meleshko@rambler.ru
Статья поступила 22 июля 2013 г.
Литература
[1] Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анализ и исслед. операций. - 2012. - T. 19, №4. - C. 48–59.
[2] Воблый В. А. Перечисление помеченных эйлеровых кактусов // Мат. XI Междунар. семинара «Дискретная математика и её приложения». - М.: МГУ, 2012. - C. 275–277.
[3] Воблый В. А., Мелешко А. К. Перечисление помеченных эйлеровых полноблочных графов // Мат. XV Межвуз. семинара .Комбинаторные конфигурации и их приложения. (Кировоград, 2013). - Кировоград: Изд-во Кировоградского нац. тех. ун-та, 2013. - C. 15–18.
[4] Зыков А. А. Основы теории графов. - М.: Наука, 1987. - 382 с.
[5] Прудников А. П. и др. Интегралы и ряды. Т. 1. - М.: Наука, 1981. - 800 с.
[6] Татт У. Теория графов. - М.: Мир, 1988. - 424 с.
[7] Харари Ф., Палмер Э. Перечисление графов. - М.: Мир, 1977. - 324 с.
[8] Carlitz L. Single variable Bell polynomials // Collect. Math. - 1962. - Vol. 14. - P. 13–25.
[9] Flajolet Ph., Sedgewick R. Analytic combinatorics. - Cambridge: Cambridge Univ. Press, 2009. - 810 p.
[10] Ford G. W., Uhlenbeck G. E. Combinatorial problems in theory graphs. I // Proc. Nat. Acad. Sci. USA. - 1956. - Vol. 42. - P. 13–25.
[11] Husimi K. Note on Mayer’s theory of cluster integrals // J. Chem. Phys. - 1950. - Vol. 18. - P. 682–684.
[12] Lan J. K., Chang G. J. Algorithmic aspects of k-domination in graphs // Discrete Appl. Math. - 2013. - Vol. 161. - P. 1513–1520.
[13] Leroux P. Enumerative problems inspired by Mayer’s theory of cluster integrals // Electron. J. Comb. - 2004. - Vol. 11, N 32.
[14] Randerath B., Volkmann L. A characterization of well covered block-cactus graphs // Australasian J. Comb. - 1994. - Vol. 9. - P. 307-314.
[15] Wang F.-H., Wang Y.-L., Chang J.-M. The lower and upper forcing geodetic numbers of block-cactus graphs // Eur. J. Oper. Res. - 2006. - Vol. 175. - P. 238–245.
