Том 19, номер 4, 2012 г., Стр. 48-59
УДК 519.175.3
Воблый В. А.
Об одной формуле для числа помеченных связных графов
Аннотация:
Получена новая формула, выражающая число помеченных связных графов через производящую функцию их блоков. В качестве приложения рассматриваются кактусы и связные внешнепланарные графы.
Библиогр. 13.
Ключевые слова: перечисление, связный граф, блок, кактус, внешнепланарный граф.
Воблый Виталий Антониевич 1
1. Московский гос. техн. университет им. Н. Э. Баумана,
ул. 2-я Бауманская, 5, 105005 Москва, Россия
е-mail: vitvobl@yandex.ru
Статья поступила 25 сентября 2011 г.
Литература
[1] Воблый В. А. О перечислении помеченных связных графов по числу точек сочленения // Дискрет. математика. — 2008. — T. 20, вып. 1. — C. 14–23.
[2] Гульден Я., Джексон Д. Перечислительная комбинаторика. — М.: Наука, ГРФМЛ, 1990. — 504 c.
[3] Прудников А. П. и др. Интегралы и ряды. T. 1. — М.: Наука, ГРФМЛ, 1981. — 800 c.
[4] Харари Ф. Теория графов. М.: Мир, 1973. — 300 c.
[5] Харари Ф., Палмер Э. Перечисление графов. — М.: Мир, 1977. — 324 c.
[6] Bodirsky M., Gimenez O., Kang M., Noy M. Enumeration and limit laws of series-parallel graphs // Eur. J. Comb. — 2007. — Vol. 28. — P. 2091–2105.
[7] Bona M., Bousqet M., Labelle M., Leroux P. Enumeration of $m$-ary cacti // Adv. Appl. Math. — 2000. — Vol. 24. — P. 22–56.
[8] Flajolet Ph., Sedgewick R. Analytic combinatorics. — Cambridge: Cambridge Univ. Press, 2009. — 810 p.
[9] Ford G.W., Uhlenbeck G. E. Combinatorial problems in theory graphs. I // Proc. Natl. Acad. Sci. USA. — 1956. — Vol. 42. — P. 122–128.
[10] Ford G.W., Uhlenbeck G. E. Combinatorial problems in theory graphs. III // Proc. Natl. Acad. Sci. USA. — 1956. — Vol. 42. — P. 529–535.
[11] Leroux P. Enumerative problems inspired by Mayer’s theory of cluster integrals // Electron. J. Comb. — 2004. — Vol. 11. — R32.
[12] Moon J. Counting labelled trees. — Montreal: Can. Math. Congress, 1970. — 110 p.
[13] The on-line encyclopedia of integer sequences. — http://www.research.att.com/ njas/sequences.
