Содержание к диссертации
Введение
1 Реберные точные графы Деза 14
1.1 Предварительные результаты 14
1.2 Техническая лемма 15
1.3 “Внутрикликовый” случай реберного графа 17
1.4 “Внекликовый” случай реберного графа
2 К\ з-свободные точные графы Деза с некоторым ограничением на структуру 38
3 Точные графы Деза с 3-кокликой
3.1 Предварительные результаты 43
3.2 Основные замечания 45
3.3 Графы с параметром к Є {2а — Ъ + 3, а + 3, Ъ + 3} 51
3.4 Графы с параметром к = 26 — а + 3 58
4 К\ з-свободные графы Деза диаметра больше двух 78
4.1 Предварительные результаты 78
4.2 Доказательство 80
Литература 85
Введение к работе
Актуальность и степень разработанности темы исследования. В данной диссертации исследуются K1,3-свободные графы Деза. Интерес к графам без порожденных K1,3-подграфов зародился благодаря работе Бей-неке (см. [19]), в которой автор дает классификацию всех реберных графов через перечисление запрещенных индуцированных подграфов, и K1,3 был одним из девяти таких подграфов. Это стало началом изучения K1,3-свободных графов как самодостаточного класса. Так, в 1974 году Самне-ром в [34] и, независимо от него, в 1975 Лас Вергнасем в [29] было доказано, что все связные графы без порожденных K1,3-подграфов с четным числом вершин имеют совершенные паросочетания. Следующим толчком для привлечения интереса к K1,3-свободным графам стало открытие алгоритма, работающего за полиномиальное время, для поиска максимального независимого множества в таких графах (см. [32], [31]). Позднее, в 1999 году, в работе [30] была дана характеризация совершенных K1,3-свободных графов. Помимо уже перечисленных работ существует множество статей и исследований, посвященных изучению графов без порожденных K1,3-подграфов (например, см. [26]).
Помимо реберных графов, интерес представляют и другие классы K1,3-свободных графов. Например, интервальные графы, граф икосаэдра, граф Шлефли, дополнения к графам без треугольников и другие. Легко понять, что графы, являющиеся дополнениями к графам без треугольников, не содержат 3-коклики. Что и гарантирует в них отсутствие K1,3-подграфа. Поэтому часто в своих исследованиях графов без порожденных K1,3-подграфов авторы полагают наличие в графе 3-коклики.
В своей статье [22] А.Брауэр и М.Нумата приводят полное описание K1,3-свободных редуцированных графов с несвязными -подграфами. Описание кореберно регулярных и вполне регулярных графов без порожденных K1,3-подграфов было дано В.В.Кабановым и А.А.Махневым в работах [10] и [11]. Ими же проводилось изучение графов с особыми ограничениями на -подграфы. Так В.В.Кабановым в [12] был описан класс
і^із-свободных графов, которые содержат 3-коклики и все /х-подграфы имеют радиус более 1, а А.А.Махневым в [14]получено полное перечисление всех графов без порожденных і^із-подграфов, содержащих 3-коклику и имеющих регулярные /х-подграфы. А в работах [1] и [2] И.А.Вакула и В.В.Кабанов описали класс связных і^із-свободных графов с некли-ковыми /.і-подграфами. Полное описание дистанционно-регулярных К\^-свободных графов было получено А.Блокхусом и А.Е.Броувером в [20].
В 2005 году важным шагом в исследовании і^із-свободных графов стала серия статей Марии Чудновской и Пола Сеймура (например, см. [23]), в которой авторы исследуют структурную теорию таких графов. В своих работах они классифицировали произвольные связные графы без клешней следующим образом:
-
Шесть специфичных классов і^із-свободных графов. Три из них — это класс реберных графов, класс правильных графов дуг окружности и класс порожденных подграфов икосаэдра. Оставшиеся три требуют дополнительных определений.
-
Графы, образованные четырьмя простыми способами из меньших -Кіз-свободных графов.
-
Антипризматические графы — класс графов, определяются как К\^-свободные графы, в которых любые четыре вершины порождают подграф с минимум двумя рёбрами (в частности, это означает, что в графе нет 3-коклик).
Несмотря на высокую значимость полученных М.Чудновской и П.Сеймуром результатов, они не всегда удобны для применения, особенно для исследования графов с определенными условиями регулярности. Также некоторые классы графов даны описательно, без приведения конструкций для их построения. И как следствие, полученная классификация не позволяет полностью определить і^із-свободные графы, которые являются графами Деза.
Благодаря статье [24] М. Деза и А. Деза возник интерес к исследованию графов, являющихся обобщением сильно регулярных графов, а именно, регулярных графов, у которых каждая пара вершин имеет либо а, либо Ь об-
щих соседей, где Ь > а. Позднее эти графы стали называть графами Деза. В 1999 году была опубликована работа пяти авторов [25], в которой они описывают базовые свойства таких графов, а также приводят некоторые конструктивные способы их построения (из разностных множеств, композиций и произведений графов и из сильно регулярных графов). В конце этой статьи дается полный перечень точных графов Деза с количеством вершин, не превышающим 13. Следующие по размеру графы Деза были найдены С.В.Горяиновым и Л.В.Шалагиновым, а именно, в своей статье [4] авторы приводят список всех неизоморфных графов Деза на 14, 15 и 16 вершинах.
Ниже приведенные результаты были получены авторами при изучении графов Деза с некоторыми ограничениями на их строение. Так, в статьях [7] - [9] Г.М.Ермаковой и В.В.Кабановым для точных графов Деза без 3-коклики с уь = Ь было найдено соотношение для параметров а и 6, а также описаны некоторые свойства и в отдельных случаях получено полное описание. Доказательство того, что точные графы Деза, полученные из треугольных, решетчатых и дополнительных к ним графов с помощью определенных инволюций, однозначно определяются своими параметрами и строением окрестности, было получено Л.В.Шалагиновым и В.В. Кабановым и опубликовано в работах [13], [17], [18]. А в статье [3] авторами определено число вершинной связности графов Деза, получаемых из сильно регулярных графов с помощью автоморфизма порядка 2. С помощью компьютерного перебора С.В.Горяиновым и Л.В.Шалагиновым были найдены все графы Деза, которые являются графами Кэли и имеют менее 60 вершин. Полученный список приводится в [5]. Реберно регулярные и кореберно регулярные точные графы Деза, содержащие вершины с несвязной второй окрестностью, исследованы в работе [6]. Авторы статьи [27] рассмотрели класс точных графов Деза с параметрами (п, /г, 6, а), где к = Ь + 1, и доказали, что при /3 > 1 этот класс состоит из 2-кликовых расширений полных многодольных графов с долями размера г±^-, а при /3 = 1 этот класс содержит две бесконечные серии с параметрами графов Пейли и параметрами графов Пейзерта. Но изученные классы не покрыва-
ют все множество графов Деза, что дает дополнительную мотивацию для продолжения исследований в этой области.
Далее приводятся основные определения.
Все рассматриваемые в работе графы являются связными, неориентированными, без петель и кратных ребер. Порожденным подграфом графа О называется подграф, вершины которого смежны тогда и только тогда, когда они смежны в графе О. Соседями будем называть смежные вершины графа. Обозначим через [w] множество всех соседей вершины w (а также подграф, порожденный на этом множестве вершин) и назовем [w] окрестностью вершины w, а число \[w]\ — степенью вершины w. Обозначим через w подграф на множестве вершин [w] U {w} и назовем w замкнутой окрестностью вершины w.
В дальнейшем граф и множество его вершин часто будем обозначать одинаково, если это не приводит к противоречию.
Полный граф на п вершинах будем называть п-кликой. Вполне несвязный граф на п вершинах будем называть п-кокликой.
Граф, состоящий из одного простого цикла на п вершинах, будем называть п-уголъником.
Полным двудольным графом Кт<п называется граф, множество вершин которого можно разбить на два подмножества мощности тип таким образом, что две вершины смежны тогда и только тогда, когда они лежат в разных подмножествах.
Реберным для заданного графа О является граф L(G), вершинами которого служат ребра графа О и две вершины которого смежны тогда и только тогда, когда соответствующие ребра имеют точно одну общую вершину в О. Хорошо известно (например, [19]), что реберные графы не содержат порожденных подграфов, изоморфных К\%. Графы, не содержащие порожденных подграфов, изоморфных К\^, называются і^з-свободными. Граф Ь(Кт<п) называется m х п-решеткой и обозначается Ктхп.
Граф О называется регулярным, если степени всех его вершин одинаковы. Кубическим называется регулярный граф степени 3. Граф является реберно регулярным с параметрами (v,k,X), если О — регулярный граф
степени к на v вершинах и для любых различных его смежных вершин и и w имеем \[и] П [w]\ = А. Граф О называется кореберно регулярным с параметрами (v,k,y), если О — регулярный граф степени к на v вершинах и для любой пары различных его несмежных вершин и и w имеем \[и] П [w]\ = у. Граф является вполне регулярным, если он регулярен и для любых различных его вершин и и w для некоторых констант А ^ 0, у > О имеем
{
А, если d(u,w) = 1; у, если d(u, w) = 2.
Граф называется сильно регулярным, если он регулярный и для любых различных его вершин и ииї для некоторых констант А, у имеем | [и] П [w] \ = X, если и ~ w, и |[м] П [w]| = yt в противном случае.
Граф О называется (v, к, Ь, а)-графом Деза (0 < а < Ь < к < v), если он содержит точно v вершин, является регулярным графом степени к и существуют такие константы Ь и а (Ь > а), что любые различные вершины u,w Є G имеют либо Ь, либо а общих соседей. Легко заметить, что класс графов Деза включает в себя класс сильно регулярных графов. Если граф Деза не является сильно регулярным и имеет диаметр 2, его называют точным графом Деза.
Отметим, что 4 х n-решетка является реберным графом для полного двудольного графа К^п. При п = А этот граф является сильно регулярным графом. А классификацию реберных сильно регулярных графов можно найти в работе [33].
В работе [25] авторами были введены дополнительные параметры а и /3 для любого графа Деза. В дальнейшем нам понадобится следующее утверждение из этой работы.
Предложение 1. [(Erickson et al.)J Пусть О является (v, k,b, а)-графом Деза. Определим для вершины и следующие параметры:
а = \{w Є G: \[и] П [w]\ = а}\, j3 = \{w Є С: \[и] П [w]\ = b}\.
Тогда а и /3 не зависят от выбора вершины и и в случае а ф Ь находятся по формулам
D(V— 1 I — R( K— 1 I о ai-u— 1 I — R( K— 1 ]
a = г— ; p = —r .
b—a ' ' a—о
Будем называть две вершины графа Деза парой “типа а”, если эти вершины имеют а общих соседей. Аналогично определим пару вершин “типа Ь”. Заметим, что каждая вершина лежит ровно в а парах “типа а” и ровно в /3 парах “типа Ь”.
Цели и задачи диссертационной работы. Целью данной работы является исследование і^із-свободных графов Деза с некоторыми ограничениями на структуру. К основным задачам работы относятся описание і^із-свободных точных графов Деза с 3-кокликой и классификация графов Деза, не содержащих і^із-подграфы в качестве порожденных и имеющих диаметр больше двух.
Научная новизна. Работа носит теоретический характер. Все основные результаты диссертации являются новыми. В диссертационной работе описан класс реберных графов, которые являются графами Деза. Для _?Сіз-свободных точных графов Деза, содержащих 3-коклику и являющихся объединением замкнутых окрестностей двух несмежных вершин, найдены параметры. Получено полное описание класса всех точных К\^-свободных графов Деза, которые содержат 3-коклику. Для графов Деза, которые имеют диаметр больше двух и не содержат .ft^ ^-подграфов в качестве порожденных, получена классификация.
Результаты работы могут быть использованы при дальнейшем исследовании графов Деза с различными условиями на структуру графа.
Теоретическая и практическая значимость. Работа носит теоретический характер. Результаты диссертации могут быть использованы для дальнейшего исследования структурных свойств графов Деза.
Методология и методы исследования. Основными методами исследования являются методы алгебраической теории графов. Основной технический аппарат — разделение графов Деза на отдельные классы и исследование их структуры.
Степень достоверности и апробация результатов. Достоверность полученных в работе результатов подтверждается соответствующими математическими доказательствами.
Основные результаты работы докладывались на следующих научных конференциях: 41-я Всероссийская молодежная школа-конференция “Проблемы теоретической и прикладной математики”, 42-я Международная Всероссийская молодежная школа-конференция “Проблемы теоретической и прикладной математики”, (43-я Всероссийская) молодежная школа-конференция “Современные проблемы математики” (ИММ УрО РАН, Екатеринбург, 2010–2012), международная конференция “Graphs and Groups, Spectra and Symmetries” (Новосибирск, 2016); а также на алгебраическом семинаре ИММ УрО РАН и научном семинаре ЧелГУ.
Публикации. Основные результаты диссертации опубликованы в работах [1-7]. Работы [1-4] опубликованы в журналах, входящих в перечень ВАК. Статья [1] также переведена на английский язык и опубликована в журнале “Proceedings of the Steklov Institute of Mathematics” (2014), статья [3] также принята к публикации в этом журнале в 2017 году.
Структура и объем диссертации. Диссертация состоит из введения, 4 глав и списка литературы. Объем диссертации составляет 90 страниц. Список литературы содержит 42 наименования.
Техническая лемма
Ввиду леммы 1.1 порожденный подграф на множестве {xij\i,j = 1,... ,6 + 1} является (6 + 1) х {Ъ + 1)-решеткой. Эта решетка вместе с полными подграфами Kuz \ {и} и Kwx \ {w} является объединением всех замкнутых окрестностей Xij, i,j = l,...,6+l. Рассмотрим [xij] П [WQ\. Поскольку G — граф диаметра 2, то [xij] П [WQ\ \ 0. Но тогда w i смежна с x k для некоторого А; из {1,... , j — l,j + l,...,6+l} или с :rTOJ- для некоторого m из {1,... , і — 1, і + 1,... , 6 + 1}. В любом случае получаем противоречие: W2 не принадлежит Kuz, J wx и и;2 не принадлежит {xij\i,j = 1,...,&+1}.
Пусть граф G имеет параметры (-и, б, 2,0). Так как G — точный граф Деза, то для пары несмежных вершин число общих соседей не равно 0. С другой стороны, нетрудно увидеть, что любая пара смежных вершин имеет ровно двух общих соседей. Следовательно, реберного точного графа Деза с такими параметрами не существует.
Пусть граф G имеет параметры (-и, б, 2,1), следовательно, \KUW\ = \KUZ\ = 4. По лемме 1.1 для каждой вершины Wi и Zj, i,j = 1,2,3, в антиокрестности [и]у существует треугольник, со всеми вершинами которого она смежна. Заметим, что любая пара вершин Wi, Wj, i,j Є {1,2,3}, і ф j, в [и]у не имеет общих соседей, а следовательно, эти треугольники не пересекаются ни по одной из вершин. Аналогично для вершин Zj, j = 1,2,3. Через Aw. (Az.), і = 1,2,3, обозначим треугольник, все вершины которого смежны с соответствующей вершиной Wi (zi). Через Aw обозначим множество всех соседей из [и[ вершин Wi, і = 1,2,3, очевидно, Aw = (Ji=1 AWi. Аналогично введем обозначение AZ, где Az = (Ji=1 Az.. Поскольку граф G является точным графом Деза, тогда G = и1- U Aw U Az. Отметим, что AW = AZ =9, при этом 0 AW П Az 9, 25 v 16.
Для дальнейших рассуждений нам понадобится следующая лемма. Лемма 1.5. Для любых Aw. и Az., i,j Є {1,2,3} верны следующие утверждения: 1. Aw. П AZj 1. 2. Если AW. П AZj = 1, то не существует ребер, соединяющих вершины из Aw. с вершинами из AZj. Доказательство. 1. Если AW. П AZj 1, тогда вершины Wi и Zj, i,j Є {1,2,3}, смежные с этими треугольниками, имеют более двух общих соседей, что противоречит заданным параметрам. 2. В противном случае получаем треугольник, все ребра которого принадлежат разным полным подграфам, а именно, Aw., Az. и некоторому полному подграфу, содержащему ребро, которое инцидентно вершинам из Aw. и Az., г, j Є {1, 2,3}. Лемма доказана.
Если AW P\AZ = 9, тогда v = 16, /3 = 15, а = 0 и, следовательно, граф G является сильно регулярным, что противоречит условию. Таким образом, AW П Az 9. Тогда существуют вершины, лежащие либо в Aw \ AZ, либо в Az\ Aw, и очевидно, что Aw\ Az = AZ\ Aw. Будем называть вершины из множества (Aw \ Az) U (Az \ Aw) “свободными”.
Отметим, что замкнутая окрестность любой вершины из Aw П Az пред ставляет собой объединение двух 4-клик, которые имеют одну общую вершину и одна из которых содержит некоторый треугольник Aw. и соответствующую ему вершину Wi, а другая — треугольник AZj и вершину Zj, соответственно, где г,j Є {1,2,3}. А поскольку граф G регулярен и G = и1- U Aw U Аг, то замкнутая окрестность любой “свободной” вершины содержит вершины из (Aw \ Az) U (Az \ Aw). Введем раскраску ребер подграфа, построенного на множестве вершин Aw U Az: красные — это ребра треугольников Aw., Az., і = 1,2,3; синие — это ребра, соединяющие две “свободные” вершины, принадлежащие разным треугольникам. При этом вершины из пересечения Aw П Az инцидентны только красным ребрам, а для “свободных” вершин верна следующая лемма.
Лемма 1.6. Из каждой “свободной” вершины выходит два красных и три синих ребра, причем все синие ребра замыкаются синими и образуют синюю А-клику.
Доказательство. очевидно из условия регулярности и параметров графа G, а также из строения графа G = и1- U Aw U Az.
Заметим, что на синих ребрах имеем объединение изолированных 4-клик. Следовательно, количество “свободных” вершин должно быть кратно 4, а \AW \ Az\ = \AZ \ Aw\ кратно 2, а следовательно, \AW П Az\ є {1,3, 5, 7}.
Пусть \AW П Az\ = 1. Без ограничения общности будем считать, что AWl П AZl ф 0. По лемме 1.5 не существует ребер, соединяющих вершины из треугольников AWl и AZl. Заметим, что вершины из множеств AWl \ AZl и AZl \ AWl не могут быть смежны более чем с одной вершиной из каждого треугольника AWi, AZi, і = 2,3, в противном случае получаем противоречие с параметром Ъ. Следовательно, каждая вершина из симметрической разности (AWl \ AZl) U (AZl \ AWl) множеств AWl и AZl смежна ровно с одной
“Внекликовый” случай реберного графа
Если т = п, тогда Л2 = Лз. Получаем набор из трех параметров Лі, A3, Л4, каждый из которых принадлежит множеству {а, &}, и тогда хотя бы два параметра равны между собой. Согласно рассуждениям выше, Лі не может быть равна Лз.
Предположим, что Лі = Л4. Подставив вместо Лі и Л4 полученные выше соотношения и выразив из них п, получаем равенство п = о + а. А так как ф 1 и п является целым числом, то ф может принимать только значение равное двум. Но тогда п = 2, что противоречит п 3, а следовательно, предположение о равенстве Лі и Л4 не верно.
Предположим, что Лз = Л4. Подставив вместо Лз и Л4 выведенные ранее для них соотношения, получаем (п — 2)ф = 2. Учитывая, что п и ф являются целыми числами и п 3, ф 2, получаем следующие значения для п и ф: п = 3, ф = 2. Получили, что граф G является кликовым 2-расширение 3 х 3-решётки.
Пусть граф G является кликовым -расширением треугольного гра гп( гп( П(П-І) фа 1 [п) (заключение 2 теоремы 3.1), где 1 [п) имеет параметры (4 , 2(п— 2),п — 2,4), п 6. При ф = 1 граф является сильно-регулярным графом, что противоречит условию леммы 3.1. Следовательно, далее мы будем рассматривать только случай ф 1. Определим количество общих соседей для различных пар вершин графа G: для вершин, лежащих в одной 0-клике, количество общих соседей составляет Лі = 2(п — 2)ф + (ф — 2) = (2п — 3)0 — 2; для смежных вершин, лежащих в разных 0-кликах, количество общих соседей составляет либо Л2 = (п — 2)ф + (ф — 1)2 = пф — 2; для несмежных вершин количество общих соседей составляет Лз = 40. Для G получили набор Лі, Л2, Лз, которые принадлежат множеству { 2,&} в соответствии с определением графа Деза. Это означает, что хотя бы два параметра должны быть равны между собой. Предположим, что Лі = Л2. Тогда после подстановки соответствующих формул в данное равенство получим, что п = 3, а это противоречит п 6. Предположим, что Лі = Лз. Тогда для параметра п получаем соотношение п = І, + -т. А так как ф 1 и п является целым числом, то ф может принимать только значение равное двум. Но тогда п = 4, что противоречит п 6.
Теперь предположим, что Л2 = Лз. Тогда для параметра ф получаем соотношение ф = —т. А так как ф 1 и является целым числом, то п—4 = 1. Следовательно, п = 5, что противоречит п 6.
Пусть граф G является кликовым -расширением графа Шлефли (заключение 3 теоремы 3.1). При ф = 1 граф является сильно-регулярным графом, что противоречит условию теоремы. Следовательно, далее мы будем рассматривать только случай ф 1. Определим количество общих соседей для различных пар вершин графа G: для вершин, лежащих в одной 0-клике, количество общих соседей составляет Лі = 16ф + (ф — 2) = 17ф — 2; для смежных вершин, лежащих в разных 0-кликах, количество общих соседей составляет либо Л2 = Юф + (ф — 1)2 = 12ф — 2; для несмежных вершин количество общих соседей составляет Лз = 8ф.
Для графа G получили набор Лі, Л2, Лз, которые принадлежат множеству {а, Ъ]. Следовательно, хотя бы два параметра должны принимать одинаковое значение. Но с учетом ф 1 мы получаем строгое неравенство для Лі, Л2, Аз, а именно, Ai А2 A3, что дает нам противоречие.
Далее будем считать, что у графа G найдется такой /і-подграф, что его радиус равен 1. Без ограничения общности будем считать, что подграф [7] П [5] имеет радиус 1 и вершина є Є ([7] П [5]) — это вершина, которая смежна со всеми остальными в /і-подграфе.
Доказательство. Если в графе G все /i-подграфы одного размера, то он является кореберно-регулярным. Согласно следствию 3.1 из теоремы 3.2, граф G является либо дополнительным графом к регулярному графу без треугольников, либо графом из заключения теоремы 3.2. Если G является дополнительным графом к графу без треугольников, то он не содержит 3-коклик, что противоречит условию леммы. Следовательно, такое не возможно. Если G является -расширением вполне несвязного графа с числом вершин т, где т Ф 2, то при т = 1 граф G является кликой с ф вершинами, при т 2 граф G является несвязным. В любом случае получаем противоречие с определением точного графа Деза. Остальные случаи из заключения теоремы 3.2 уже рассмотрены в лемме 3.1.
Предварительные результаты
Пусть граф G удовлетворяет условию теоремы, то есть является связным графом Деза с параметрами (i , к, о, а), 0 а Ъ к -и, /С з-свободный и диаметра больше двух. Заметим, что а = 0, к 2 и если d(u,w) = 2 для некоторых вершин и и w графа G, то [и] Г\[ъи]\ = Ъ.
Ранее было приведено утверждение 0.1, в котором М. Эриксоном с соавторами были определены некоторые ограничения для графов Деза с диаметром d = 2. Докажем аналогичное утверждение для графов Деза диаметра больше двух.
Лемма 4.1. Пусть G является (v, к,6, а) -графом Деза диаметра больше двух. Определим для вершины и следующие параметры: а (и) = \{w Є [и]: \[и] П [w]\ = а]\, (3(и) = \{w Є [и]: \[и] П [w]\ = b}\. Тогда а = 0 и имеет место следующее соотношение а (и) (к — 1) + (3(и) (к — Ъ — 1) = \G2{u)\ Ъ Доказательство. Зафиксируем вершину и графа G. Обозначим через N количество упорядоченных троек (u,w,x), где и w, w ж, х Є (J2(W). Количество упорядоченных троек (u,w,x), содержащих вершину w такую, что [и] П [w]\ = а = 0, равно а(и) (к — а — 1) = а(и) (к — 1). Количество упорядоченных троек (it,if,ж), содержащих вершину if такую, что [it] П [w]\ = 6, равно (3(и) (к — b — 1). Тогда N будет вычисляться как N = а (и) (к — 1) + (3(и) (к — Ъ — 1).
С другой стороны, количество различных вершин ж, входящих в упорядоченные тройки (u,w,x), будет равно \G2(u)\. Кроме того, для любых вершин и и w графа G таких, что d(u,w) = 2, выполняется \[и] П [w]\ = 6, 6 1. Следовательно, число N можно вычислить как N = \G2{u) Ъ\. Приравняв полученные выражения для числа N, получаем соотношение а (и) (к — 1) + (3(и) (к — Ъ — 1) = \G2{u)\ Ъ. Лемма доказана.
Продолжим доказательство теоремы. Далее рассмотрим три случая для графа G с учетом дополнительных ограничений.
1. Пусть граф G — реберно регулярный граф с параметром А = а = 0. Так как G является і і;з-свободным, то окрестность любой вершины не может содержать 3-коклики. Следовательно, степень любой вершины не превосходит двух, что дает нам значение для параметра к: к = 2. По условию граф G является связным, следовательно, он является n-угольником, п 6.
2. Пусть граф G — реберно регулярный граф с параметром А = 6, 6 1. Поскольку граф G связный, он является вполне регулярным графом с параметрами А = 6, /І = 6, отсюда, согласно следствию 4.1, выполняется равенство к = 2А + 3 — /І, то есть к = Ъ + 3. Заметим также, что в этом случае параметры а(и) = 0 и (3(и) = к для любой вершины и из графа G.
Определим значение параметра \G2(u)\ для произвольной вершины и графа G в соответствии с леммой 4.1: IG2fit)! = Т = —Ц = 2 + і v /1 о о о Так как параметр \G2{u)\ может принимать только целые значения, то Ъ делит 6. Поскольку граф G является реберно регулярным графом с параметром A = 6, вычислим для графа значение параметра Ъ\: Ъ\ = к — Х — 1 = (Ь + 3) — 6—1 = 2. Напомним, что 6г2(и ) = 2+ для произвольной вершины w. А так как \G2(w)\(k—2bi +2) = 26+8+f и кЪл = 26+6, выполняется утверждение 2 теоремы 4.2. Поэтому граф G является либо реберным графом кубического графа без треугольников, либо является графом икосаэдра.
3. Пусть граф G не является реберно регулярным. Пусть для любых смежных вершин и и w графа G число вершин в [и] П [w] равно либо 0, либо Ъ. Тогда в графе G найдутся два ребра Х\у\ и Х2У2 таких, что [х\\ П [у\\ \ = О и [х2] П [у2І = Ъ. Поскольку граф G является связным по условию теоремы, найдется простая цепь, включающая ребра Х\у\ и Х2У2. Будем перемещаться по этой цепи, начиная с ребра Х\у\, до тех пор, пока не встретим ребро, для вершин которого количество общих соседей равно Ъ. Как только такое ребро найдется, зафиксируем вершину и, которая является общей для найденного ребра UW2 и для предыдущего ребра в цепи uw\. Отметим, что [и] П [wi] \ = О, [и] П [if2] = о, 6 1 и в этом случае параметр к принимает значения к 3, и W\\ оо W2].
Так как граф G является if -свободным, то все вершины из множества [it]\({u i} U {іі г}) смежны с вершиной W2. Тогда а = 1, /3 = к — 1, \[и]\ = Ъ + 2 = к и граф G имеет параметры (-и, Ъ + 2, 6,0).
Из леммы 4.1 следует, что число вершин в G2(it) принимает значение \G2(u)\ = 2 + . Так как \G2(u)\ является целым числом, Ъ делит 2.
Граф G имеет параметры (-и, 4, 2,0). Рассмотрим некоторую вершину х графа G, и пусть окрестность этой вершины состоит из вершин i/i, 2/2, уз, 2/4. Поскольку граф G имеет параметры Ъ = 2, а = 0, каждая вершина окрестности [ж] будет иметь степень либо 0, либо 2. А так как граф G по условию теоремы является і і;з-свободным, то окрестность [х] не содержит 3-коклику. Следовательно, окрестность любой вершины графа G может быть либо 4-угольником, либо представляет собой объединение К\ U К%.
Если окрестность вершины х является 4-угольником, то у пары несмежных вершин этой окрестности будут 3 общих соседа, что противоречит 6 = 2. Следовательно, окрестность любой вершины является объединением К\ и к%.
Доказательство
Для вершин (/9i и (/92 в графе G найдется такая вершина х, что \ (/9i, % (/92. Соседи вершины % не могут лежать в (/9і П (/92, иначе поучаем подграф К\. При этом у вершин р должно быть не менее а общих соседей, поэтому количество общих соседей у вершин р в окрестности вершины (/9i должно быть не менее а — 2. Аналогичны рассуждения для х и ф в окрестности вершины (/92, и тогда количество общих соседей у и в [ері] U [(p2\ составляет не менее 2а — 4. Отметим, что \[х] П [ф]\ должно быть не менее а.
Рассмотрим различные возможности соотношений между а и 2а — 4: если а 2а — 4, то а 4. Так как а 3 и а - нечетное, получаем значения параметров а = 3, Ъ = 4, к = 8. если 6 2а — 4 а, то первое неравенство приводит к ограничению а 7, второе - к а 4. С учетом того, что а - нечетное число, получаем два набора параметров: (-и, 12, 7, 5) и (-и, 16,10, 7).
Далее рассмотрим различные значения для числа \[ipi] \ ([ 2] U V )!, которое принадлежит множеству {0,1,2}.
Предположим [(/?і] \ ([(р2І U V;_L)I = ІІУ2] \ ([ty?i] U "1)! = 0. В этом случае [(/?i] П [(/92] = а + 2, что дает 6 = а + 2. Тогда получаем равенство а + 2 = - , из которого следует, что а = 5, то есть граф G имеет набор параметров (-и, 12, 7, 5). Заметим, что [ері] \ [(р2\ и [ifo\ \ [ері] содержат по а вершин, и все они смежны с г\). Но для вершин существует несмежная с ними х, которая и с (/?i, и с (f2 должна иметь не менее а общих соседей. Получили, что [х] П [ері] = [ф] П [ері] = [ері] \ [(р2\ и [х] [ 2] = М [ 2] = [ 2] \ [ 2], но тогда [ ] П [х] = 2а = 10, что противоречит значениям а и Ь. Следовательно, предположение не верно.
Предположим \[tpi\ \ ([ 2] U 0J ) = [ty?2] \ ([ty?i] U "1)! = 1. В этом случае [(/?i] П [(/92] = а + 1, что дает 6 = а + 1. Тогда получаем равенство а + 1 = - , из которого следует, что а = 3, то есть граф G имеет набор параметров (-и, 8, 4,3).
Для вершины ері известно, что [ері] П [ф] = а и [ /?і] П [%] а, тогда \[Ф] [х] [v i]! — а 1. Аналогично рассуждая для вершины (/92, получаем I [ ] П [x] П [ 2] a 1- А следовательно, [ ]І І[Х] — 2a—2, где 2a—2 = 4 = b. А значит, [ф] П [x] П [ /?i] = [ф] П [x] П [ 2] = a — 1 = 2 и [ /?i] П [%] = I [(p2\ П [x] I = a Для вершины % определили 2a соседей в [ /?i] U [( 2],следовательно, оставшиеся две вершины лежат вне [cpi] U [( 2]. Обозначим их через Xi- Х2 и проведем для них аналогичные рассуждения по нахождению общих соседей с ері и с (f2- В результате рассуждений получим неравенство [Xi] [Х2\ ([ l] U [ty?2]) 2a — 2, где 2a — 2 = 6. Но вершина х является общим соседом для Xi и Х2, н0 тогда [%i] П [%2] &+ 1, что противоречит параметрам графа G. Следовательно, предположение не верно.
В [ /?i] \ [( 2] вершина ф смежна с а вершинами, а с двумя несмежна. Обозначим их из через Ь\ и Ьч и отметим, что они смежны между собой, иначе получаем подграф К\ . В [ері] П [іро\ вершина ф ни с чем не смежна, но тогда [ері] П [(/92] \ { } образуют клику размера a — 1, иначе получаем подграф К\. Более того, отсутствие К\ в качестве порожденного подграфа в графе G приводит к тому, что все вершины из [ері] П [(р2\ \ {ф}: Si и 62 также образуют клику размера a + 1. Аналогичны рассуждения про вершины из окрестности (/92, которые не смежны с ф: но смежны между собой. Обозначим их через 71, 72, и {7ь72І U ([(/9і] П [(/92] \ {ф}) тоже образуют клику размера a + 1.
Зафиксируем две произвольные вершины из [(/9i]n[(/92]\{V;} и посчитаем для них количество общих соседей: a — 3 вершины из [ері] П [(/92] \ { К ь 2, 7ь 72, ty?i, {Р2- Получили не менее a + 3 вершин, а следовательно, Ъ а + 3. Из ранее определенных наборов параметров этому условию удовлетворяет только (г , 16,10, 7).
Рассмотрим произвольную вершину фі из [ері] П [(р2\ \ {ф}: при этом вся её замкнутая окрестность должна лежать в (pfUip - Для неё уже определены некоторые соседи: а — 2 вершины из [ері] П [іро\ \ {ф}: 5\, #2, 7ъ 72, ty?i, 2, то есть а + 4 = 11 вершин. Тогда оставшиеся 5 соседей вершины лежат в ([ty?i] П [ ]) U ([(/92] п [?/ ]).
Для вершин фі и (/9і уже определены а общих соседей (вершины из [ері] П [(р2\ \ {ф}: Si и 2), и Для вершин фі и (/92 также определены а общих соседей. Поэтому последующее определение оставшихся пяти соседей вершины фі в ([ері] П [ф]) U ([(/92] П [ф]) приведет к тому, что хотя бы одни подграф из {[(/9і] П [фі\, [(/92] П [фі]} должен содержать Ъ вершин. Без ограничения общности будем считать, что [фі] П [ері] \ = Ъ = 10, то есть 3 из 5 соседей вершины фі лежат в [ері] П [ф]. Но тогда оставшиеся два соседа лежат в [(р2\ П [ф]: что приводит к [(/92] П [фі]\ = [(/9і] П [(/92] \ {ф,фі}\ + {7ь72ІІ + 2 = а + 2 = 9. Получили противоречие в параметрами а иЬ графа G, следовательно, предположение не верно.