Некоторые задачи перечисления помеченных связных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР имени А.А.Дородницына

На правах рукописи

ВОБЛЫЙ Виталий Антониевич

НЕКОТОРЫЕ ЗАДАЧИ . ПЕРЕЧИСЛЕНИЯ ПОМЕЧЕННЫХ СВЯЗНЫХ ГРАФОВ

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Москва - 2008

003460143

Работа выполнена в отделе математических проблем распознавания и методов комбинаторного анализа Вычислительного центра имени А.А.Дородницына РАН

Научный консультант:

Доктор физ.-мат. наук, профессор ЛЕОНТЬЕВ В.К.

Официальные оппоненты:

Доктор физ.-мат. наук, профессор САПОЖЕНКО A.A.

Доктор физ.-мат. наук, профессор ГОРДЕЕВ Э.Н.

Доктор физ.-мат. наук СМЕТАНИН Ю.Г.

Ведущая организация: Институт системного

программирования РАН

Защита состоится " c^c-ßf- 2009 г. в час.

на заседании диссертационного совета Д.002.017.02 при Вычислительном центре имени А.А.Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан JL&4- 2008 г.

Ученый секретарь диссертационного совета, д.ф.-м.н., профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как структурная химия и статистическая физика.

У истоков теории графов лежат работы А. Кэли по перечислению помеченных деревьев и связанных с ними химических структур, опубликованные в 1857-1889 гг. Однако только во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики и в том числе теории перечисления графов.

Обычно задачам перечисления помеченных графов уделяется мало внимания, так как они считаются более простыми по сравнению с непомеченным случаем [1]. Но в ряде физических задач, как например, в классической статистической механике используются именно помеченные графы [2-4], поэтому перечисление таких графов является актуальной задачей. Хотя теория перечисления помеченных связных графов развивается уже в течение 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о чем говорят работы зарубежных исследователей последних лет [5-9].

Комбинаторика находится в тесном взаимодействии с теорией вероятностей. Если на множестве исследуемых графов задано равномерное распределение вероятностей, то числовые характеристики этих графов можно рассматривать как случайные величины. Поэтому во многих случаях из решения перечислительной задачи теории графов можно вывести следствия, характеризующие свойства и структуру соответствующих случайных графов. Результаты перечисления помеченных графов применяются для их случайной генерации и анализа эффективности алгоритмов [6].

Цель работы. Перечисление некоторых классов помеченных связных графов, нахождение явных формул и соответст-

вующей асимптотики, а также упрощение ряда результатов в этой области, полученных другими исследователями.

Методы исследований. В работе использованы методы теории графов, комбинаторного анализа, теории функций комплексного переменного и теории специальных функций математической физики.

Научная новизна. Все основные результаты диссертации являются новыми.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты могут найти применение для генерации помеченных графов и анализа эффективности алгоритмов, а также в статистической физике.

Апробация работы. Основные результаты диссертации докладывались и обсуждались на семинаре отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра имени А.А.Дородницына РАН, а также были представлены на Международных конференциях «Вероятностные методы в дискретной математике» (Петрозаводск, 1988, 2000, 2004), на Международных семинарах «Дискретная математика и ее применения»(Москва, 2001, 2004,2007), на Всероссийских симпозиумах по прикладной и промышленной математике (Сочи, 2005, 2007).

Публикации. Материал диссертации опубликован в 8 статьях (все опубликованы в журналах из списка ВАК) и 8 тезисах докладов. Все статьи написаны без соавторов. В одной статье использованы идеи Г.Н. Багаева.

Структура и объем работы. Диссертация состоит из введения, 6 глав и списка литературы, содержащего 121 название. Общий объем диссертации 138 страниц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы и дается краткое содержание работы.

В первой главе исследуются помеченные связные графы с заданным числом вершин и точек сочленения. Обозначим через 5ти - число помеченных связных графов

с п вершинами, из которых т точки сочленения, а через

- соответствующую экспоненциальную производящую

г

'тп

функцию:

п = 2

со ^

Пусть Я(х,г) = ^8т(г)хт = -

п=2 П\

т

2

т = 0 л = 2

где Вп - число помеченных блоков с я вершинами. Очевидно, ~ ^(г). Йинг-Ли Джин и Селков нашли, что

8{{г) = г{ев'(г)-В\г)-1).

Кроме того, Селков [10] вывел следующее дифференциально-функциональное уравнение для :

55 „/ 55 „ . 55л

г--х— = гВ'

дг дх

г + хг--1- х(1 - х)

дг дх

V

и получил асимптотику для ^ при я -> °о и фиксированном т.

В работе из уравнения Селкова при т > 1 выведено обыкновенное дифференциальное уравнение для 5т(г):

25;, (2) - т5м (7) - ±-Ут (/а,, / • 2!Я2 ,..., >! а„,) , т\

где Ут(/ё\>—>/§т) - многочлены разбиений Белла и

/к=/к = 2к+хВ{ш\г), а^БЬЮ + ^г)-— 5,_,(г) .

г г

Как следствие получено выражение для 52(г)

Далее в работе найдено явное решение уравнения Селкова в виде формулы, содержащей энумератор помеченных блоков по числу вершин.

Ут"2)

т\

Затем дано комбинаторное доказательство этой формулы и получена следующая асимптотика для т = о(п) при п —» со

(п-т- 2)\

-(п-т)(п-т-\)

Во второй главе рассматриваются связные гомеоморфно несводимые графы. Сначала излагается метод сжатия-разжатия Багаева [11]. Суть метода состоит в следующем.

Для перечисления графов заданного вида в каждом графе выделяется порожденный подграф с определенными структурными свойствами, который сжимается в особую вершину. Образовавшиеся графы, содержащие фиксированную (особую) вершину с заданной степенью, а также сжатые подграфы независимо перечисляются известными методами перечисления. Перечисление исходных графов завершается суммированием по всем возможным степеням особой вершины произведений числа сжатых подграфов, числа графов, образовавшихся после сжатия, и числа способов восстановления (разжатия) исходного графа.

Как эпизод прием сжатия-разжатия графов встречается у Муна, а также у В.Н.Сачкова. В последнее время метод сжатия-разжатия находит применение за рубежом [5].

Обозначим через - число помеченных связных

графов с п вершинами, из которых к висячих, а р внутренних. Методом сжатия-разжатия для 0 <к <п- р, р> 3, доказана формула

где

— нецентральные числа Стерлинга второго рода, которые определяются с помощью производящей функции

Затем во второй главе перечисляются точно и асимптотически помеченные связные гомеоморфно несводимые разреженные графы.

Обозначим через - число помеченных простых

(связных) гомеоморфно несводимых графов с р вершинами и <7 ребрами, а через Н(х,у)(Н'{х,у)) - соответствующую экспоненциальную производящую функцию. Джексон и Рейли [12] вывели формулу

И(х,у) = XV« ^т- = О + *УГШ ехР

о'

р.ч и-

ху х2у2

/ С 1 Х\

(1 +дг)ехр уехр

V <\ + ху))

— X у 2__

1 + ху

Кроме того, в силу теоремы Гильберта, Н\х,у) = \пН(х,у) . Таким образом, задача перечисления помеченных связных гомеомофно несводимых графов в принципе была решена. Однако получение асимптотики из формул Джексона-Рейли представляется затруднительным. Поэтому в работе предложен другой подход к перечислению рассматриваемых разреженных графов.

Пусть У^(р,р + с}) — число помеченных гладких графов с р вершинами, из которых т - узлы, и {p + q) ребрами. Введем производящую функцию

оо р

гЫ

р=з р\

С помощью метода сжатия-разжатия выводится, что при ц > О

ю

производящая функция Шч{г) = '^1НС{р,п + (])— для числа

п-6 М-

НС(п,п + д) связных гомеоморфно несводимых графов с п помеченными вершинами и (п + ребрами удовлетворяет соотношению

где С(м?) — производящая функция чисел помеченных

корневых деревьев:

Л = 1

и!

Пусть нир(п) - число помеченных связных гомеоморфно

несводимых унициклических графов с п вершинами, из которых р циклических, тогда при п>2р , как следствие, получена формула

2 р /=р *= 1

/ „\

п-р-1

./-I

При фиксированном q, ц> 0, и доказана асимптотическая формула

/ \ "+-(5?-')

НС(п,п + д)~ Идп 2

1/, 1\"+

е -I

п —> 00

методом Дарбу

где

ч2/

5д

\ 1

+ 1

{5,-1)

2?

а й - коэффициенты

V 2 .

Степанова-Райта.

В третьей главе перечисляются помеченные связные графы с заданным количеством висячих вершин.

Рид [13] получил в виде разностного уравнения решение задачи перечисления помеченных связных графов с заданным числом висячих вершин. Райт [14] дал точные и асимптотические формулы для числа помеченных связных разреженных графов без висячих вершин.

Автором получено решение уравнения Рида в виде формулы, выражающей число помеченных связных графов с заданным коли-чеством висячих вершин через число таких графов без висячих вершин. Затем с помощью этой формулы и результатов Райта найдена асимптотика числа помеченных связных разреженных графов с заданным количеством висячих вершин .

Пусть Ср(п,к) - число помеченных связных графов с п вершинами, из которых к - висячие, ар - внутренние, то есть циклические или принадлежат простой цепи между циклами. Обозначим через Ур -Ср{р,0) - число помеченных связных графов с р вершинами, среди которых нет висячих. При любых р>3 и 0<к<п-р доказана формула

где Л" (О обобщенные числа Стерлинга 2-го рода по базе + . Так как числа Д['(р) совпадают с нецентральными числами Стерлинга второго рода 8р(п,к) , то эта формула совпадает с формулой, полученной во второй главе методом сжатия-разжатия.

Пусть с(п,п + д,к) - число помеченных связных графов с п вершинами и п + <7, ребрами, причем к вершин висячие. При фиксированных к > 0 , <7 >0 и п -> со с помощью теоремы Харди-Литтлвуда получена асимптотическая формула

с(п,п + Ч,к)= РкчпгМ"-Хп\(\ + о^)\

где /3. = (-} -^^- , а й- коэффициенты

** Ы к\(2к + 3Ч-\)\ф\ 4

Степанова-Райта.

Графом-гусеницей или колючим графом назовем граф, который становится гладким после однократного удаления висячих вершин вместе с инцидентными им ребрами. Пусть СС(п,п + д) - число помеченных графов-гусениц с п вершинами и п + д ребрами, тогда при фиксированном д>0 и п -> со получена асимптотическая формула

где Ь- 0.5671... -корень уравнения ге: = 1, а ¿ч -коэффициенты Степанова-Райта.

В четвертой главе находится асимптотика чисел, удовлетворяющих квадратичному разностному уравнению типа свертки, и рассматриваются ее приложения.

В работах многих авторов асимптотика числа помеченных связных разреженных графов выражается с помощью коэффициентов, задаваемых квадратичным рекуррентным соотношением. Эти коэффициенты названы Г.Н. Багаевым коэффициентами Степанова-Райта. Они определяются следующим образом

Райт нашел приближенное значение предела, к которому стремятся эти коэффициенты при п -> да , а Г.Н. Багаев и Е.Ф. Дмитриев без доказательства дали точное значение этого предела [15].

Автором при и -> да получена асимптотика: с1п ~\!2л . Кроме того, для коэффициентов Степанова - Райта выведено линейное разностное уравнение, а также найдены явные выражения в виде определителя и суммы по всем разбиениям номера коэффициента.

Коэффициенты Степанова-Райта называются за рубежом константами Райта и числами Райта-Лушара-Такача, они применяются также в теории броуновского блуждания [16] и теории хэширования [17].

Райт [18] выразил асимптотику числа помеченных блоков с помощью следующих чисел, которые назовем

коэффициентами Райта : и ПРИ к~2

выполнено

f k~x

2(к + l)bk+] = (3к + 2) kbk + 3 Y s{k - s)bsbk

( 1 \ JS K—S

\ S = 1 J

При n -> oo выведена асимптотическая формула

1

гъ\"

М) .

V^-y

2ле

Пусть д„ - число помеченных 3-связных кубических графов с 2п вершинами. Вормальд [19] получил формулу

_ (2/1)! Чп 3пГ г„ ,

где гг= 1 и при п> 2 верна рекуррентность

п-2

гп ={Ъп-2){гп_х+^гкгп-к .

к=2

Автором при и -> оо доказана асимптотика

е~2........ГЗ

<7„~ — (2я)!(я-1)!|д

Она совпадает с асимптотикой для цп, полученной Вормальдом другим путем.

В заключение рассматривается квадратичное разностное уравнение

п

а„+1 =(" + а)а„ + у£ ял.а„_л, и > 0, а0 = я .

.5 = 0

При п —> со и 2^и0 + а -1 > 0 найдена асимптотическая формула

а„=-(1 + о(1)) .

¿ГОаоХГО^о+а)

Как следствие этой общей формулы получается асимптотика для коэффициентов Степанова-Райта.

В пятой главе исследуются регулярные и бирегулярные графы . Пусть СРп , СМп и С„ - соответственно, число кубических псевдо-графов, число кубических мультиграфов и число простых кубических графов с 2п помеченными вершинами. Рид [20] получил формулы

СР =1Муу_(6/-2у)!6М,0)

6" ^о (3/ - 7)1(2/- ])\/.(п - 0148'

см = (-1)'(б/-2у)!б^,(;)

1=0

(3/-у)!(2/-у)!;!(«-/)!48'

С„

6" ^^(3|-;)!(2/-У)!/.(и-0!48'

И

где Ар{с?) = £-

¿0{Я-2к)\к\

В работе получены, интегральные представления 1

I 1

31

3 2 7 V 3/ — 1

Л,

3 2

( 1

+

3/

3/ + 1

ж,

1 00 /»"'

С помощью метода расщепления Егорычева вводятся числа

31

л

1-— 31

я„

V

I 1

31

3 2ДЗ/-1

с/г .

При этом Сп = Сп (2п). Затем найдена производящая функция

= —1

п=0т-0

п\ т\

I и 2у

~2~Т

ехр

2 2у Зи

--2У +--3

ЗУ 2

/

из которой методом Бендера [21] получена асимптотика при

п -»СО

С„

2л"«

- «I

п\(2п)\ .

Эта асимптотика совпадает с асимптотикой, полученной Ридом в его диссертации (доказательство не опубликовано).

Следуя Риду, назовем (р,я) - бирегулярным графом двудольный граф, у которого все вершины из 1 -й доли имеют степень р, а из 2-й доли - степень q. Рид получил для числа помеченных общих (допускаются петли и кратные ребра)

(р, ц) -регулярных графов выражение в виде скалярного произведения цикловых индексов композиций симметрических групп: N{Z(E,/l,/ll[S|,])*Z(Epn/h[Sí|])} .

Пусть число помеченных общих (2,к)-

бирегулярных графов с кп вершинами в 1-й доле и 2п вершинами во 2-й доле. Автором получено интегральное представление

где Нк (х) - многочлен Эрмита, а \ - мнимая единица . В качестве следствия найдены формулы

М2,=(2„Ж2„,!С"^) , 4(3) = (3">!;у)!С""0) ,

где Ь°(х) - многочлен Лагерра. Получена также общая формула

(2 кп)\

Ьв { 2'-' 2' 2 2 '2 ' ' - ' где - гипергеометрическая функция Лауричеллы п переменных 2-го рода. Из интегрального представления для методом Лапласа при фиксированном к и п —» оо найдена асимптотика

Пусть Мп(к)- число помеченных без кратных ребер (2,к)-бирегулярных графов с кп вершинами в 1-й доле и 2п вершинами во 2-й доле. Получено интегральное представление

М„(к)= , '[е",Я»"(т>/г

где Нк(х) - многочлен Эрмита. В качестве следствия получены формулы

О „ (3«)!(2и)!(2и)! 1/2_.1,/ 3

2

где L"(x) - многочлен Jlareppa.

Число остовных деревьев графа является важной характеристикой его надежности как сети для передачи информации. В химии число остовных деревьев молекулярного графа связано с физическими свойст-вами сложного соединения.

Пусть G - регулярный граф степени к с п вершинами, а T{G) - число его остовных деревьев. Для максимального

числа остовных деревьев графа G известна простая оценка Кельманса -Бигса:

T(G)<-п

пк

ч/1-l

V

Л,

Известна также точная оценка Маккея [22]:

т(с\< AXogn (г V гле ^ _ (¿"О*"'

Для числа остовных деревьев T(G) регулярного графа G степени к с п вершинами получена оценка сверху

f

7XG) ex р

2к +2к-\ -п

ч Ы j

, где с = е137/6°,

Эта оценка является при п °о , к -> ю в некотором смысле асимптотически точной для бесконечной последовательности регулярных графов. Кроме того, доказано, что для к ~ с,«" при п да , о < а < 1 , первые два члена асимптотического разложения для полученной оценки и оценки Маккея совпадают.

В шестой главе рассматриваются задачи перечисления карт. Комбинаторные карты имеют приложения в теоретической физике (дискретная квантовая гравитация)[23], а также в стереохимии. В работе упрощены некоторые формулы для числа карт на поверхностях, полученные

другими исследователями, и найдена соответствующая асимптотика. Выведены два комбинаторных тождества :

I

/=о

(п\ ( т ^ -1 гп

Л

п\Г

ш -2п +1

X

¡=о

'2Л

V ' /

1 + 1

-2"' =

2" Г

2п + 2 п +1

т>2п

-п-1

■1 , и>0

отсутствующие в известных сборниках таких тождеств. Пусть сп - число общих корневых кубических планарных карт (допускаются петли и кратные ребра) с 2п -1 некорневыми вершинами, п > 2. Лью [24] получил формулу:

_ у! 22"~'+1 (п + 1-1) (2п - / +1)

С помощью первого тождества формула для сп существенно

упрощена:

с„ =6-

3 п

8"Г(у) (п + 2)!гф

затем из нее при л->со с помощью формулы Стерлинга найдена асимптотика : сн 2(\2-Л)" .

Пусть /„(*) = |>„*", /г(х)=^их\ /,(*)=£*»*" -

// = 1 /7 = 2 /1 = 2

соответственно, производящие функции по числу ребер карты 1

для числа ~ - существенных карт на проективной плоскости,

1-существенных карт на торе и 1-существенных карт на бутылке Клейна. Хао, Каи и Лью [25] вывели следующие формулы:

Л ' йн (я + 1) Л (и-/)

„=0,=0 5! г! («-г) (и + 2) (« + 1) где Я, (и) = 50п1 - 8и(/ — 18)— /2 —21/ + 82 .

оо

Обозначим через /к (х) = ^Х*" - производящую функцию

н=2

по числу ребер карты для числа 2-существенных карт на бутылке Клейна. В. Лью и У. Лью [26] вывели формулу:

„4^5! /'! (и-/) (и+ 2) (л + 1) где ^(п)=60и2 -16га-2/2 + 168 л-42/+ 84 .

С помощью второго полученного тождества существенно упрощены формулы для р„ , /„ , кп и кп :

л 9- 2П~Х Рп= 2 -

п

, ^ 1 (2")! к - 1 (5и-2)(2Я)! п22я.} " 12(л-2)!и! ' " 12 (и-1)!и!

- (2„)! " 2(и-1)!(и-1)!

Кроме того из этих формул найдена асимптотика числа рассматриваемых карт при п оо .

1 - 5 - - 1

П ~22"-1 I п1?2" к п2?2" к и2?2"

Рп z 5 'н ' Г~ ' " ~ ¡—П А

12л/л- 12л/Л" 2л/л-

Большинство перечислительных задач, связанных с раскрасками графов, относятся к числу нерешенных задач. Однако еще Татт при исследовании хроматических сумм корневых планарных триангуляций нашел, что их энумерант является предельным случаем ( при А-оо ) производящей функции хроматических сумм. Эту связь использовали также Ли и Лью для перечисления общих простых карт на плоскости [27]. Поскольку коэффициентами в хроматических суммах графов

служат их хроматические многочлены, важно исследовать условия хроматичности многочлена.

Пусть Р(0,Х) = '^а]Х - хроматический многочлен связного

7=0

графа Сер помеченными вершинами. Автором доказано, что для любого 7=1,...,/? выполняется неравенство:

I' (к-\"

Кроме того, для любого у = 1,...,р выполняется неравенство:

¿=1 Гр + \^

ак >0.

,! = 1

Полученные необходимые условия хроматичности многочлена в ряде случаев оказываются сильнее уже известных условий Котляра и Хватала.

Основные результаты диссертации

1. Найдена явная формула для энумератора помеченных связных графов по числу вершин с заданным количеством точек сочленения. Получена асимптотика для числа помеченных связных графов с большим количеством вершин и большим количеством точек сочленения.

2. Выведена формула для энумератора помеченных связных гомеоморфно несводимых графов по числу вершин с заданным цикломатическим числом. Получена асимптотика для числа помеченных связных разреженных гомеоморфно несводимых графов с большим количеством вершин и фиксированным цикломатическим числом.

3. Выведена асимптотика для числа помеченных связных разреженных графов с большим числом вершин и фиксированным количеством висячих вершин.

4. Получена асимптотика чисел, удовлетворяющих квадратичному разностному уравнению типа свертки. Найдены предельные значения для коэффициентов Райта и Степанова-Райта.

5. Найдены интегральные представления и асимптотика для числа помеченных кубических графов. Выведены явные формулы для числа помеченных (2,к) -бирегулярных графов.

6. Выведены два комбинаторных тождества, с помощью которых упрощены некоторые формулы для числа карт на поверхностях и получена соответствующая асимптотика для карт с большим количеством вершин или ребер.

ЛИТЕРАТУРА

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

2. Иванчик И.И. Проблемы теории графов в статистической физике. Труды ФИАН, т. 106. М.: Наука, 1979, с. 3-89.

3. Калмыков Г.И. Древесная классификация помеченных графов. М.: Физматлит, 2003.

4. Калмыков Г.И. Каркасная классификация помеченных графов. М.: Научный мир, 2006.

5. Ravelomanana V., Thimonier L. Enumeration of the first multicyclic isomorphism-free labelled graphs. Proc. 13th internat. conf. on Formal Power Series and Algebraic Combinatorics (FPSAC01), 2001,411-420.

6. Bodirsky M., Gropl C., Kang M. Generating labeled planar graphs uniformly at random. In ICALP 2003, pp. 1095-1107, Springer, Berlin, 2003.

7. Flajolet P., Salvy В., Schaeffer G. Airy phenomena and analitic combinatorics of connected graphs. Electron. J. Combin. 11(2004), #34.

8. Leroux P. Enumerative problems inspired by Mayer's theory of cluster integrals . Electron. J. Combin. 11(2004), #32.

9. Chae G.-B., Palmer E.M., Robinson R.W. Computing the number of labeled general cubic graphs. Discrete Math. 307(2007), 2979-2992.

10. Selkow S.M. The enumeration of labeled graphs by number of cutpoints. Discrete Math. (1998), 185, 183-191.

11. Багаев Г.Н., Воблый B.A. Метод сжатия-разжатия для перечисления графов. - Дискретная математика, т. 10, вып. 4, 1998, с. 82-87.

12. Jackson D.M., Reilly J.W. The enumeration of homeomorphically irreducible labeled graphs. J. Combin. Theory(B), 19(1975), 272-286.

13 Read R.C. Some unusual enumeration problems. - Ann. N.-Y. Acad. Sci., 1970, V. 175, Art. 1, 314-326.

14. Wright E.M. Enumeration of smooth labelled graphs. Proc. Roy. Soc. Edinburgh, 1981. A91, N 3/4, 205-212.

15. Багаев Г. H., Дмитриев Е. Ф. Перечисление связных двуцветных графов. Комбинаторный анализ (1983), вып. 6, 58-64.

16. Janson S. Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas. Probability Surveys, 4(2007), 80-145.

17. Flajolet P., Poblete P., Viola A. On the analysis of linear probing hashing. Algorithmica 22(1998), 490-515.

18. Wright E.M. The number of connected sparsely edged graphs. IV . J. Graph Theory. 1983. V. 7. N 2. P. 219-229.

19. Wormald N.C. Enumeration of labelled graphs II: Cubic graphs with given connectivity. J. London Math. Soc. (2), 20(1979), 1-7.

20. Read R.C. The enumeration of locally restricted graphs. I J.London Math Soc., 1959. v. 34, 417-436.

21. Bender E.A. An asymptotic expansion for the coefficients of some formal power series // J. London Math. Soc. (2). 1975. V. 9. 451-458.

22. McKay B.D. Spanning trees in regular graphs. Europ. J. Combinatorics, 4(1983), 149-160.

23. Malyshev V.A. Combinatorics and probability of maps.

In Asymptotic combinatotics with application to mathematical physics, Dordrecht a.o., Kluwer, 2002, 71-95.

24. Liu Y.P. A note on the number of cubic planar maps, Acta Mathematica Scintia, 12(1992), 282-285.

25. Hao R., Cai Y., Liu Y. Counting g-essential maps on surfaces with small genera. - Korean J. Comput. and Appl. Math., v. 9 (2002), №2, 451-463.

26. Liu W., Liu Y. Enumeration of three kinds of rooted maps on the Klein bootle. J. Appl. Math. & Computing 24(2007), 411-419.

27. Li Z., Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223-237.

Публикации по теме диссертации

1. Воблый В. А. Асимптотическое перечисление помеченных связных разреженных графов с заданным числом висячих вершин . - Дискретный анализ , Новосибирск, 1985. вып. 42,

с. 3-14.

2. Воблый В.А. О коэффициентах Райта и Степанова-Райта. -Матем. заметки, т. 42, вып. 6, 1987, с. 854-862.

3. Воблый В.А. О вероятности появления графа-гусеницы среди случайных разреженных графов. - Вероятностные методы в дискретной математике, Петрозаводск, 1988, с. 25-26.

4. Воблый В. А. О перечислении помеченных связных гомео-морфно несводимых графов. - Матем. заметки 49(1991), №3,

с. 12-22.

5. Багаев Г.Н., Воблый В.А. Метод сжатия-разжатия для перечисления графов. - Дискретная математика, т. 10, вып. 4, 1998, с. 82-87.

6. Воблый В.А. Асимптотика числа общих кубических графов с помеченными вершинами и ребрами - Обозрение прикладной и промышленной математ., 2000, т. 7, вып. 1, с. 92

7. Воблый В.А. Некоторые необходимые условия хроматичности многочлена. Дискретная математика, т. 13, вып. 1, 2001, с. 73-77. Исправление опечаток: Дискретная математика, т. 13, вып. 2, с. 159.

8. Воблый В.А. О перечислении помеченных (2,4) -бирегулярных графов - Материалы VII Международного семинара «Дискретная математика и ее приложения», М., МГУ, ч. II, 2001, с. 212.

9. Воблый В.А. Интегральное представление и асимптотика для числа помеченных общих (2, к) - бирегулярных графов -Материалы VIII Международного семинара «Дискретная математика и ее приложения», М., МГУ, 2004, с. 329-330.

10. Воблый В.А. Упрощение формул для числа g-cyщe-ственных карт на поверхностях с малым родом. - Обозрение прикладной и промышленной математики, 2004, т.11, вып. 2, с. 236-237.

11 . Воблый В.А. Асимптотика числа кубических планарных карт. - Обозрение прикладной и промышленной математики, 2005, т. 12, вып. 4, с. 850-851.

12. Воблый В.А. Решение уравнения Селкова для энумератора помеченных связных графов по числу точек сочленения. -Материалы IX Международного семинара «Дискретная математика и ее приложения», М., МГУ, 2007, с. 265-268.

13. Воблый В.А. Упрощение некоторых формул для числа карт на поверхностях. - Математические заметки, т.83, вып.1, 2008, с. 14-23.

14. Воблый В.А. О перечислении помеченных связных графов по числу точек сочленения. Дискретная математика, т.20, вып.1, 2008, с. 52-63.

15. Воблый В.А. Асимптотика числа помеченных 3-связных графов. - Обозрение прикладной и промышленной математики, 2008, т. 15, вып.2, с.237.

16. Воблый В.А. Простая верхняя оценка для числа остовных деревьев регулярных графов. Дискретная математика, т.20, вып.З, 2008 , с. 47-50.

Воблый Виталий Антониевич Некоторые задачи перечисления помеченных связных графов

Подписано в печать 06.11.2008

Формат бумаги 60x84 1/16 Уч.-изд.л. 1. Усл.-печ. л. 1,5 Тираж 100 экз. Заказ 32

Отпечатано на ротапринтах в Вычислительном центре им. A.A. Дородницына Российской академии наук 119333, Москва, ул. Вавилова, 40

ВВЕДЕНИЕ.

ГЛАВА I. Графы с заданным числом точек сочленения

§ 1. Решение уравнения Селкова.

§2. Комбинаторный вывод формулы для производящей функции.

§3. Асимптотика для числа графов с большим количеством вершин.

ГЛАВА II. Гомеоморфно несводимые графы

§ 1. Метод сжатия-разжатия.

§2. Разреженные гомеоморфно несводимые графы.

ГЛАВА III. Графы с заданным количеством висячих вершин

§ 1. Перечисление по числу вершин и ребер.

§2. Асимптотика.

§3. Графы-гусеницы.

ГЛАВА IV. Асимптотика решения квадратичного разностного уравнения и ее применение.

§1. Связные разреженные графы и блоки.

§2. 3-связные кубические графы.

§3. Общее квадратичное разностное уравнение.

ГЛАВА V. Регулярные графы.

§ 1. Кубические графы.

§2. (2, к) - бирегулярные графы.

§3. Максимальное число, остовов регулярных графов.

ГЛАВА VI. Асимптотика числа карт.

§ 1. Общие кубические планарные карты.

§2. g - существенные карты на поверхностях с малым родом.

§3. Эйлеровы карты на проективной плоскости.

§4. Условия хроматичности многочлена.

Важным разделом теории графов является теория их перечисления, имеющая многочисленные приложения не только в математической кибернетике, но и в таких областях естествознания, как например, структурная химия и статистическая физика [30]. У истоков теории графов лежат работы А. Кэли по перечислению помеченных деревьев и связанных с ними химических структур, опубликованные в 1857-1889 гг. Однако только во второй половине двадцатого столетия бурный прогресс вычислительной техники и кибернетики обусловил интенсивное развитие всей дискретной математики и в том числе теории перечисления графов.

Комбинаторика тесно связана с теорией вероятностей. В настоящее время теория вероятностей далеко ушла от своих комбинаторных истоков, превратившись в могучую математическую реку со своим мощным аппаратом исследования. Однако «комбинаторные ключи» постоянно подпитывают эту реку. Во многих работах по теории случайных графов используются комбинаторные построения [22, 52,66].

Если на множестве исследуемых графов задано равномерное распределение вероятностей, то числовые характеристики этих графов можно рассматривать как случайные величины и анализировать их с помощью хорошо развитого аппарата теории вероятностей . Однако возможен и другой подход, когда, как в начале развития теории вероятностей , с помощью комбинаторики получаются утверждения для случайных графов. Во многих случаях из решения перечислительной задачи теории графов можно вывести следствия, характеризующие свойства и структуру соответствующих случайных графов.

Перечисление помеченных графов необходимо при непосредственном перечислении непомеченных графов с помощью леммы Бернсайда [26], а также используется для получения асимптотики непомеченных графов [105]. Результаты перечисления помеченных графов применяются для их случайной генерации и анализа эффективности алгоритмов^].

Хотя теория перечисления помеченных связных графов интенсивно развивается уже в течение 50 лет, интерес к этой области перечислительной комбинаторики не пропал, о чем говорят многочисленные работы зарубежных исследователей последних лет [58, 70, 82, 54, 59].

Помеченные графы используются в ряде физических задач [17-20] и поэтому перечисление таких графов является актуальной задачей.

Диссертация состоит из введения, шести глав и списка литературы. Ссылки в тексте за пределами главы содержат в качестве первого индекса номер главы, а второй индекс - номер утверждения или формулы. Ссылки внутри главы содержат только номер утверждения (формулы).

1. Багаев Г. Н. Случайные графы со степенью связности 2. Дискретный анализ (1973) 22, 3-14.

2. Багаев Г. Н. Предельные распределения метрических характеристик случайного неразложимого отображения. Комбинаторный и асимптотический анализ. КГУ, Красноярск, 1977, 55-61.

3. Багаев Г. Н., Дмитриев Е. Ф. Перечисление связных двуцветных графов. Комбинаторный анализ (1983) 6, 58—64.

4. Багаев Г. Н. Распределение числа вершин в слоях случайного многоцветного дерева. Вероятностные процессы и их прилоэюения. МИЭМ, Москва, 1984, 12-16.

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

6. Багаев Г.Н., К перечислению связных гиперграфов. Комбинаторный анализ, (1980), вып. 5, 59-61.

7. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции, т. 1, М: Наука, ГРФМЛ, 1965.

8. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции, т. 2, М: Наука, ГРФМЛ, 1966.

9. Бендер Э.А. Асимптотические методы в теории перечислений. Перечислительные задачи комбинаторного анализа. М., Мир, 1979,с. 266-310.

10. Гельфонд А.О. Исчисление конечных разностей. М.: Наука, 1967.

11. Градштейн И.С., Рыжик И. М. Таблицы интегралов, сумм, рядов, произведений. М.: Наука, 1971.

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

13. Дмитриев Е. Ф. Перечисление отмеченных связных и гладких гомеоморфных графов. Деп. ВИНИТИ 8.07.85 4957-85, 10 стр.

14. Евграфов М.А. Аналитические функции. М.: Наука, 1968.

15. Егорычев Г.П., Интегральное представление и вычисление комбинаторных сумм. Наука, Новосибирск . 1977.

16. Зайцев В.Ф., Полянин А.Д. Справочник по нелинейным дифференциальным уравнениям. Наука, М., 1993.

17. Иванчик И.И. О бесповторном перечислении связных помеченных графов. Сб. Комбинаторный анализ, вып. 4, М.: Изд-во МГУ, 1976, 78—87.

18. Иванчик И.И. Проблемы теории графов в статистической физике. Труды ФИАН, т. 106. М.: Наука, 1979, 3-89.

19. Калмыков Г.И. Древесная классификация помеченных графов. М.: Физматлит, 2003.

20. Калмыков Г.И. Каркасная классификация помеченных графов. М.: Научный мир, 2006.

21. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М.: Наука, 1971. <

22. Колчин В.Ф. Случайные графы. М.: Физматлит, 2000.

23. Котляр Б.Д. Об одном необходимом условии хроматичности многочлена— Кибернетика и системный анализ, 1998, № 5, 176-178.

24. Лаврентьев М.А., Шабат Б.В. Методы теории функций комплексного переменного. М.: Физматлит, 1965.

25. Леонтьев В.К. Избранные задачи комбинаторного анализа. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.

26. Лисковец В.А. Некоторые результаты комбинаторной теории перечисления графов. I. В сб.: Комбинаторный и асимптотический анализ, Красноярск, Издат. Красноярского университета, 1975, с. 9-36.

27. Лямин В.Н., Селиванов Б.И. Гипердеревья с заданным числом концевых вершин и ребер. Комбинаторный анализ, (1974), вып. 3, 68-71.

28. Маренич A.C. Решения уравнения w = -exp(z + w) , их свойства и применения. Вычислительная математика и математическая физика. М.:, 1985, 32-42.

29. Медведев Ю.И., Ивченко Г.И. Асимптотическое представление конечных разностей от степенной функции в произвольной точке. -Теория вероятностей и ее применения, 1965, т. 10, №1, 151-156.

30. О некоторых тенденциях теории перечисления. Гаврилов Г.П., Лисковец В.А., Пермяков П.П., Селиванов Б.И. В сб.: Перечислительные задачи комбинаторного анализа, Мир, М., 1979, с. 336-362.

31. Олвер Ф. Введение в асимптотические методы и специальные функции-М.: Наука, 1978. «

32. Ope О. Теория графов. М, Наука, 1968.

33. Платонов М.Л. Комбинаторные числа класса отображений и их приложения. М.: Наука, 1979.

34. Прудников А.П. и др. Интегралы и ряды, т. 1. -М: Наука ГРФМЛ, 1981.

35. Прудников А.П. и др. Интегралы и ряды, т. 2. -М: Наука ГРФМЛ, 1983.

36. Прудников А.П. и др. Интегралы и ряды, т. 3. -М: Наука ГРФМЛ,1986.

37. Риордан Дж., Введение в комбинаторный анализ. ИЛ, М. 1963.

38. Риордан Дж., Комбинаторные тождества. Наука, ГРФМЛ, М. 1982.

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

40. Степанов В.Е. Несколько теорем относительно случайных графов. Вероятностные методы в дискретной математике. Петрозаводск, 1983, с. 90-92.

41. Уиттекер Э.Т., Ватсон Дж. Курс современного анализа, т. 1, ГИФМЛ, М.: 1963.

42. Федорюк М.В. Метод перевала. Наука. ГРФМЛ, М., 1977.

43. Харари Ф., Палмер Э. Перечисление графов. Мир, М., 1979.

44. Цветкович Д., Дуб М., Захс X. Спектры графов. Теория и применение. Киев, Наукова думка, 1984.

45. Adam A. A., Broere J. Chromatic polynomials of graphs in terms of trees. J. Math. Phys. Sci. 27(1993), 231-240.

46. Bender E.A. Central and local limits theorems applied to asymptotic enumeration. J. Combin. Theory, A15(1973), 91-111.

47. Bender E.A. An asymptotic expansion for the coefficients of some formal power series // J. London Math. Soc. (2). 1975. V. 9. 451-458.

48. Bender E.A., Richmond L.B. Central and local limits theorems applied to asymptotic enumeration II. Multivariate generating functions. J. Combin. Theory, A34(1983), 255-265.

49. Bender E.A., Richmond L.B. An asymptotic expansion for the coefficients of some power series. II // Discrete Math. 1984. V. 50, N2/3, 135-141.

50. Biggs N. Algebraic graph theory. London, Cambridge univ. press, 1974.

51. Bodirsky M., Gropl C., Kang M. Generating labeled planar graphs uniformly at random, in ICALP 2003, pp. 1095-1107, Springer, Berlin, 2003.

52. Bollobas B. Random graphs, London a.o., Academic Press, 1985.

53. Brown T.J.N., Mallion R.B., Pollak P., Roth A. Some methods for counting in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Appl. Math. 67(1996), 51-66.

54. Chae G.-B., Palmer E.M., Robinson R.W. Computing the number of labeled general cubic graphs. Discrete Math. 307(2007), 2979-2992.

55. Comtet L. Analyse combinatoire. I. Paris: Presses Universitaires de France, 1970.

56. Fan Chung, Yau S.-T. Coverings, heat kernels and spanning trees. Electronic J. Combin. 6(1999), #R12.

57. Flajolet P., Poblete P., Viola A. On the analysis of linear probing hashing. Algorithmica 22(1998), 490-515.

58. Flajolet P., Salvy B., Schaeffer G. Airy phenomena and analitic combinatorics of connected graphs. Electron. J. Combin. 11(2004), #34.

59. Flajolet Ph.,Sedgewick R. Analytic combinatorics, Web edition, 2008.

60. Ford G.W., Uhlenbeck G.E., Combinatorial problems in the theory of graphs. I. Proc. Nat. Acad. Sci. USA, (1956), 42, 122-128.

61. Gould H.W. Combinatorial identities. Morgantown, West Wirg. Univ., 1972.

62. Hao R., Cai Y., Liu Y. Counting g-essential maps on surfaces with small genera. Korean . J. Comput. and Appl. Math., v. 9 (2002), №2, 451-463.

63. Harary F., Manvel B. On the number of cycles in graph. Matematicky casopis, 1971, v. 21, No.l, 55-63.

64. Harary F., Schwenk A J. The number of caterpillars. Discrete Math. 6(1973), №4, 359-365.

65. Jakobson D., Rivin I. On some extremal problems in graph theory. Preprint, arXiv:math/9907050vl math.CO. 8 Jul 1999.

66. Janson S., Luczak T., Rucinski A. Random graphs, N.Y. a.o., Wiley,2000.

67. Janson S. Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas. Probability Surveys, 4(2007), 80-145.

68. Jin Y.-L., Tazawa S., Shirakura T. Enumeration of connected graphs with cut vertices. J. Statistical Planning and Inference 106(2002), 409-418.

69. Koutras M. Non-central Stirling; numbers and some applications. Discrete Math. 42(1982), 73-89.

70. Leroux P. Enumerative problems inspired by Mayer's theory of cluster integrals . Electron. J. Combin. 11(2004), #32.

71. Lewis R.P. The number of spanning trees of a complete multipartite graphs. Discrete Math., 197/198(1999), 537-541.

72. Li Z., Liu Y. Chromatic sums of general simple maps on the plane. Utilitas Math. 68(2005), 223-237. •

73. Linial N. Graph coloring and monotone functions on posets. Discrete Math. 58(1986), 97-98.

74. Liu W., Liu Y. Enumeration of three kinds of rooted maps on the Klein bootle. J. Appl. Math. & Computing 24(2007), 411-419.

75. Liu Y.P. A note on the number of cubic planar maps, Acta Mathematica Scintia, 12(1992), 282-285.

76. Lord R.D. Some integrals involving Hermite polynomials // J. London Math Soc., 1949. v. 24, part 2, № 94, 101-112.

77. McKay B.D. Spanning trees in regular graphs. Europ. J. Combinatorics, 4(1983), 149-160. .-мок

78. Meir A., Moon J.W. On nodes of degree two in random trees. Mathematika, 15(1968), 188-192. . v ,

79. Moon J.W. Counting labeled trees. In: Graph Theory and Theoretical Physics. Academic Press. N.Y., 1967, 261-267.

80. Moon J.W. A problem on random trees. J. Comb. Theory (1971) 10, №3, 201-205.

81. Myrvold W. Reliable network synthesis: some recent developments. Proc. 8th international confer, on graph theory, combinatorics, algorithms and applications, 1999, v.2, p. 650-660.

82. Pittel В., Wormald N.C. Counting connected graphs inside-out. -J. Combin. Theory, ser. B, 93(2005), №2 , 127-172.

83. Ravelomanana V., Thimonier L. Enumeration of the first multicyclic isomorphism-free labelled graphs. Proc. 13th internat. conf. on Formal Power Series and Algebraic Combinatorics (FPSAC01), 2001, 411-420.

84. Read R.C. The enumeration of locally restricted graphs. I // J. London Math Soc., 1959. v. 34, 417-436.

85. Read R.C. An introduction to chromatic polynomials. J. Combin. Theoiy, 4(1968), 52-71.

86. Read R.C. Some unusual enumeration problems. Ann. N.-Y. Acad. Sci.,1970, V. 175, Art. 1,314-326.

87. Ren H., Liu Y. Counting rooted eulerian maps on the projective plane. -Acta Mathematica Scintia, 20B (2) (2000), 169-174.

88. Selkow S.M. The enumeration of labeled graphs by number of cutpoints. Discrete Math. (1998), 185, 183-191.

89. Tan Z., Gao S., Niederhausen H. Enumeration of (0,l)-matrices with constant row and column sums. Appl. Math. J. Chinese Univ. Ser. B, 21(4)(2006), 479-486.

90. Tutte W.T. Chromatic sums for rooted planar triangulations. IV. The case /1 = oo . Canad. J. Math., 25(1979), 929-940.

91. WilfH.B. Which polynomials are chromatic? Colloq. Internaz. Sulle Teorie Combinatorie, Rome, 1976, 247-256.

92. Vukicevic D. Thorny graphs. I. Valence connectivities. MATCH Commun. Math.Comput.Chem., 55(2006), 73-82.

93. Wormald N.C. Enumeration of labelled graphs II: Cubic graphs with given connectivity. J. London Math. Soc. (2), 20(1979), 1-7.

94. Wormald N.C. The asymptotic connectivity of labelled regular graphs. J. Combin. Theory, Ser. B, 31(1981), 156-187.

95. Wright E.M., A relationship between two sequences. Proc. London Math. Soc.,(3), (1967), 17, 296-304.

96. Wright E.M., The number of connected sparsely edged graphs. J. Graph Theory, 1(1977),' 317-330.

97. Wright E.M., The number of connected sparsely edged graphs. II. Smooth graphs and blocks. J. Graph Theory, 2(1978), 299-305.

98. Wright E.M. The number of connected sparsely edged graphs. Ill. J. Graph Theory. 1980. V. 4. N 4. P. 393-407.

99. Wright E.M. The number of connected sparsely edged graphs. IV . J. Graph Theory. 1983. V. 7. N 2. P. 219-229.i iii

100. Wright E.M. Enumeration of smooth labelled graphs. // Proc. Roy. Soc. Edinburgh, 1981. A91, N 3/4, 205-212.

101. Wright E.M. A quadratic recurrence of Faltung type. Math. Proc. Camb. Phil. Soc. 88(1980), 193.

102. Xiao-Dong Zhang A new bound for the complexity of a graph. Utilitas Mathematica 67(2005), 201-203.

103. Yang Ling-ling, Li Song-chen, Enumeration of special kind of labeled connected graphs. Trans. Tianjin Univ. (2004), 10, 233-235.

104. Ying-Lie Jin, Enumeration of labeled connected graphs and Euler graphs with only one cut vertex. Yokohama Math. J. (1997), 45, 125-134.

105. Воблый B.A. Асимптотическое перечисление графов некоторых типов. Дис. к.ф.-м.н. М., ВЦАН, 1985.

106. Воблый В. А. Асимптотическое перечисление помеченных связных разреженных графов с заданным числом висячих вершин . — Дискретный анализ, Новосибирск, 1985. Вып. 42, 3—14. Исправление опечатки: Дискретный анализ, вып. 44, с. 71.

107. Воблый В.А. О коэффициентах Райта и Степанова-Райта. Матем. заметки, т. 42, вып. 6, 1987, 854-862.

108. Воблый В.А. О вероятности появления графа-гусеницы среди случайных разреженных графов, т- Вероятностные методы в дискретной математике, Петрозаводск, 1988, с. 25-26.

109. Воблый В. А. О перечислении помеченных связных гомеоморфно несводимых графов. Матем. заметки 49(1991), №3, 12-22.

110. Багаев Г.Н., Воблый В.А. Метод сжатия-разжатия для перечисления графов. Дискретная математика, т. 10, вып. 4, 1998, с. 82-87.

111. Воблый В.А. Асимптотика числа общих кубических графов с помеченными вершинами и. ребрами Обозрение прикладной и промышленной математ., 2000, т. 7, вып. 1, с. 92 .

112. Воблый В.А. О перечислений" помеченных (2,4) бирегулярных графов - Материалы VII Международного семинара «Дискретная математика и ее приложения», М., МГУ, ч. II, 2001, с. 212.

113. Воблый В.А. Некоторые необходимые условия хроматичности многочлена. Дискретная математика, т. 13, вып. 1, 2001, 73-77. Исправление опечаток: Дискретная математика, т. 13, вып. 2, 159.

114. Воблый В.А. Интегральное представление и асимптотика для числа помеченных общих (2,к) бирегулярных графов - Материалы VIII Между-народного семинара «Дискретная математика и ее приложения», М., МГУ, 2004, с. 329-330.

115. Воблый В.А. Упрощение формул для числа g-существенных карт на поверхностях с малым родом. Обозрение прикладной и промышленной математики, 2004, т.11, вып. 2, 236-237.

116. Воблый В.А. Асимптотика числа кубических планарных карт. -Обозрение прикладной и промышленной математики, 2005, т. 12, вып. 4, 850-851.

117. Воблый В.А. Решение уравнения Селкова для энумератора помеченных связных графов по числу точек сочленения. Материалы IX Международного семинара «Дискретная математика и ее приложения», М., МГУ, 2007, 265-268.

118. Воблый В.А. Упрощение некоторых формул для числа карт на поверхностях. Математические заметки, т.83, вып.1, 2008, 14-23.

119. Воблый В.А. О перечислении помеченных связных графов по числу точек сочленения. Дискретная математика, т.20, вып.1, 2008, 52-63.

120. Воблый В.А. Асимптотика числа помеченных 3-связных графов. -Обозрение прикладной и промышленной математики, 2008, т. 15, вып.2, 237.

121. Воблый В.А. Простая верхняя оценка для числа остовных деревьев регулярных графов. Дискретная математика, т. 20, вып. 3, 2008 , 1-4.