Графы Тервиллигера в теории дистанционно регулярных графов

Оглавление
Введение 3
Определения и основные обозначения................................. 4
Обозначения .................................................. 4
Определения свойств регулярности графов....................... 6
Определения семейств графов .................................. 8
Мотивация работы................................................... 9
Общая характеристика работы........................................24
1 Характеризации графов Тервиллигера 27
1.1 Вспомогательные результаты....................................31
1.2 Проблема регулярности в регулярных графах Тервиллигера . . 35
1.3 Графы Тервиллигера с \1 ^ 3...................................40
1.3.1 Графы Тервиллигера с д = 2..............................40
1.3.2 Сильно регулярные графы Тервиллигера с /х = 2....44
1.3.3 Графы Тервиллигера с/х = 3..............................46
1.4 Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена 49
1.5 Графы Тервиллигера с /х = 4...................................51
1.6 Неравенство Кулена - Пака и графы Тервиллигера................59
1.7 Граница для коклик в //-подграфах.............................64
2 Локальные характеризации некоторых графов 68
2.1 Вспомогательные результаты....................................71
2.2 Дистанционно регулярные локально <5 графы.....................74
2.3 Локально НоЗг графы...........................................76
2.3.1 Предварительное обсуждение..............................76
2.3.2 Графы диаметра не больше 5..............................79
2.3.3 Ограничение диаметра....................................87
2.4 Возможные автоморфизмы дистанционно регулярных локально Яоб'г графов ...................................................91
2
2.4.1 Предварительное обсуждение................................91
2.4.2 Массив пересечений {50,42,1,1,2,50}.......................98
2.4.3 Массив пересечений {50,42,9,1,2,42}......................100
2.4.4 Замечание о рациональных характерах в методе Хигмена 103
2.5 Графы, в которых окрестность каждой вершины изоморфна
графу Гевиртца..................................................104
2.5.1 Предварительное обсуждение...............................104
2.5.2 Редукция к графам диаметра, большего 3...................108
2.5.3 Графы большого диаметра..................................115
3 Нереализуемость некоторых массивов пересечений 117
3.1 Вспомогательные результаты.....................................118
3.2 Массивы пересечений {55,36,11; 1,4,45} и
{56,36,9; 1,3,48}...............................................119
3.3 Массив пересечений {45,30, 7; 1,2,27}..........................123
3.3.1 Предварительное обсуждение...............................124
3.3.2 Верно неравенство \Ьо\ <7.............................130
3.3.3 Верно неравенство |/^о| < 6.............................132
3.3.4 Верно неравенство \Ьо\ ф 5.............................139
3.4 Массивы пересечений {52,35,16; 1,4,28} и
{69,48,24; 1,4,46}..............................................143
4 Графы Райзера и геодезические графы диаметра 2 149
4.1 Графы Райзера..................................................152
4.2 Бирсгулярные геодезические графы диаметра 2................158
4.2.1 Вспомогательные результаты...............................158
4.2.2 Случай нерегулярного графа В.............................161
4.2.3 Случай регулярного графа В...............................165
4.2.4 Некоторые результаты о несуществовании графов .... 168
3
Введение
В диссертации проводится систематическое изучение класса графов Тсрвил-лигера и связанных с ним вопросов в теории дистанционно регулярных графов. Разработаны методы изучения локального строения графов Тервилли-гера, дистанционно регулярных графов с заданными окрестностями вершин, предложены доказательства несуществования дистанционно регулярных графов с некоторыми допустимыми массивами пересечений.
В этой главе приведены основные определения и обозначения, объясняется мотивация работы.
Определения и основные обозначения
В этом разделе собраны общие для всех глав обозначения и определения графов и их свойств. Наша терминология и обозначения в основном стандартны, см. монографию [1].
Обозначения
В работе рассматриваются только неориентированные графы без петель и кратных ребер. Пусть Г является таким графом. Для подмножества X вершин графа Г мы будем также через X обозначать подграф, индуцированный в Г множеством X. Соответственно число вершин в графе X обозначается через |Х|. Далее термин подграф всегда будет означать подграф, индуцированный множеством вершин.
Для пары вершин х, у € Г таких, что в Г существует путь, соединяющий х и у, через д(х,у) обозначается расстояние между х и у, т.е. длина кратчайшего пути между этими вершинами. Диаметром с1(Г) графа Г называется максимальное встречающееся расстояние между его вершинами. Вершины х:у с б(х.у) = 1, т.е. соединенные ребром, называются смежными; смежность вершин также обозначается через х ~ у.
4
Для вершины ж Є Г окрестностью х в Г называется подграф, индуцированный множеством ее соседей (вершин на расстоянии 1 от х) и обозначаемый через Г (а;). Зачастую, если граф Г определен контекстом, окрестность вершины х обозначается через [х]. Через х1 обозначается замкнутая окрестность или шар радиуса 1 с центром в ж, т.е. ж1 = {ж} и [х]. Для подграфа X графа Г через Xа- обозначим П^д-ж-1, т.е. в общем случае Xі £ X.
Более общо, через Г»(ж) обозначим подграф, индуцированный множеством вершин на расстоянии і от х. В частности, [х\ = Г(ж) = ГДх). Для множества вершин X графа Г через Г(Х) обозначим множество вершин из Г \ X, имеющих хотя бы одного соседа в X.
Степенью или валентностью вершины х называется количество ее соседей, т.е. число |Г(ж)|. Если граф Г определен контекстом, то степень вершины х обозначается через кх. Граф Г называется регулярным, степени к, если степень каждой его вершины равна к. Граф называется бирегулярнъш, если в нем встречаются вершины точно двух различных степеней.
Пусть Т — некоторый класс графов. Граф называется локальноТ-графом, если окрестность всякой его вершины изоморфна некоторому графу из Т.
Для вершин х.у, находящихся на расстоянии 2 в Г, подграф Г(ж) П Г(у) называется р-подграфом вершин х,у. Скажем, что для графа Г определено число р{Г), если для любых двух вершин ж, у Є Г, находящихся на расстоянии 2, верно равенство |Г(ж) Г) Г(?/)| = р(Т).
Для пары смежных вершин ж, у подграф Т(х)ПТ(у) называется \-подграфом вершин ж, у. Если граф Г определен контекстом, то число вершин в Л-подграфе вершин ж, у обозначается через \ху.
Матрицей смежности графа Г называется (ОД)-матрица А = Иг размера |Г| х |Г|, строки и столбцы которой индексированы множеством вершин Г и (ж, з/)-элемент А равен 1, если ж ~ у, и равен 0, если ж фу.
Спектром графа называется спектр его матрицы смежности. Спектр записывается в виде {0{],..., $(*}, где в{* означает, что собственное значение 0г имеет кратность /г.
Два графа, имеющие одинаковый спектр, называются изоспектральиыми. Из существования изоморфизма между графами следует их изоспектральность; обратное в общем случае неверно. Пусть графы Гі и Г2 на V вершинах имеют матрицы смежности А] и А-2 соответственно, Л„ — матрица порядка-у, состоящая целиком из единиц. Если матрицы уЗп - А] и уЗп - А2 (обобгце7і-пые матрицы смежности графов, см. |2|) имеют равные спектры для любого у € И, то графы Г] и Г2 называются Н-изоспектральными.
Для графов Х,У с У(Х) ПГ(У) = 0 через X фУ обозначим граф, назы-
5
ваемый прямой суммой X и У, полученный объединением грас|юв X и У и добавлением ребер, соединяющих все вершины из X со всеми вершинами из У.
Для графа Г через Aut(T) обозначается группа всех его автоморфизмов. Для элемента д Є Aut(T) через Fix(g) обозначается подграф вершин из Г, неподвижных под действием д.
Определения свойств регулярности графов
Пусть Г является связным графом диаметра <1. Если вершины х, у находятся на расстоянии 0 < і ^ d в Г, то через Ьг(х, у) (через сг(х, у)) обозначим число вершин в подграфе Гг+і(т) ПГ(у) (соотв. Гг_і(а-) П Г(г/)). Здесь мы полагаем Г_ і (a:), Td+i(x) пустыми множествами и Т0(х) = {.т}.
Граф Г называется дистанционно регулярным с массивом пересечений
{Ьо> Ь\у • • • > bd—її ^1,, сД}
если верны равенства Ьг(х,у) — 6, и сг(х,у) = сг для любых вершин х,у, находящихся на расстоянии г в Г, и для любого 0 ^ г ^ d. Положим также аг = 60 — Ьг — Сг. Заметим, что для дистанционно регулярного графа число 60 равно степени к графа, ci = 1, сч = /х(Г) и bd = со = 0.
Дистанционно регулярный граф — единственный, если любой дистанционно регулярный граф с таким же массивом пересечений ему изоморфен.
В дистанционно регулярном графе для любых 0 ^ i,j,l ^ d и любых вершин х, у, находящихся на расстоянии Z, количество вершин г, находящихся одновременно на расстоянии г от х и на расстоянии j от у, т.е. число |Г,(я) П (у)|, не зависит от выбора вершин х,у и равно р[у т1исла р\; называются числами пересечений. В частности, для любой вершины х Є Г подграф Т\(х) содержит одно и тоже число вершин, равное kt = р^г, 1 ^ г < d, и является регулярным графом степени аг. Заметим, что по определению аь := ргг1, 6, := Р\+и» Ь := tf-w
Ввиду [1, Предложение 4.1.6) числа пересечения с,, удовлетворяют следующим условиям:
bQ> b 1 ^ ^ bd- ь 1 = Cl ^ с-2... < с*
с, ^ bj, если i + j ^ d,
а но [1, Лемма 4.1.7) числа пересечений р1Х] могут быть вычислены по следующим соотношениям:
р\3 :== Р1зг> р\о := 6гі> р\м 1 := О.Ри-1 :== °U Р1и аь :=
6
р^+і, := — (рі.-А-і +р\М - аі) + р‘],,+і^+і - ?7-іЛ-і)>
с.7+1
в частности, все числа пересечений могут быть вычислены по числам из массива пересечений.
Дистанционно регулярный граф диаметра 2 с массивом пересечений {бо, 61; сьс2} обычно называется сильно регулярным графом с параметрами (щ к, А, р), где V := |Г|, /с := 6о, А бо - &і - 1 и /г := с2-
Вполне регулярным графом с параметрами [у, к. А, р) называется граф Г, содержащий V вершин, регулярный степени к, в котором |Гі(т) П Г і (т/) | = А для любой нары смежных вершин х,у: и |Гі(х)ПГі(і/)| = р для любой пары вершин х,у с с1(а*,?/) = 2. (Таким образом, сильно регулярный граф является вполне регулярным графом диаметра 2.)
Прямоугольным соотношением в дистанционно регулярном графе называется равенство
к(к - а\ - 1) = /с2с2,
получаемое подсчетом двумя способами числа ребер между первой и второй окрестностями вершины. В сильно регулярном графе это равенство принимает вид
к(к — X — I) = (у — к — 1 )р.
Матрица смежности дистанционно регулярного графа диаметра (I имеет точно <і+1 различных собственных значений Ьц = Оо > в\ > ... > 0^. Ввиду [1, Раздел 4.1.В] различные неглавные собственные значения дистанционно регулярного графа (т.е. отличные от его валентности) являются собственными значениями следующей матрицы:
/ - 1 - \
-Сі Ьі 0 0 ... . 0
Сі 1 о- 1 5* Ь-2 0 ... . 0
0 С2 к — &2 — с3 63 .... 0
0 0 сз к - 63 - с4 Ь4 . 0
0 . . . . • • ... «... 0
0 . . . . • . ... . . . . Ьа-1
0 . . . • • . ... ... і -о 1 г-* 1 £
\
По [1, Теорема 4.1.4] кратность собственного значения 0 вычисляется по формуле
т :=
V
ЕІ0 кМО)2’
7
где иг(в) := и)г(0)/(Ьо • • • и щ(0) := 1, и многочлены ге,(х) определяются следующим образом:
ш0(х) := 1, ь>\(х) := х, У)г+\(х) •= “ <ь)щ(х) - сД-іШг_і(х).
Собственные значения сильно регулярных графов, как правило, целые. Исключение составляют так называемые графы в половинном случае, имеющие параметры (4д -1- 1,2/*, у, у - 1) (см. лемму 2.1.1 в работе).
Граф диаметра д называется антиподалъным, если отношение на множестве вершин совпадать или находиться па расстоянии сі является отношением эквивалентности. Антинодальный граф Г называется г-пакрытием графа Е, если всякий антиподальный класс в Г содержит точно г вершин и его фактор-граф но указанному отношению эквивалентности изоморфен графу Е.
Неполный граф Г называется графом Терв'иллигера, если определено число д(Г) и любой д-подграф в Г является кликой.
При изучении графов Тервиллигера будут полезны следующие определения и обозначения. Для вершины х графа Г подграф [х]1 назовем ядром вершины х и обозначим его порядок через Ех, если граф Г ясен из контекста. Вершина х называется редуцированной, если [х]1 = {х}, и передуцировап-пой в противном случае. Таким образом, ядро х является максимальным по включению множеством вершин, замкнутая окрестность которых содержит окрестность X.
р]сли Г — граф Тервиллигера, то нас будет также интересовать окрестность вершины за вычетом ее ядра, т.е. подграф
Дг,х := Г1(х)\(Г1(х)±),
обозначемый через Дх, если граф Г ясен из контекста.
Для произвольного графа Г определим его а-кликовое расширение как граф Г, полученный заменой каждой вершины х графа Г на клику Ьх С Г порядка а так, что Ьх П Ьу = 0, если х ф у} и попарным соединением всех вершин из двух таких клик ЬХу Ьу, если их прообразы х,у смежны в Г.
Определим отношение эквивалентности = на множестве вершин графа Г по правилу х = у <*=> х1 = у1. Фактор-граф графа Г по отношению = будет обозначаться через Г.
Определения семейств графов
Напомним, что с-клшой С графа Г называется полный подграф (т.е., граф, любые две вершины которого смежны) графа Г, содержащий точно с вершин.
8
Подграф С называется кликой, если он является с-кликой для некоторого с.
Кокликой С графа Г называется непустой индуцированный подграф в Г с пустым множеством ребер. Коклика называется с-кокяикой, если она содержит точно с вершин.
Клика или коклика в графе называется максимальной, если она является максимальной по включению.
Полный многодольный граф с п долями порядков тпь..., тп обозначается через Кт1>"')ТПп. Полный двудольный граф К]>т называется т-звездой или т-лапой.
Для целых тп > 0, п > 0 определим гп х п-решетку как граф, множеством вершин которого являются все пары вида (г,^), 1<г^т, 1<.7< п, и различные пары (г,.?) и (?•',/) смежны, если и только если г = г' или j = /.
Для натурального числа п п-циклом или п-угольником называется граф на п вершинах хи • • •, в котором ^ Хг+ъ г = 1,..., 7г и х\ ~ хп.
Граф Петерсена является единственным сильно регулярным графом с параметрами (10,3,0.1), граф Хоффмана - Синглтона является единственным сильно регулярным графом с параметрами (50,7,0,1). Сильно регулярные графы с параметрами Л = 0, р = 1 называются графами Мура,
Заметим, что в сильно регулярном графе с параметрами (г>, /с, Л, 1) окрестность любой вершины состоит из г = к/(А 4- 1) изолированных 5-клик, где 5 = А + 1. Обозначим через Т(в,г) класс сильно регулярных графов с параметрами (тдг5,5-1,1). В частности, класс сильно регулярных графов Мура совпадает с классом /’(1,г) (иге {2,3,7,57} ввиду результата [12]). Примеры графов из класса К{з,г) при 5 > 1 не известны.
Графы икосаэдра, Конвея - Смита, Доро являются единственными дистанционно регулярными графа с массивами пересечений {5,2,1; 1,2,5}, {10, 6,4,1; 1,2,6,10} и {10,6,4; 1,2,5} соответственно. Определения также упоминаемых в работе графов Хэмминга, Джонсона и Грассмана могут быть найдены в [1, Глава 9|.
Мотивация работы
Объектами исследования в настоящей работе являются дистанционно регулярные графы и графы с некоторыми более специфическими условиями такими, например, как запрет на подграфы определенного вида.
Напомним одно из нескольких эквивалентных определений дистанционной регулярности графа. Граф Г называется дистанционно регулярным., если для любого I = 0,... Д := с!(Г) и любой пары вершин х,у, находящихся на рас-
9
стоянии I в Г, множество Г,(а:) П Т3(у) содержит точно р1Х1 вершин, причем число р{3 зависит только от г. ^Л, но не от выбора конкретной пары вершин х, у, находящихся на расстоянии /. Числа р[3 называются числами пересечений графа.
Такое определение позволяет понять, что свойство дистанционной регулярности является обобщением дистанционной транзитивности, т.е. транзитивности группы автоморфизмов графа на множестве равноудаленных пар вершин.
Классическими в некотором смысле примерами дистанционно регулярных (и дистанционно транзитивных) графов являются графы Хэмминга и графы Джонсона, см. [1, Глава 9). Эти семейства графов связывают теорию дистанционно регулярных графов соответственно с алгебраической теорией кодирования и теорией блок-схем (дизайнов), что было показано в диссертации Ф. Дельсарта (3). Существует, однако, гораздо больше подобных связей: с теорией конечных групп, конечными геометриями, схемами отношений, ортогональными многочленами. В последнее время интерес к дистанционно регулярным графам наблюдается со стороны задач комбинаторной оптимизации, теоретической физики и квантовых вычислений, см. обзор [4]. В качестве завершения вступления можно сказать, что дистанционно регулярные графы, методы их исследования (комбинаторные и алгебраические) позволяют единообразно изучать объекты из различных областей дискретной математики и алгебры.
Одной из центральных задач в теории дистанционно регулярных графов является классификация (^-полиномиальных дистанционно регулярных графов или, в других терминах, (Р и <3)-полиномиальных схем отношений.
Решение этой задачи стимулирует исследование более общих вопросов теории (некоторые из них также рассматриваются в диссертации и): существование и единственность графов с заданными параметрами, изучение строения графов известных семейств.
Задача классификации (^-полиномиальных дистанционно регулярных графов была сформулирована в известной монографии Баннаи и Ито [5] в начале 1980-х годов, и ее важность объясняется, с одной стороны, возможным новым подходом к классификации конечных простых групп, поскольку каждая конечная простая группа за исключением спорадических групп и групп малого лиевского ранга является группой автоморфизмов определенного (}-полиномиального дистанционного регулярного графа. С другой стороны, известно всего 16 семейств примитивных дистанционно регулярных графов неограниченного диаметра, которые, как правило, имеют естественные опи-
10
сания на языке групп или конечных геометрий.
На сегодняшний день, пожалуй, наибольший вклад в решение упомянутой задачи классификации принадлежит П. Тервиллигеру. Класс графов, названный его именем и вынесенный в название диссертационной работы, возник в связи со следующей гипотезой Баннаи и Ито, также сформулированной в монографии [5]:
для каждого к ^ 3 существует лишь конечное число конечных дистанционно регулярных г]хіфюб валентности к.
Данная гипотеза верна в предположении дистанционной транзитивности графа, см. [6]. Ее сложность в общем случае можно пояснить следующим образом. Известно [1, Предложение 4.1.6), что в массиве пересечений любого дистанционно регулярного графа выполняются неравенства
Ьг ^ С» ^ Сі—1 ? О ^ І ^ с£,
т.е. последовательности {сг}^=1 не возрастают и не убывают, соответ-
ственно.
Поскольку 6о — это валентность графа, то выполнение неравенства Ьг > 6!+і (или Съ > Сг_і) для всех і означало бы, что граф имеет диаметр не больше 6о и тогда очевидно, что число графов с ограниченными валентностью и диаметром конечно. Поэтому проблема заключается в доказательстве строгих неравенств или ограничении числа повторения нестрогих неравенств Ьг ^ С-1 ^ Сг-\-
В работе |7| Тервиллигер показал, что для массива пересечений дистанционно регулярного графа, содержащего порожденный 4-цикл, выполняются неравенства
с*і Ь-і ^ с,—і ^1—1 и і 4~ 2, 1 ^ ^ гі,
где по определению аг = 60 - Ьг — сг.
Используя эти неравенства, можно показать, что для дистанционно регулярного графа, содержащего 4-цикл, верна граница Тервиллигера (1, Следствие 5.2.2]:
л^Ь0 + сл<_2Ьо_ а\ 4- 2 аі 4- 2 и таким образом гипотеза Баннаи и Ито верна в этом случае.
Дистанционно регулярные графы, не содержащие 4-циклов, были названы графами Тервиллигера. Затем условие дистанционной регулярности было заменено на гораздо более слабое условие |1, Глава 1.16): неполный грае]) Г называется графом Тервиллигера, если для любой пары его вершин х, у,
11
находящихся на расстоянии 2, подграф Т\(х) ПГ\(у), индуцированный общими соседями вершин х,у, является полным графом на ц вершинах, где ц = д(Г) — это некоторая константа, зависящая от Г. В дальнейшем, подграф ГДт^ПГ!(?/) для вершин х. у, находящихся на расстоянии 2 в произвольном графе Г, будем называть ц,-подграфом. По устоявшейся традиции символ д используется и для обозначения такого подграфа, и для обозначения его мощности как числового параметра графа Г.
Стоит заметить, что для дистанционно регулярных графов, имеющих кратчайший цикл заданной длины д (т.е. с заданным обхватом у), гипотеза Баннаи - Ито также верна в силу границы Иванова [1, I лава 5.9]:
(1 ^ д^~\
Таким образом, доказательство гипотезы сводится к оценке обхвата графа как функции от его валентности. что является довольно тяжелой задачей исследования спектров дистанционно регулярных графов с массивами пересечения специфического вида. Спустя практически 25 лет с момента формулировки гипотезы ее доказательство было аннонсировано коллективом авторов под руководством Дж. Кулена [8|.
Гипотеза Банна.и и Ито не связана напрямую с упомянутой выше задачей классификации (^-полиномиальных дистанционно регулярных графов, но результаты, полученные на пути доказательства первой, работают в процессе решения второй; см., например, статью [9], в которой по массивам пересечений охарактеризованы семейства графов свернутого половинного куба, половинною куба и свернутых графов Джонсона.
Класс графов с запрещенными 4-циклами активно изучается в теории графов (прежде всего, в экстремальной теории графов, изучающей графы с запрещенными подграфами), см., например, [10], но в теории дистанционно регулярных графов эти графы привлекают внимание исследователей не только как исключение в границе Тервиллигера. но и в связи со следующим курьезным фактом: в своей работе [7] Тервиллигер рассмотрел графы без условия дистанционной регулярности (т.е. называемые нами сейчас графами Тервиллшера) и сформулировал сильное утверждение, доказательство которого оказалось некорректным, см. [1, Предложение 1.16.1].
Прежде, чем его сформулировать, отметим две конструкции графов Тервиллигера. Первая из них определяется через операцию кликового расширения. Действительно, если Г — это граф Тервиллигера с \х — 1 (класс таких графов не поддается описанию), то операция а-кликового расширения позволяет построить граф Тервиллиюра с произвольным заданным ц = а > 1.
12
Рис 0.1. Пятиугольник и его 2-кликовос расширение.
Операция прямой суммы графов, т.е. попарного соединения вершин из двух графов с нспересекающимися множествами вершин, позволяет также получать графы Тервиллигера с произвольно заданным /х, если в качестве слагаемых прямой суммы выступают граф Тервиллигера диаметра 2 с параметром р! и клика порядка р — //.
Описанные выше конструкции графов Тервиллигера с // > 1 не представляют интереса. Мы исключим эти случаи из общего рассмотрения следующим образом. Понятно, что в графе Тервиллигера Г, полученном как а-кликовос расширение графа Тервиллигера Г с р = 1, для всех вершин х выполнено неравенство |Г 1 (а:)х| ^ /х(Г) (неравенство может быть строгим для вершин из Г, окрестности которых являются кликами). Тогда мы будем рассматривать графы Тервиллигера Г с условием, что в них найдется вершина х, для которой |Г1 (гг)-1-1 < //(Г). Дополнительно к этому, условие Г1 = 0 исключает из рассмотрения прямые суммы графов Тервиллигера и клик.
Такие ограничения не исключают из рассмотрения кликовые расширения графов Тервиллигера с р = 2, например, или любым другим р > 1. Но класс графов Тервиллигера существенно меняется при переходе от графов с // = 1 к графам с /х > 1: для /2 > 2 не известны примеры графов Тервиллигера Г с Г-1 = 0, не являющихся кликовыми расширениями, а для р = 2 известны только три таких графа, которые будут описаны ниже.
Теперь упомянутое выше утверждение Тервиллигера [7] можно сформулировать следующим образом:
в регулярном графе Тервиллигера Г с р > 1, содержащем хотя бы одну вершину х с |Г 1 (д:)-11 < р, подграфы регулярны для всех вершин у £ Г.
Заметим, что подграф Ау является также графом Тервиллигера, либо объединением изолированных клик, либо пустым множеством. Этот естественный факт позволяет эффективно использовать индуктивные рассуждения при изучении графов Тервиллигера.
13
Поскольку доказательство из [7] оказалось некорректным, в монографии [1, стр. 35] утверждение Тервиллигера было записано как нерешенная проблема. Одним из основных результатов первой главы диссертации является положительное решение этой проблемы. В частном случае р = 2 эта проблема была ранее решена в работе A.A. Махнева |11].
Справедливость доказанного утверждения указывает на очень жесткое локальное строение регулярных графов Тервиллигера, поскольку подграфы Ау имеют диаметр 2, а в силу предложения 1.16.2 из [1] регулярные графы Тервиллигера диаметра 2 являются кликовыми расширениями дистанционно регулярных графов (дистанционно регулярные графы диаметра 2 называются также сильно регулярными).
Рассмотрим теперь подробнее класс графов Тервиллигера Г с р = 2 при условии, что они не являются кликовыми расширениями и Гх = 0. Окрестность вершины в графе из этого класса является графом Тервиллигера диаметра 2 с р = 1. Графы Тервиллигера диаметра 2 с р = 1, в свою очередь, представляют самостоятельный интерес и называются геодезическими графами диаметра 2 [1, Глава 1.17]. Некоторые свойства этих графов изучаются в четвертой главе диссертации.
Известны лишь три графа Тервиллигера с р = 2, все они дистанционно регулярны: граф икосаэдра с массивом псрессчениий {5,2,1; 1,2,5}, граф Доро {10,6,4; 1,2,5} и граф Конвея - Смита {10,6,4,1; 1,2,6,10}. В графе икосаэдра окрестность каждой вершины изоморфна пятиугольнику, а в двух других графах окрестность каждой вершины изоморфна графу Петерсена.
Пятиугольник и граф Петерсена являются представителями еще одного интригующего класса графов — сильно регулярных графов Мура |12). В этот класс входит также граф Хоффмана - Синглтона и гипотетический граф на 3250 вершинах, вопрос о существовании которого не решен [13].
14
Рис 0.3. Граф икосаэдра.
Икосаэдр является единственным связным локально пятиугольным графом [1, Теорема 1.1.4]. Связных локально иетерсеновых графов всего 3: по теореме Холла [1, Теорема 1.16.5] кроме указанных выше графов Доро и Конвея - Смита таким является также граф Т(7) (дополнительный граф к треугольному графу на 7 символах).
Теорема Холла классифицирует графы, в которых окрестность всякой Bej>-шины изоморфна графу Петерсена. В первой главе диссертации показано, что граф Тервиллигера, содержащий хотя бы одну вершину, окрестность которой изоморфна графу Петерсена, является графом Доро или графом Конвея Смита, либо совпадает с шаром радиуса 1 с центром в этой вершине.
Напомним некоторые другие результаты, в том числе характеризующие известные графы Тервиллигера с у, = 2.
Прежде всего, отметим популярную задачу классификации графов без 3-лап, т.е. без порожденных полных двудольных графов с долями порядка 1 и 3, в процессе решения которой графы с кликовыми //-подграфами рассматриваются как особый случай. Графы Тервиллигера без 3-лап были классифицированы В.В. Кабановым и A.A. Махневым в работе [14].
А. Юришич и Дж. Кулен [16] показали, что икосаэдр, графы Доро и Конвея - Смита являются единственными 1-однородными графами Тервиллигера с fi > 1. Напомним, что граф Г обладает свойством //-однородности, если для всех пар вершин х,у 6 Г, находящихся на расстоянии /г, всех индексов i,j = 0, ...,сі(Г) и всех вершин z Є ГДгг) П Г/(у) число вершин в ГДг) П Гі(х) П Tj(y) зависит только от г, j, но не от выбора вершин x,y,z с указанными свойствами. Очевидно, что 0-однородность эквивалентна дистанционной регулярности. К. Номура 115] показал, что 1-однородные графы содержатся в классе дистанционно регулярных графов.
15