Исследование хроматического числа и размера максимальной клики графа

• Автор: Просолупов, Евгений Викторович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Санкт-Петербург
• Количество страниц: 128 с. : ил.

0.1 Базовые понятия и обозначения

0.2 Функции из интервала [а(С), х((7)]

0.3 Обзор данной работы

1 О функциях интервала [а((?),х(<7)]

1.1 Свойства системы функций интервала [а(С?),х((7)]

1.2 О разрыве между <1(0) и х(С)

1.2.1 Введение

1.2.2 Пример графа, для которого а((7) = < х(С)

1.2.3 Обобщение примера

1.3 О разрыве между г+((7) и х(С?)

1.4 Новые функции интервала [а(С),х(С)|

1.4.1 О целочисленном ортонормальном помечивании графа
1.4.2 Об е-ортонормальном помечивании графа
1.4.3 Оценка числа вершинной независимости через минимальную размерность е-ортонормального помечивания
2 Свойства трех операций над графом
2.1 Определения и основные свойства
2.1.1 Определения операций
2.1.2 Матрица смежности Ахроматического графа
2.2 Оценки значений инвариантов графа при применении
операций орД), ор2() и орз()
2.2.1 Размер максимальной клики и хроматическое число

2.2.2 Число вершинной независимости и число кликового
покрытия
3 Об универсальных ^-раскрашиваемых графах
3.1 Свойства тензорных степеней матриц Т1,Т2,Тз
3.1.1 Последовательность {Т®*}
3.1.2 Последовательность {Т®^}
3.1.3 Последовательность {Т®*}
3.2 Универсальные графы на классе двудольных графов
3.3 Случай произвольного хроматического числа
3.4 Обобщение результата об универсальности для операции
дублирования вершин графа
Заключение
4.1 Итоги и направления дальнейших исследований
4.2 Благодарности
Литература

Введение 0.1 Базовые понятия и обозначения
Данная работа посвящена изучению графов и связанных с ними матриц. Введем ряд базовых определений, знание которых необходимо для понимания излагаемого материала. Подробнее об основных понятиях теории графов можно посмотреть, например, [30], [10], [3]. По поводу теории матриц можно обратиться к [5], [27], [4].
Под словом граф будем понимать обыкновенный неориентированный граф Є = (У,Е), где V — У(С) — конечное множество и Е — Е{СЇ) — множество неупорядоченных пар различных элементов из V. Число п — |П| называют порядком графа. Иногда для простоты будем заменять вершины графа их порядковыми номерами, то есть будем считать П(С) = {1,2,... , п}.
Вершины и п V графа С называются смежными или соседями, если {и, у} Є Е{С1). Две вершины графа и иг/ называют близнецами, если множества их соседей совпадают. Полным называется граф, любые две вершины которого смежны. Полный граф с п вершинами обозначают Кп. Пустым графом Кп называют граф с п вершинами и без ребер.
Дополнением графа Є порядка п называют такой граф С, что У(С) = У{С) и Е(С) = Е{Кп) Е{С).
Степенью V вершины графа С называют число ее соседей. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей. Граф (7 называется ^-регулярным, если степени всех его вершин равны к. Граф называется регулярным, если он ^-регулярный для некоторого к.
Графы Є и Я называются изоморфными, если существует биективное

Доказательство. Очевидно, что x(G) = d+(G) < dz(G) по определению функций d+(G) и dz(G). Рассмотрим произвольный граф G. Пусть Vx, V2, ...,V^(G), V(G) = подмножества множества
вершин, порождающие клики минимального кликового покрытия графа G. Построим неотрицательное ортонормальное помечивание с целыми компонентами размерности x(G) следующим образом: сопоставим всем вершинам v Е Vi — г-тый орт пространства Следовательно
x(G)>dl(G)
Следствие 1.4.5 Если у графа G существует неотрицательное ортонормальное помечивание размерности t, то у G существует ортонормальное помечивание, сопоставляющее каждой вершине орт пространства Rf.
Таким образом, хроматическое число может быть определено с помощью минимума ранга по конечному множеству матриц. Расширения множества CZ(G) на множество C(G) или множество AUG) не дают изменения минимума ранга.
Определим функцию rz(G) следующим соотношением
rz(G) = min rank X.
XgAz(G)
Рассмотрим, какими свойствами обладает такая функция. Очевидно,
r(G) Теорема 1.4.6 Для любого графа G
q(G) = rz{G) влечет a(G) = x{G)