Оценки числа независимых множеств в графах из некоторых классов

• Автор: Дайняк, Александр Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 98 с. : ил.

Оглавление
Введение

Глава 1. Оценки числа независимых множеств в деревьях фиксированного диаметра

1.1 Основные понятия

1.2 Число независимых множеств в деревьях диаметра

1.3 Структура (п, (1)-минимальных деревьев

1.4 Радиально регулярные деревья

1.5 Асимптотика числа независимых множеств в полных д-арных

деревьях
Глава 2. Оценки числа максимальных независимых множеств в графах фиксированного диаметра

2.1 Основные понятия

2.2 Нижние оценки числа максимальных независимых множеств
в графах фиксированного диаметра
2.3 Верхние оценки числа максимальных независимых множеств
в деревьях фиксированного диаметра
Глава 3. Оценки числа независимых множеств в графах с фиксированным числом независимости
3.1 Верхняя оценка числа независимых множеств в классе всех
графов с заданным числом независимости

3.2 Верхние оценки числа независимых множеств в лесах с заданным числом независимости
3.3 Соотношения между числом независимости и количеством независимых множеств в регулярных графах
3.4 Число независимых множеств в квазирегулярных двудольных графах
Приложение А
Список литературы

Введение
Важную роль в комбинаторике с момента её возникновения играют перечислительные задачи, связанные с подсчётом числа объектов, обладающих заданными свойствами. Примерами задач такого рода являются проблемы оценки количества целочисленных решений системы линейных неравенств, числа изомеров химических соединений, количества графов с теми или иными свойствами. Другим важным классом комбинаторных задач являются экстремальные задачи, связанные с описанием структуры объектов из заданного класса, максимизирующих или минимизирующих некоторый параметр. В качестве примера можно привести знаменитую теорему Турина о наибольшем числе рёбер в графе, не содержащем клик заданного размера. В диссертации решаются задачи, лежащие на стыке двух указанных областей комбинаторики. Доказываются верхние и нижние оценки числа независимых множеств (то есть подмножеств попарно не смежных вершин) в графах из различных классов, и описывается структура графов, на которых достигаются полученные оценки.
История вопроса
Задача перечисления независимых множеств в графах рассматривается с середины прошлого века и успела стать одним из классических разделов теории графов. Эта задача находит приложения не только непосредственно в математике (комбинаторная теория чисел [17, 21], теория кодирова-

вершинах, где п" 5= 2кп, выполнены соотношения
С(Т'") 1 ,
> 1 + 1п

Х~пГп
<т-') +

1 / 2те' — 2Аш — 4 , ,,9 Д
> 1 + -—р- 1п г - 2е_/(2г) >
2 + кп п'п )
> 1 + 1 (12("; ~ Ьг ~ 2) _ П
2 + кп I 25я/ 10) 100кп'

Утверждение 6. Пусть натуральные числа а, Ь, х, у удовлетворяют неравенствам а, Ь М, х, у N и а1х > Ъ1!у. Тогда > 1 + Мщ2м)К
Доказательство. Имеем
аДх ( ау/х-Ь1/у ау/х
= 1 + : > 1 +

ь1/у
Возможны два случая:
1. аУ/'х е N. Тогда, поскольку ау/х > Ь, из (8) следует, что

ЪЧу > 1 + уЪ > 1 + ЛШ'
2. ау!х N. Положим р = ау/х — ау!х . Тогда

N3 (МГ =Ё(1)1
I—п
,у/х

ау/х

г,У/х

Отсюда, и из неравенств 0 < р < 1 следует, что

> Л 7 Г" >
{аУ/х + Т)х 2х аУ'

Используя (8) и (9), получаем
а1/ж Л Р Л 1
, . , > 1 4
Ь !у
уЬ 2 хаУуЬ МЫ{2М)М