Графы без 3-лап и сопутствующие частичные геометрии

• Автор: Вакула, Игорь Александрович
• Шифр специальности: 01.01.04
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Екатеринбург
• Количество страниц: 93 с.

Глава 1. Предварительные результаты
• Глава 2. Графы, содержащие 4-коклику
Глава 3. Графы, не натягиваемые на некоторую 3-коклику
Глава 4. Графы, разбиваемые на три клики
Глава 5. Графы, натягиваемые на любую 3-коклику
Список литературы

Постановка задачи. В настоящей работе исследуется класс графов без 3—лап и сопутствующие частичные геометрии. Имеется несколько источников интереса к исследованию предпринятому в настоящей работе. И как это часто бывает, приведенные ниже точки зрения имеют тесные внутренние взаимосвязи.
Первый источник лежит в области общей теории графов. Здесь и далее под словом граф мы понимаем конечный неориентированный граф без петель и кратных ребер. Если Г — граф, то посредством V(Г) и Е(Г) обозначим, соответственно, множество вершин и множество ребер графа Г. '3-лапой называется полный двудольный граф с долями из одной и трех вершин. Далее всюду, если не оговорено противное, подграф из Г будет означать порожденный подграф графа Г, то есть подграф, в котором вершины смежны тогда и только тогда, когда они смежны в Г. О графе мы говорим, что он является графом без 3-лап, если он не содержит подграфов изоморфных 3-лапе. Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберным графом мы называем любой граф Г, который изоморфен графу С(Д), для подходящего графа Д, где £(Д) — граф вершинами, которого являются ребра графа Д, причем две вершины смежны тогда и только тогда, когда их пересечение одноэлементно.
Класс графов без 3-лап можно рассматривать как класс, являющийся наиболее интересным расширением класса реберных графов, при этом он гораздо шире, и вместе с тем графы этого класса наследуют многие свойства реберных графов. Треугольник Т (полный подграф на трех вершинах) графа Г называется нечетным, если в Г Т существует вершина смежная Г в точности с нечетным числом вершин. В [10] доказано, что следующие условия эквивалентны:
(1) Г — реберный граф;
(2) Г не содержит 3—лап, и если два нечетных треугольника имеют общее ребро, то подграф, порожденный их вершинами, является полным подграфом.
Из ее формулировки видно, почему в качестве расширения класса реберных графов был выбран класс графов без 3-лап.
До последнего времени задача изучения графов без 3-лап при достаточно общих дополнительных ограничениях казалась сложной. Условие отсутствия 3-лап относится к, так называемым, локальным свойствам. Говорят, что граф обладает локально свойством Р, если подграф порожденный вершинами окрестности произвольной вершины этого графа об-ладет свойством Р. Если а — вершина графа Г, то через [а] будем обозначать окрестность вершины а, то есть множество вершин графа Г, смежных с а, а через а1 — объединение [а] и {а}, которое назовем замкнутой окрестностью вершины а. п—кликой (соотв. кокликой) графа Г называется любое его п—подмножество любые две вершины которого смежны (соотв. несмежны) в Г. Таким образом, графы без 3-лап — это в точности графы, в которых окрестность всякой вершины не содержит 3-коклик. Можно сказать, что задача полного описания графов без 3-лап является задачей восстановления графа по информации о его локальной структуре. Эта задача в такой постановке в основном изучается для точечных графов конечных геометрий (см. [13]) и других комбинаторносимметричных графов.
Сложность задачи восстановления графа по его локальным свойствам, в первую очередь связана с тем, что имея даже хорошее представление
0 строении окрестности каждой вершины графа в общем случае невозможно получить информацию о строении графа порожденного объединением окрестностей двух вершин графа, находящихся на расстоянии
1 и 2 в графе. Поэтому на этапе изучения необходимы дополнительные предположения о "взаимодействии'окрестностей вершин. Пусть о и 6 — вершины графа Г. Тогда подграф, порожденный пересечением [а] П [Ь] их окрестностей называется Л—подграфом, если они смежны, и р—подграфом, если они находятся на расстоянии 2. Последний из них обозначается М(а,Ь). Именно строение у—подграфа М(а,Ь) позволяет связать свойства окрестностей вершины а и Ь. Скажем, что Г — граф с некликовыми у—подграфами, если любой его у—подграф содержит пару несмежных вершин. Вместе с тем, как нетрудно видеть, любой граф не содержащий 3-коклик является графом без 3-лап, поэтому для того, чтобы условие отсутствия 3-лап не было вырожденным необходимо потребовать, чтобы каждая связная компонента содержала 3-коклику. При этом, как нетрудно видеть, выполнение условия отсутствия 3-лап и некликово-сти ^—подграфов для всего графа эквивалентно выполнению этих условий для всех его связных компонент. Итак, мы приходим к задаче изучения связных графов без 3-лап с некликовыми у—подграфами, содержа-

ны множества {ах, а2, а3,р,р2,рз, Я, 92,9з} служебными, а вершины {РьР2,РЗ)9ь92>9з} вершинами служебных треугольников. Для вершины и; е У(Г) {а1,а2,аз} через Маьаз>аз(и;) обозначим то множество М;(ах,а2,аз) (* = 112,3), которому принадлежит ги, а по-# средством М~иа2Аз{'ш) и М+а2аз(ш), соответственно, Л^_](а1,а2,аз) и
М+1(а1,а2,аз). Указание вершин 3-коклики во введенных выше обозначениях не будем производить в случае, когда 3-коклика фиксирована и нет неоднозначного понимания контекста. Зафиксируем 3-коклику оь а2, аз. Для вершины ш из д-подграфа левым /х-подграфом назовем подграф М~(и]), а правым — подграф М+(и>). Будем говорить, что вершина ге £ Г смежна слева (соотв. справа) с некоторой вершиной со свойством Р, если вМ+(щ)П [и>] (соотв. М~(ги) П [ге]) есть вершина со свойством Р.
Пометим вершины треугольника {р1,р2,рз} красным цветом, а вершины треугольника {дъ € У(Г) {ах, а2,03} назовем красной (соотв. синей), если она смежна слева и справа с вершинами красного (соотв. синего) треугольника, коричневой левой (соотв. правой), если слева она смежна с вершиной синего (соотв. красного) треугольника, а справа — красного (соотв. синего). Вершина — коричневая, если она коричневая левая или коричневая правая. Для коричневой вершины быть левой или правой означает иметь, соответственно, левую или правую ориентацию. Про набор из двух или более коричневых вершин будем говорить, что его вершины одной ориентации, если они все либо коричневые левые, либо коричневые правые. Заметим, что вершинам треугольников при таком определении присвоены те же цвета. В дальнейшем, говоря о красных вершинах, будем иметь в виду красные вершины не принадлежащие красному треугольнику, аналогично для синих вершин. Скажем, что вершины V(Г) {а], а2, аз} поименованы. В случае когда 3-3$ коклика и пара треугольников фиксированы для X С У(Г) посредством
а(Х), Р{Х), к(Х) и к'(Х) обозначим, соответственно, множества красных, синих, коричневых левых, коричневых правых содержащихся в X (вершины треугольников не учитываются).
Лемма 5.2. Пусть Г — связный редуцированный граф без '6-лап с некликовыми р-подграфами, удовлетворяющий (г) — (ш) и (Б)