Графы Тервиллигера в теории дистанционно регулярных графов тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Гаврилюк, Александр Львович

• Гаврилюк, Александр Львович
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Гаврилюк, Александр Львович

Введение

Определения и основные обозначения.

Обозначения

Определения свойств регулярности графов.

Определения семейств графов

Мотивация работы.

Общая характеристика работы.

1 Характеризации графов Тервиллигера

1.1 Вспомогательные результаты.

1.2 Проблема регулярности в регулярных графах Тервиллигера

1.3 Графы Тервиллигера с /а ^ 3.

1.3.1 Графы Тервиллигера с /л = 2.

1.3.2 Сильно регулярные графы Тервиллигера с /л = 2.

1.3.3 Графы Тервиллигера с ¡л = 3.

1.4 Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена.

1.5 Графы Тервиллигера с ^ = 4.

1.6 Неравенство Кулена - Пака и графы Тервиллигера.

1.7 Граница для коклик в ¿¿-подграфах.

2 Локальные характеризации некоторых графов

2.1 Вспомогательные результаты.

2.2 Дистанционно регулярные локально <5 графы.

2.3 Локально НоБъ графы.

2.3.1 Предварительное обсуждение.

2.3.2 Графы диаметра не больше 5.

2.3.3 Ограничение диаметра.

2.4 Возможные автоморфизмы дистанционно регулярных локально Новг графов

2.4.1 Предварительное обсуждение.

2.4.2 Массив пересечений {50,42,1,1, 2, 50}.

2.4.3 Массив пересечений {50,42,9,1, 2,42}.

2.4.4 Замечание о рациональных характерах в методе Хигмена 103 2.5 Графы, в которых окрестность каждой вершины изоморфна графу Гевиртца.

2.5.1 Предварительное обсуждение.

2.5.2 Редукция к графам диаметра, большего 3.

2.5.3 Графы большого диаметра.

3 Нереализуемость некоторых массивов пересечений

3.1 Вспомогательные результаты.

3.2 Массивы пересечений {55,36,11; 1,4,45} и

56,36,9; 1,3,48}.

3.3 Массив пересечений {45, 30,7; 1, 2, 27}.

3.3.1 Предварительное обсуждение.

3.3.2 Верно неравенство |L0| <7.

3.3.3 Верно неравенство |Lo| < 6.

3.3.4 Верно неравенство \Lq\ ф 5.

3.4 Массивы пересечений {52,35,16; 1,4, 28} и

69,48,24; 1,4,46}.

4 Графы Райзера и геодезические графы диаметра

4.1 Графы Райзера.

4.2 Бирегулярные геодезические графы диаметра

4.2.1 Вспомогательные результаты.

4.2.2 Случай нерегулярного графа В.

4.2.3 Случай регулярного графа В.

4.2.4 Некоторые результаты о несуществовании графов

Введение диссертации (часть автореферата) на тему «Графы Тервиллигера в теории дистанционно регулярных графов»

В диссертации проводится систематическое изучение класса графов Тервил-лигера и связанных с ним вопросов в теории дистанционно регулярных графов. Разработаны методы изучения локального строения графов Тервилли-гера, дистанционно регулярных графов с заданными окрестностями вершин, предложены доказательства несуществования дистанционно регулярных графов с некоторыми допустимыми массивами пересечений.

В этой главе приведены основные определения и обозначения, объясняется мотивация работы.

Определения и основные обозначения

В этом разделе собраны общие для всех глав обозначения и определения графов и их свойств. Наша терминология и обозначения в основном стандартны, см. монографию [1].

Обозначения

В работе рассматриваются только неориентированные графы без петель и кратных ребер. Пусть Г является таким графом. Для подмножества X вершин графа Г мы будем также через X обозначать подграф, индуцированный в Г множеством X. Соответственно число вершин в графе X обозначается через \Х\. Далее термин подграф всегда будет означать подграф, индуцированный множеством вершин.

Для пары вершин х,у £ Г таких, что в Г существует путь, соединяющий ж и у, через с!(ж, у) обозначается расстояние между х и у, т.е. длина кратчайшего пути между этими вершинами. Диаметром с1(Г) графа Г называется максимальное встречающееся расстояние между его вершинами. Вершины х, у с д.(х,у) = 1, т.е. соединенные ребром, называются смежными; смежность вершин также обозначается через х ~ у.

Для вершины х Е Г окрестностью £ в Г называется подграф, индуцированный множеством ее соседей (вершин на расстоянии 1 от х) и обозначаемый через Г(ж). Зачастую, если граф Г определен контекстом, окрестность вершины х обозначается через [ж]. Через х1 обозначается замкнутая окрестность или шар радиуса 1 с центром в х, т.е. х1 = {х} и [х]. Для подграфа X графа Г через X1- обозначим П^^я;-1-, т.е. в общем случае X1- % X.

Более общо, через Гг(х) обозначим подграф, индуцированный множеством вершин на расстоянии г от х. В частности, [ж] = Г(ж) = Г^ж). Для множества вершин X графа Г через Г(Х) обозначим множество вершин из Г \ Х: имеющих хотя бы одного соседа в X.

Степенью или валентностью вершины х называется количество ее соседей, т.е. число |Г(х)|. Если граф Г определен контекстом, то степень вершины х обозначается через кх. Граф Г называется регулярным степени к, если степень каждой его вершины равна к. Граф называется бирегулярным, если в нем встречаются вершины точно двух различных степеней.

Пусть Т — некоторый класс графов. Граф называется локально ^-графом, если окрестность всякой его вершины изоморфна некоторому графу из Т.

Для вершин ж, у, находящихся на расстоянии 2 в Г, подграф Г (ж) П Г(у) называется ¡1-подграфом вершин х,у. Скажем, что для графа Г определено число /¿(Г), если для любых двух вершин х, у Е Г, находящихся на расстоянии 2, верно равенство |Г(а;) П Г(?/)| = /¿(Г).

Для пары смежных вершин х, у подграф Г(ж)ПГ(?/) называется \-подграфом вершин х,у. Если граф Г определен контекстом, то число вершин в Л-подграфе вершин х,у обозначается через Хху.

Матрицей смежности графа Г называется (ОД)-матрица А = АТ размера |Г| х |Г|, строки и столбцы которой индексированы множеством вершин Г и (х, у)-элемент А равен 1, если х ~ у, и равен 0, если х ф у.

Спектром графа называется спектр его матрицы смежности. Спектр записывается в виде ., где в(г означает, что собственное значение 6г имеет кратность /г.

Два графа, имеющие одинаковый спектр, называются изоспектральными. Из существования изоморфизма между графами следует их изоспектраль-ность; обратное в общем случае неверно. Пусть графы Г1 и Г2 на V вершинах имеют матрицы смежности Ах и А2 соответственно, — матрица порядка г>, состоящая целиком из единиц. Если матрицы уЗп — и уЗп — А2 (обобщенные матрицы смежности графов, см. [2]) имеют равные спектры для любого у Е К, то графы Г1 и Г2 называются К-изоспектральными.

Для графов X, У с У(Х) П У(У) = 0 через X © V обозначим граф, называемый прямой суммой X и У, полученный объединением графов X и У и добавлением ребер, соединяющих все вершины из X со всеми вершинами из У.

Для графа Г через Аи^Г) обозначается группа всех его автоморфизмов. Для элемента д Е Аи^Г) через Р1х(д) обозначается подграф вершин из Г, неподвижных под действием д.

Определения свойств регулярности графов

Пусть Г является связным графом диаметра Если вершины х, у находятся на расстоянии то через Ьг(х, у) (через сг(х, у)) обозначим число вершин в подграфе Гг+1(х) П Г(у) (соотв. Гг1(а;) П Г(у)). Здесь мы полагаем Г1(ж), 1^+1(2;) пустыми множествами и Го(ж) = {ж}.

Граф Г называется дистанционно регулярным с массивом пересечений

ЬоМ, ■ ■ ■ ■ ■ • ,с<*}> если верны равенства Ьг(х,у) — Ьг и сг(х,у) = сг для любых вершин х,у, находящихся на расстоянии г в Г, и для любого 0 ^ г ^ с?. Положим также аг = Ьо — Ьг — Съ. Заметим, что для дистанционно регулярного графа число 6о равно степени к графа, с\ = 1, С2 = /¿(Г) и = со = 0.

Дистанционно регулярный граф — единственный, если любой дистанционно регулярный граф с таким же массивом пересечений ему изоморфен.

В дистанционно регулярном графе для любых 0 ^ г^Л ^ ¿¿и любых вершин х, у, находящихся на расстоянии I, количество вершин г, находящихся одновременно на расстоянии г от о; и на расстоянии у от у, т.е. число |Гг(:г) П не зависит от выбора вершин х, у и равно р\у Числа р1 называются числами пересечений. В частности, для любой вершины х € Г подграф Тг(х) содержит одно и тоже число вершин, равное кг = р^г, 1 ^ г ^ с?, и является регулярным графом степени аг. Заметим, что по определению аг := ргг1, Ъг

Рг+1,1' :== Рг-1,1

Ввиду [1, Предложение 4.1.6] числа пересечения Ъг, сг удовлетворяют следующим условиям:

Ь0> Ь1 ^ . ^ 1 = с: ^ с2. ^ с^, Ь3, если I + j ^ (1, а по [1, Лемма 4.1.7] числа пересечений р1 могут быть вычислены по следующим соотношениям: р[3 '~р\г; Р1г0 '■= р{Л+1 := 0, := р[,1 ■= Щ, Р1,1+1 — Ьи

Pj+1, cj+1 plj,i-ibi-i +Plj,iiai - аз) +Pl3,i+lCi+l в частности, все числа пересечений могут быть вычислены по числам из массива пересечений.

Дистанционно регулярный граф диаметра 2 с массивом пересечений {6q, Ь\] съ сг} обычно называется сильно регулярным графом с параметрами (v, к, А, /л), где v := |Г|, к := 60, А := 60 - &i - 1 и /1 := с2.

Вполне регулярным графом с параметрами (v, А:, Л, fi) называется граф Г, содержащий v вершин, регулярный степени к, в котором |Pi(а;) П Гх(?/)| = Л для любой пары смежных вершин а;, у, и |Pi(o;) П Гх(г/)| = р, для любой пары вершин х, у с у) = 2. (Таким образом, сильно регулярный граф является вполне регулярным графом диаметра 2.)

Прямоугольным соотношением в дистанционно регулярном графе называется равенство к(к - ai - 1) = к2с2, получаемое подсчетом двумя способами числа ребер между первой и второй окрестностями вершины. В сильно регулярном графе это равенство принимает вид к{к - Л - 1) = (v - к - 1 )fjL.

Матрица смежности дистанционно регулярного графа диаметра d имеет точно d + 1 различных собственных значений &0 = > > • • • > Qd- Ввиду [1, Раздел 4.1.В] различные неглавные собственные значения дистанционно регулярного графа (т.е. отличные от его валентности) являются собственными значениями следующей матрицы: -г, bi О О

Ь\-С2 Ь2 О с2 к -Ь2- с3 Ь3

О сз к — 63 — С4 64 V

-с 1 С\ О О О О О к

Cd

0 О О О о bd-i

1 к - 6di - cd

По [1, Теорема 4.1.4] кратность собственного значения в вычисляется по формуле т := v где иг(6) := и>г(0)/(6о • • • 1) и щ(0) 1> и многочлены гиг(х) определяются следующим образом: ъио(х) := 1, ^(ж) := ж, «^(ж) := (х - аг)гиг(ж) - сД 110,-1(2;).

Собственные значения сильно регулярных графов, как правило, целые. Исключение составляют так называемые графы в половинном случае, имеющие параметры (4/л + 1,2/х, ¡1, — I) (см. лемму 2.1.1 в работе).

Граф диаметра с1 называется антиподальным, если отношение на множестве вершин совпадать или находиться на расстоянии (1 является отношением эквивалентности. Антиподальный граф Г называется г-накрытием графа Е, если всякий антиподальный класс в Г содержит точно г вершин и его фактор-граф по указанному отношению эквивалентности изоморфен графу Е.

Неполный граф Г называется графом Тервиллигера, если определено число /¿(Г) и любой /¿-подграф в Г является кликой.

При изучении графов Тервиллигера будут полезны следующие определения и обозначения. Для вершины х графа Г подграф [ж]-1 назовем ядром вершины х и обозначим его порядок через Ьх, если граф Г ясен из контекста. Вершина х называется редуцированной, если [гг]1 = {ж}, и нередуцированной в противном случае. Таким образом, ядро х является максимальным по включению множеством вершин, замкнутая окрестность которых содержит окрестность х.

Если Г — граф Тервиллигера, то нас будет также интересовать окрестность вершины за вычетом ее ядра, т.е. подграф

Дг^ГхфХ^Ос)-1), обозначемый через Ах, если граф Г ясен из контекста.

Для произвольного графа Г определим его а-кликовое расширение как граф Г, полученный заменой каждой вершины х графа Г на клику Ьх С Г порядка а так, что Ьх П Ьу = 0, если х ф у, и попарным соединением всех вершин из двух таких клик ЬХ,ЬУ, если их прообразы ж, у смежны в Г.

Определим отношение эквивалентности = на множестве вершин графа Г по правилу х = у х1- = у1. Фактор-граф графа Г по отношению = будет обозначаться через Г.

Определения семейств графов

Напомним, что с-кликой С графа Г называется полный подграф (т.е., граф, любые две вершины которого смежны) графа Г, содержащий точно с вершин.

Подграф С называется кликой, если он является с-кликой для некоторого с.

Кокликой С графа Г называется непустой индуцированный подграф в Г с пустым множеством ребер. Коклика называется с-кокликой, если она содержит точно с вершин.

Клика или коклика в графе называется максимальной, если она является максимальной по включению.

Полный многодольный граф с п долями порядков 7П1,., тп обозначается через Полный двудольный граф К\,т называется т-звездой или тлапой.

Для целых т > 0, п > 0 определим т х п-решетку как граф, множеством вершин которого являются все пары вида (г, 1 ^ г ^ га, 1 ^ ^ ^ п, и различные пары (г,^) и (г',/) смежны, если и только если г = %' или 3 = у'.

Для натурального числа п п-циклом или п-узольником называется граф на п вершинах х\,., хп, в котором Х{ ~ £¿+1, г = 1,., п и х\ ~ хп.

Граф Петерсена является единственным сильно регулярным графом с параметрами (10,3,0,1), граф Хоффмана - Синглтона является единственным сильно регулярным графом с параметрами (50,7,0,1). Сильно регулярные графы с параметрами Л = 0, ц — 1 называются графами Мура.

Заметим, что в сильно регулярном графе с параметрами (г>, к, А, 1) окрестность любой вершины состоит из г = к/(Х + 1) изолированных й-клик, где в = А + 1. Обозначим через г) класс сильно регулярных графов с параметрами (г>, г в, в — 1,1). В частности, класс сильно регулярных графов Мура совпадает с классом ^(1, г) (и г е {2,3,7, 57} ввиду результата [12]). Примеры графов из класса Т(з,г) при й > 1 не известны.

Графы икосаэдра, Конвея - Смита, Доро являются единственными дистанционно регулярными графа с массивами пересечений {5, 2,1; 1, 2, 5}, {10, 6,4,1; 1, 2, б, 10} и {10,6,4; 1,2, 5} соответственно. Определения также упоминаемых в работе графов Хэмминга, Джонсона и Грассмана могут быть найдены в [1, Глава 9].

Мотивация работы

Объектами исследования в настоящей работе являются дистанционно регулярные графы и графы с некоторыми более специфическими условиями такими, например, как запрет на подграфы определенного вида.

Напомним одно из нескольких эквивалентных определений дистанционной регулярности графа. Граф Г называется дистанционно регулярным, если для любого I = 0,. ,(1 с1(Г) и любой пары вершин х, у, находящихся на расстоянии I в Г, множество Гг(а:) П Г7(у) содержит точно р1 вершин, причем число р\ зависит только от г,.?,/, но не от выбора конкретной пары вершин 7 х,у, находящихся на расстоянии I. Числа р называются числами пересечений графа.

Такое определение позволяет понять, что свойство дистанционной регулярности является обобщением дистанционной транзитивности, т.е. транзитивности группы автоморфизмов графа на множестве равноудаленных пар вершин.

Классическими в некотором смысле примерами дистанционно регулярных (и дистанционно транзитивных) графов являются графы Хэмминга и графы Джонсона, см. [1, Глава 9]. Эти семейства графов связывают теорию дистанционно регулярных графов соответственно с алгебраической теорией кодирования и теорией блок-схем (дизайнов), что было показано в диссертации Ф. Дельсарта [3]. Существует, однако, гораздо больше подобных связей: с теорией конечных групп, конечными геометриями, схемами отношений, ортогональными многочленами. В последнее время интерес к дистанционно регулярным графам наблюдается со стороны задач комбинаторной оптимизации, теоретической физики и квантовых вычислений, см. обзор [4]. В качестве завершения вступления можно сказать, что дистанционно регулярные графы, методы их исследования (комбинаторные и алгебраические) позволяют единообразно изучать объекты из различных областей дискретной математики и алгебры.

Одной из центральных задач в теории дистанционно регулярных графов является классификация (^-полиномиальных дистанционно регулярных графов или, в других терминах, (Р и (5)-полиномиальных схем отношений.

Решение этой задачи стимулирует исследование более общих вопросов теории (некоторые из них также рассматриваются в диссертациии): существование и единственность графов с заданными параметрами, изучение строения графов известных семейств.

Задача классификации (^-полиномиальных дистанционно регулярных графов была сформулирована в известной монографии Баннаи и Ито [5] в начале 1980-х годов, и ее важность объясняется, с одной стороны, возможным новым подходом к классификации конечных простых групп, поскольку каждая конечная простая группа за исключением спорадических групп и групп малого лиевского ранга является группой автоморфизмов определенного полиномиального дистанционного регулярного графа. С другой стороны, известно всего 16 семейств примитивных дистанционно регулярных графов неограниченного диаметра, которые, как правило, имеют естественные описания на языке групп или конечных геометрий.

На сегодняшний день, пожалуй, наибольший вклад в решение упомянутой задачи классификации принадлежит П. Тервиллигеру. Класс графов, названный его именем и вынесенный в название диссертационной работы, возник в связи со следующей гипотезой Баннаи и Ито, также сформулированной в монографии [5]: для каждого к ^ 3 существует лишь конечное число конечных дистанционно регулярных графов валентности к.

Данная гипотеза верна в предположении дистанционной транзитивности графа, см. [6]. Ее сложность в общем случае можно пояснить следующим образом. Известно [1, Предложение 4.1.6], что в массиве пересечений любого дистанционно регулярного графа выполняются неравенства

Ьг > Ьг+1, сг > сг 1, 0 < г < т.е. последовательности {6г}^=о, (сг}^=1 не возрастают и не убывают, соответственно.

Поскольку Ьо — это валентность графа, то выполнение неравенства Ьг > Ьг+1 (или с^ > Сг—х) для всех г означало бы, что граф имеет диаметр не больше 60 и тогда очевидно, что число графов с ограниченными валентностью и диаметром конечно. Поэтому проблема заключается в доказательстве строгих неравенств или ограничении числа повторения нестрогих неравенств

Ъг ^ £>г+Ъ Сг ^ Сг1.

В работе [7] Тервиллигер показал, что для массива пересечений дистанционно регулярного графа, содержащего порожденный 4-цикл, выполняются неравенства сг - Ьг > сг 1 - Ъг-1 + ах + 2, 1 < г ^ с?, где по определению аг = £>о — Ьг — сг.

Используя эти неравенства, можно показать, что для дистанционно регулярного графа, содержащего 4-цикл, верна граница Тервиллигера [1, Следствие 5.2.2]: . Ь0 + сл 2 Ь0 а ^-- ^ц + 2 ах+ 2' и таким образом гипотеза Баннаи и Ито верна в этом случае.

Дистанционно регулярные графы, не содержащие 4-циклов, были названы графами Тервиллигера. Затем условие дистанционной регулярности было заменено на гораздо более слабое условие [1, Глава 1.16]: неполный граф Г называется графом Тервиллигера, если для любой пары его вершин х,у, находящихся на расстоянии 2, подграф Г^ж) П Г\(у), индуцированный общими соседями вершин х,у, является полным графом на ¡1 вершинах, где /1 = /1(Г) — это некоторая константа, зависящая от Г. В дальнейшем, подграф Г1(ж)ПГ1(?/) для вершин ж, у, находящихся на расстоянии 2 в произвольном графе Г, будем называть /х-подграфом. По устоявшейся традиции символ /х используется и для обозначения такого подграфа, и для обозначения его мощности как числового параметра графа Г.

Стоит заметить, что для дистанционно регулярных графов, имеющих кратчайший цикл заданной длины д (т.е. с заданным обхватом д), гипотеза Баннаи - Ито также верна в силу границы Иванова [1, Глава 5.9]: ^ д^0'1.

Таким образом, доказательство гипотезы сводится к оценке обхвата графа как функции от его валентности, что является довольно тяжелой задачей исследования спектров дистанционно регулярных графов с массивами пересечения специфического вида. Спустя практически 25 лет с момента формулировки гипотезы ее доказательство было аннонсировано коллективом авторов под руководством Дж. Кулена [8].

Гипотеза Баннаи и Ито не связана напрямую с упомянутой выше задачей классификации (^-полиномиальных дистанционно регулярных графов, но результаты, полученные на пути доказательства первой, работают в процессе решения второй; см., например, статью [9], в которой по массивам пересечений охарактеризованы семейства графов свернутого половинного куба, половинного куба и свернутых графов Джонсона.

Класс графов с запрещенными 4-циклами активно изучается в теории графов (прежде всего, в экстремальной теории графов, изучающей графы с запрещенными подграфами), см., например, [10], но в теории дистанционно регулярных графов эти графы привлекают внимание исследователей не только как исключение в границе Тервиллигера, но и в связи со следующим курьезным фактом: в своей работе [7] Тервиллигер рассмотрел графы без условия дистанционной регулярности (т.е. называемые нами сейчас графами Тервиллигера) и сформулировал сильное утверждение, доказательство которого оказалось некорректным, см. [1, Предложение 1.16.1].

Прежде, чем его сформулировать, отметим две конструкции графов Тервиллигера. Первая из них определяется через операцию кликового расширения. Действительно, если Г — это граф Тервиллигера с (1 — 1 (класс таких графов не поддается описанию), то операция о;-кликового расширения позволяет построить граф Тервиллигера с произвольным заданным /л = а > 1.

Операция прямой суммы графов, т.е. попарного соединения вершин из двух графов с непересекающимися множествами вершин, позволяет также получать графы Тервиллигера с произвольно заданным у, если в качестве слагаемых прямой суммы выступают граф Тервиллигера диаметра 2 с параметром // и клика порядка /л — //.

Описанные выше конструкции графов Тервиллигера с \х > 1 не представляют интереса. Мы исключим эти случаи из общего рассмотрения следующим образом. Понятно, что в графе Тервиллигера Г, полученном как а-кликовое расширение графа Тервиллигера Г с у = 1, для всех вершин х выполнено неравенство ^(ж)-1! ^ м(Г) (неравенство может быть строгим для вершин из Г, окрестности которых являются кликами). Тогда мы будем рассматривать графы Тервиллигера Г с условием, что в них найдется вершина х, для которой ^(гг)-1! < /¿(Г). Дополнительно к этому, условие Г-1 = 0 исключает из рассмотрения прямые суммы графов Тервиллигера и клик.

Такие ограничения не исключают из рассмотрения кликовые расширения графов Тервиллигера с у = 2, например, или любым другим // > 1. Но класс графов Тервиллигера существенно меняется при переходе от графов с у = 1 к графам с ¡1 > 1: для у > 2 не известны примеры графов Тервиллигера Г с Г-1 = 0, не являющихся кликовыми расширениями, а для у = 2 известны только три таких графа, которые будут описаны ниже.

Теперь упомянутое выше утверждение Тервиллигера [7] можно сформулировать следующим образом: в регулярном графе Тервиллигера Г с у > 1, содержащем хотя бы одну вершину х с ^хОг)^ < у, подграфы Ау регулярны для всех вершин у £ Г.

Заметим, что подграф Ау является также графом Тервиллигера, либо объединением изолированных клик, либо пустым множеством. Этот естественный факт позволяет эффективно использовать индуктивные рассуждения при изучении графов Тервиллигера.

Поскольку доказательство из [7] оказалось некорректным, в монографии [1, стр. 35] утверждение Тервиллигера было записано как нерешенная проблема. Одним из основных результатов первой главы диссертации является положительное решение этой проблемы. В частном случае /1 = 2 эта проблема была ранее решена в работе A.A. Махнева [11].

Справедливость доказанного утверждения указывает на очень жесткое локальное строение регулярных графов Тервиллигера, поскольку подграфы Ау имеют диаметр 2, а в силу предложения 1.16.2 из [1] регулярные графы Тервиллигера диаметра 2 являются кликовыми расширениями дистанционно регулярных графов (дистанционно регулярные графы диаметра 2 называются также сильно регулярными).

Рассмотрим теперь подробнее класс графов Тервиллигера Г с fi = 2 при условии, что они не являются кликовыми расширениями и Г-1 = 0. Окрестность вершины в графе из этого класса является графом Тервиллигера диаметра 2 с /i = 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].

Рис 0.3. Граф икосаэдра.

Икосаэдр является единственным связным локально пятиугольным графом [1, Теорема 1.1.4]. Связных локально петерсеновых графов всего 3: по теореме Холла [1, Теорема 1.16.5] кроме указанных выше графов Доро и Кон-вея - Смита таким является также граф Т(7) (дополнительный граф к треугольному графу на 7 символах).

Теорема Холла классифицирует графы, в которых окрестность всякой вершины изоморфна графу Петерсена. В первой главе диссертации показано, что граф Тервиллигера, содержащий хотя бы одну вершину, окрестность которой изоморфна графу Петерсена, является графом Доро или графом Конвея Смита, либо совпадает с шаром радиуса 1 с центром в этой вершине.

Напомним некоторые другие результаты, в том числе характеризующие известные графы Тервиллигера с ß — 2.

Прежде всего, отметим популярную задачу классификации графов без 3-лап, т.е. без порожденных полных двудольных графов с долями порядка 1 и 3, в процессе решения которой графы с кликовыми /¿-подграфами рассматриваются как особый случай. Графы Тервиллигера без 3-лап были классифицированы В.В. Кабановым и A.A. Махневым в работе [14].

А. Юришич и Дж. Кулен [16] показали, что икосаэдр, графы Доро и Конвея - Смита являются единственными 1-однородными графами Тервиллигера с [I > 1. Напомним, что граф Г обладает свойством /¿-однородности, если для всех пар вершин х, у € Г, находящихся на расстоянии h, всех индексов i,j = 0, .,d(r) и всех вершин г 6 ГДх) П Г j(y) число вершин в Г^г) П ГДа:) П Tj(y) зависит только от i,j, но не от выбора вершин x,y,z с указанными свойствами. Очевидно, что 0-однородность эквивалентна дистанционной регулярности. К. Номура [15] показал, что 1-однородные графы содержатся в классе дистанционно регулярных графов.

Дж. Кулен и С. Банг [17] доказали, что для всякого натурального числа т существует лишь конечное число дистанционно регулярных графов Тер-виллигера с С2 ^ 2 и наименьшим собственным значением графа Ой ^ — т (этот результат является частным случаем их более общего результата, см. ниже, о негеометрических дистанционно регулярных графах, который, в свою очередь, является обобщением теоремы Ньюмайера о сильно регулярных графах). Заметим, что по определению в дистанционно регулярном графе Тер-виллигера Г число пересечения С2 равно /¿(Г).

В [18] Дж. Кулен и др. показали, что для всякого вещественного числа Т ^ 1 существует конечное множество дистанционно регулярных графов Тервиллигера с С2 > 1 и вторым собственным значением 0\ ^ ^ — 1 (известно, см. [1, Теоремы 4.4.3, 4.4.11], что для любого дистанционно регулярного графа выполняется неравенство 0\ ^ Ъ\ — 1, и все графы, для которых достигается равенство в последнем неравенстве, охарактеризованы). В той же работе ее авторы доказали, что дистанционно регулярный граф Тервиллигера с С2 > 1 и ^ ^ — 1 является икосаэдром, графом Доро или Конвея - Смита.

В 2010 г. в [19] Дж. Кулен и Дж. Пак доказали неравенство, которое при условии С2 > 1 связывает числа пересечения С2,аг,6о и размер коклики 5 в окрестности вершины дистанционно регулярного графа:

5(ах + 1) - 60 й) ' и заметили, что граф является графом Тервиллигера, если для некоторого ,5 достигается равенство и любая 2-лапа графа содержится в й-лапе.

Еще одним результатом первой главы диссертации является новая ха-рактеризация известных дистанционно регулярных графов Тервиллигера с С2 > 1 как единственных графов, для которых достигается равенство в данном неравенстве Кулена - Пака.

Описанные выше результаты и характеризации известных (дистанционно регулярных) графов Тервиллигера, довольно различные по своей природе, свидетельствуют в пользу гипотезы:

Графы икосаэдра, Доро или Конвея - Смита являются единственными нетривиальными графами Тервиллигера с /л > 1.

В процессе решения проблемы регулярности в регулярных графах Тервиллигера был разработан подход к изучению локального строения графов Тервиллигера с заданным параметром /х. На основе этого подхода в первой главе диссертации получено описание локального строения гипотетических графов Тервиллигера с параметром р Е {3,4}.

В связи с тем, что известные дистанционно регулярные графы Тервилли-гера — это локально графы Мура: пятиугольник или граф Петерсена, естественным является вопрос о существовании графов (и, в частности, графов Тервиллигера), окрестность каждой вершины в которых является графом Хоффмана - Синглтона, третьим известным графом Мура. Вторая глава диссертации посвящена, в основном, изучению этого вопроса.

Граф Хоффмана - Синглтона является единственным сильно регулярным графом с параметрами (г>, к, Л, ¡i) = (50, 7,0,1), где v — число вершин в графе, к — валентность, Л (соотв. ¡л) — число общих соседей пары смежных (соотв. несмежных) вершин. В обозначениях дистанционно регулярного графа имеем к = bo, Л = ¡л = С2.

Задача локальной характеризации, т.е. определения графа или класса графов по заданным окрестностям его вершин, является одной из наиболее популярных в теории графов [20] и, как правило, решается тем сложнее, чем более "разреженным" (sparse) в смысле соотношения количества ребер и количества вершин является заданный локальный граф. Граф Хоффмана - Синглтона можно отнести к разреженным графам. Дополнительное ограничение в виде предположения дистанционной регулярности искомого графа могло бы помочь в решении задачи (и не было бы выхолащивающим, поскольку и локально пятиугольники, и локально петерсоновы графы являются дистанционно регулярными). Далее граф Хоффмана - Синглтона будем обозначать HoSi.

Пусть граф Г дистанционно регулярен и окрестность каждой его вершины является сильно регулярным графом с параметрами (ь,к,Х,/л). Первые элементы массива пересечений Г определяются локальным строением: &о = v (степень вершины в Г), Ъ\ — v — к — 1 (т.е. а\ = к). Но уже параметр С2 может принимать несколько значений (несложно показать, что для пары вершин х,у 6 Г, находящихся на расстоянии 2, подграф ГДж) П Т\(у) будет регулярным графом степени (л, и С2 делит 6o&i). В частности, если окрестность каждой вершины в Г является графом HoSi, то (г/, к', А', //) = (50, 7,0,1) и к = bo = 50, b\ =42, Л = 7, сг|42 • 50 и ¿¿-подграфы в Г состоят из изолированных ребер (регулярны степени 1).

III d(T) < ? к = 6П = 50

Рис 0.4. Иллюстрация, поясняющая параметры локально НоБг-графов.

В монографии [1, стр. 36] была сформулирована проблема существования дистанционно регулярных локально HoSi графов, в частности, графов с массивами пересечений {50,42,9; 1, 2,42} и {50,42,1; 1, 2,50} — ясно, что такие графы могли бы быть локально HoSi графами, однако, полный перечень подходящих массивов пересечений не был известен. Во второй главе диссертации показано, что дистанционно регулярный локально HoSi граф должен иметь один из двух указанных выше массивов пересечений и, следовательно, оказывается графом Тервиллигера.

К сожалению, графы с указанными массивами пересечений (если бы существовали) не обладают никакими интересными свойствами (такими как Q-полиномиальность, например), которые могли бы помочь в дальнейшем продвижении — построении графов или доказательстве их несуществования. На данный момент не получается даже показать, что такие графы действительно были бы локально HoSi. С другой стороны, в пользу несуществования говорит еще один результат, полученный во второй главе диссертации, — группы автоморфизмов этих гипотетических графов не могут быть вершинно-транзитивными (при том, что граф икосаэдра, графы Доро и Кон-вея - Смита являются даже дистанционно-транзитивными). В доказательстве этого результата использовался т.н. метод Хигмена, развитый в работах A.A. Махнева и др. [21].

Одна из подзадач, возникающая при классификации дистанционно регулярных графов Г с заданным локальным строением, заключается в хорошем ограничении диаметра Г. Если известно, что d(r) ^ D для сравнительно небольшого числа D, то число возможных массивов пересечений для Г длины не более чем D с известными начальными элементами &о и конечно.

Поэтому, в крайнем случае, можно перебрать все такие массивы и найти среди них допустимые, т.е. удовлетворяющие всем известным ограничениям.

Если Г содержит 4-цикл, то для оценки диаметра можно использовать границу Тервиллигера, не очень эффективную, если параметр а\ мал в сравнении с Ьо. Если же Г может не содержать 4-циклов, то граница Иванова дает оценку диаметра, экспоненциально зависящую от 6о, а некоторые уточнения этой границы, например, Хираки - Кулена [22], — зависимость вида ¿jj.

Таким образом, рассматриваемая задача классификации локально HoSi графов разбивается на 2 различных случая: с2 > 2 (в этом случае любой /1-подграф в Г состоит из с2/2 изолированных ребер, поэтому Г содержит 4-цикл, т.е. не является графом Тервиллигера) и с2 = 2 (в этом случае ц-подграф состоит из одного ребра, т.е. 2-клики). Случай с2 > 2, как было показано A.A. Махневым [23], не возможен.

Во второй главе диссертации предложены два новых способа оценки диаметра локально HoSi графов.

Один из них основан на том, что матрица смежности графа HoSi имеет спектр 71, 228, — З21. Теперь, рассматривая изолированные подграфы С := Гг1(х) nTi(y) и В Гг+1(а;)ПГ^у) для пары вершин х,у Е Г, находящихся на расстоянии г ^ 2, по теореме о переплетении спектров [25, Теорема 2.5.1] имеем, что максимальное собственное значение по крайней мере одного из графов В или С не больше 2 (т.е. второго по величине собственного значения графа HoSi). По теореме Смита [1, Теорема 3.2.5] граф, максимальное собственное значение которого не превосходит 2, является объединением изолированных подграфов из графов А, где X Е {An,Dn,EQ,E7:E$,}. Далее, комбинаторными рассуждениями удается показать, что в случае d(T) ^ 8и граф В, и граф С содержат порожденный подграф, не являющийся подграфом из X, что приводит нас к противоречию.

Второй подход основан на комбинации границы Ван Дама - Хэмерса [24] и обращении т.н. границы Таннера, известной в теории графов-экспандеров [25, Предложение 4.5.1] (точные формулировки см. в разделе 2.2 данной работы).

Оба подхода дают одинаковую оценку d(T) ^ 7, что является, по всей видимости, просто случайным совпадением. При этом первый способ не предполагает дистанционной регулярности графа Г и может быть применен к любому графу, окрестность каждой вершины в котором имеет второе по величине собственное значение 2 (это наблюдение форсировало цикл работ по изучению графов с таким свойством [26]). В свою очередь, ограничение, полученное из границы Таннера, может быть применено к изучению только дистанционно регулярных графов, но с более широким классом локальных подграфов.

Разработанные методы оценки диаметра графов также применяются во второй главе диссертации для изучения дистанционно регулярных графов, окрестность каждой вершины в которых изоморфна графу Гевиртца — сильно регулярному графу с параметрами (56,10,0, 2). Эта задача представляет интерес в связи с работой [27].

Как упоминалось ранее, одним из наиболее общих в теории дистанционно регулярных графов является вопрос существования графа с заданным массивом пересечений. Известно, см. [1, Глава 5], множество необходимых арифметических условий, заключающихся, как правило, в целочисленности некоторых выражений или выполнении некоторых неравенств, зависящих от элементов массива пересечений. Эти условия возникают из комбинаторных или алгебраических соображений. Тем не менее, существует и достаточно большое количество массивов пересечений и их параметризованных бесконечных серий, удовлетворяющих всем известным необходимым условиям, но существование соответствующих графов не известно. В этом контексте каждое доказательство несуществования (или построение нового примера) графа является оригинальным результатом, для получения которого приходится разрабатывать новые подходы — отметим работы Д.Г. Фон-дер-Флаасса [28, 29], К. Кулсета [30], К. Кулсета и А. Юришича [31], А. Юришича и Я. Видали [32].

Третья глава диссертации посвящена доказательству нереализуемости в виде графов пяти массивов пересечений, удовлетворяющих всем известным необходимым условиям. Некоторые из этих массивов были просто отмечены как допустимые в известном списке [1, Глава 14], а некоторые были получены в результате решения различных классификационных задач. Но наше внимание к этим массивам было обусловлено уже упоминавшимся неравенством Кулена - Пака [19]. Фактически, данное неравенство позволяет ограничить сверху порядок максимальной коклики в окрестности вершины дистанционно регулярного графа с заданным массивом пересечений. Если этот порядок оказывается сравнительно небольшим числом, то можно надеяться, что дальнейший комбинаторный анализ приведет к противоречию или явному определению окрестности. Это рассуждение было отправной точкой для исследований.

Массивы пересечений {55,36,11,1; 4,45} и {56, 36,9; 1,3,48} были первыми, на которых данный подход был опробован. Легко видеть, что порядок коклики в окрестности вершины графа в обоих случаях не превосходит 3 по неравенству Кулена - Пака. С другой стороны, в случае массива {55, 36,11,1; 4,45} можно показать, что известное неравенство Брукса [25, Предложение 3.6.1] дает число 3.5 как нижнюю оценку порядка ко-клики в окрестности вершины, что приводит к противоречию. Для массива {56,36,9; 1,3,48} потребовался более тонкий комбинаторный анализ окрестности вершины. Заметим, что одновременно и независимо несуществование тех же самых графов было показано С. Банг [33].

Напомним [1, Предложение 4.4.6(г)] границу Хоффмана - Дельсарта, согласно которой клика в дистанционно регулярном графе с наименьшим собственным значением — га и валентностью к имеет порядок не более чем 1 + ^-Клика называется кликой Дельсарта, если ее порядок достигает этой границы. Дистанционно регулярный граф называется геометрическим, если в нем существует множество £ клик Дельсарта такое, что любое ребро графа принадлежит единственной клике из £. Геометрическими являются многие "классические" семейства графов: Хемминга, Джонсона, Грассмана, двойственных полярных пространств, отношений билинейных форм и др. Название "геометрический" обусловлено тем, что множество вершин такого графа, рассматриваемое как множество точек, и множество клик Дельсарта, рассматриваемых как прямые, образуют систему инцидентности на точках и прямых, удовлетворяющую аксиомам частичной геометрии [34].

В работе [17] Дж. Кулен и С. Банг доказали, что для всякого натурального числа т существует лишь конечное число негеометрических дистанционно регулярных графов с С2 ^ 2 и наименьшим собственным значением графа ба, ^ —т. Таким образом, представляет интерес задача классификации геометрических дистанционно регулярных графов с заданным наименьшим собственным значением = —т, т ^ 2.

Классификация геометрических дистанционно регулярных графов с наименьшим собственным значением —2 следует из результатов П. Камерона, Дж. Геталса, Я. Зейделя, Е. Шульта [35] и А. Блокхьюза, А.Е. Браувера [36].

В 2011 г. работе [33] С. Банг классифицировала геометрические дистанционно регулярные графы с наименьшим собственным значением —3. В ее теореме утверждается, что такой граф имеет массив пересечений, принадлежащий одному из 12-ти параметризованных семейств массивов пересечений. Одно из семейств имеет вид

За + 3, 2а + 2, а + 2 - /?; 1,2,3/?}, (1) где а ^ /5 > 1 — целые числа.

Из списка [1, Глава 14] этому семейству принадлежат только массивы графов Хэмминга Н(3, ск + 2) (при /3 = 1), графа Дуба (с тем же массивом, что и

Н(3,4)) и массив {45, 30, 7; 1,2, 27} (при о; = 14, /5 = 9), существование графа для которого не было известно. Вопрос существования графа с массивом {45,30,7; 1, 2, 27}, таким образом, является частью вопроса: существуют ли дистанционно регулярные графы с массивом пересечений (1) при /3 > 1?

В 2012 г. Дж. Кулен и С. Банг [37] показали, что ответ на этот вопрос отрицателен за исключением случая ос — 14, ¡3 = 9, причем в этом случае их метод принципиально не работает. В третьей главе диссертации показано несуществование графов с массивом пересечений {45,30,7; 1,2,27}, что совместно с результатом Кулена и Банг дает ответ на указанный выше вопрос и, таким образом, уточняет результат [33].

Для доказательства несуществования графов с массивами пересечений {52,35,16; 1,4, 28} и {69,48,24; 1,4,46} потребовалась комбинация различных утверждений, ограничивающих порядки клик и коклик в дистанционно регулярном графе. Сначала, используя границу Кулена - Пака, мы показываем, что порядок максимальной коклики в окрестности вершины не превосходит 5 (для обоих массивов). Отсюда следует, что /¿-подграф не содержит 3-х попарно несмежных вершин (в противном случае граф содержит клику, порядок которой превышает границу Хоффмана - Дельсарта). Наконец, более тонкими комбинаторными рассуждениями мы показываем, что ^-подграф не может содержать даже 2-х попарно несмежных вершин. Таким образом, граф является графом Тервиллигера, что быстро приводит к противоречию с классификацией графов Тервиллигера с ¡л = 4.

Заметим, что граф с массивом пересечений {69,48, 24; 1,4, 46} фигурирует в работе [19] как один из возможных т.н. графов Шиллы.

В четвертой и заключительной главе диссертации рассматриваются вопросы, несколько выходящие за рамки теории дистанционно регулярных графов.

Ранее мы определяли геодезические графы диаметра 2 как графы Тервиллигера диаметра 2 с ¡1 = 1. Известно [1, Теорема 1.17.1], что любой такой граф является либо объединением клик с одной общей вершиной, либо сильно регулярным графом, либо графом, в котором встречаются только две степени вершин, т.е. бирегулярным графом. Графы первого типа не представляют интереса, среди графов второго типа известно существование только графов Мура: пятиугольника, графа Петерсена и графа Хоффмана - Синглтона.

В графе третьего типа через А (соотв. через В) будем обозначать подграф, индуцированный вершинами меньшей (соотв. большей) степени. В [1, Глава 1.17] описаны 4 известных конструкции бирегулярных геодезических графов диаметра 2:

• граф на 214-1 вершинах, в котором подграф А — это I-коклика, подграф В является объединением изолированной вершины (смежной со всеми вершинами из А) и ¿-клики;

• для натурального I такого, что существует аффинная плоскость (X, С) порядка I, вершины подграфа А — точки плоскости, а подграф В — это граф, дополнительный к графу коллинеарности прямых плоскости, и точка смежна с прямой, если точка лежит на этой прямой;

• для графа Г', получаемого из предыдущей конструкции, построим граф Г добавлением к графу Г' клики порядка I, каждая вершина которой смежна только с каждой прямой класса параллельных прямых аффинной плоскости;

• для натурального I такого, что существует проективная плоскость (X, С) порядка I, и полярности этой плоскости 7г определим граф Г на множестве точек X, в котором две вершины х, у смежны тогда и только тогда, когда х Е уж.

Главный вопрос заключается в том, является ли этот список исчерпывающим? В [1, Глава 1.17] приведены некоторые классификационные результаты геодезические графы диаметра 2, имеющие параметры (фактически, две различные степени вершин), подходящие под описанные выше конструкции, действительно могут быть получены с помощью этих конструкций.

Заметим, что графы, получаемые с помощью описанных конструкций, в определенном смысле симметричны (так, например, подграф В является иногда объединением изолированных клик одинаковых порядков или даже дистанционно регулярным графом).

В четвертой главе диссертации показано, что всем бирегулярным геодезическим графам диаметра 2 (т.е. не только известных конструкций) присуще еще одно интересное свойство. Напомним, что два графа называются изо-спектральными (или ко спектральными), если их матрицы смежности имеют одинаковый спектр (с точностью до кратностей собственных значений).

Рис 0.5. Примеры геодезических графов диаметра 2.

Показано, что для любого г = 1,., \А\ и любых двух г-элементных подмножеств А 1,^2 С А графы, индуцированные множествами А\ и В и А2 и В, изоспектральны (причем легко привести пример, когда такие графы будут неизоморфными). Кроме того, получены некоторые новые необходимые условия существования бирегулярных геодезических графов диаметра 2, которые позволили уточнить классификацию графов Тервиллигера с ¡1 = 2.

Завершается четвертая глава диссертации решением задачи, поставленной в работе [38]. Часто исследуемые классы графов, в том числе и рассматриваемые в данной диссертации, определяются через наложение различных ограничений на подграфы, индуцированные пересечениями подмножеств вершин (например, окрестностей вершин). Авторы [38] рассматривали в этом смысле противоположную задачу — классифицировать графы, в которых объединения окрестностей любой пары различных вершин равномощны. Легко понять, что регулярный граф, обладающий таким свойством, будет сильно регулярным с параметрами Л = у. В общем случае в работе [38] задача решена с помощью теоремы Райзера [39] о (0,1)-матрице, удовлетворяющей определенному квадратному уравнению. Поставленная в [38] следующая задача формулируется так: классифицировать графы, в которых объединение окрестностей любой пары смежных (соотв. несмежных) различных вершин содержит г\ (соотв. Г2) вершин.

В диссертации показано, что графы с данным свойством, за исключением некоторых конструктивно указанных графов, являются сильно регулярными.

Общая характеристика работы

Методы исследований: стандартные методы алгебраической теории графов (комбинаторный анализ, анализ спектров матриц смежности), методы теории представлений конечных групп (т.н. метод Хигмана) для выяснения порядков возможных автоморфизмов дистанционно регулярных графов и исследования подграфов неподвижных точек этих автоморфизмов. При изучении графов Тервиллигера ключевой является возможность проведения индуктивных рассуждений по порядку графа или параметру у.

Научная новизна. Все основные результаты диссертации являются новыми:

• Разработан подход к описанию локального строения графов Тервиллигера с заданным параметром у. На основе этого подхода доказана регулярность подграфов определенного вида в регулярных графах Тервиллигера (положительный ответ на проблему [1, стр. 35]).

• Показано, что графы икосаэдра, Доро и Конвея - Смита являются единственными графами, для которых достигается равенство в границе Ку-лена - Пака [19].

• Вопрос существования дистанционно регулярных локально НоБг графов сведен к вопросу существования графов с массивами пересечений {50,42,9; 1, 2,42} и {50,42,1; 1, 2,50} (частичный ответ на проблему [1, стр. 36]). Показано, что дистанционно регулярный локально Новг граф не является вершинно транзитивным, а диаметр любого связного локально НоБг графа не больше 7.

• Классифицированы массивы пересечений дистанционно регулярных графов, в которых окрестности вершин изоморфны графу Гевиртца С. Показано, что диаметр любого связного локально С графа не больше 5.

• Предложен новый метод оценки диаметра дистанционно регулярного графа с заданными окрестностями вершин, основанный на комбинации неравенств Ван Дама - Хэмерса и Таннера.

• На основе единообразного подхода изучения вложения клик и коклик в дистанционно регулярный граф доказано несуществование дистанционно регулярных графов с массивами пересечений {55,36,11,1; 4,45}, {56,36, 9; 1,3,48}, {45, 30,7; 1,2,27}, {52,35,16; 1,4, 28} и {69,48, 24; 1,4, 46} (тем самым, уточнена классификация геометрических дистанционно регулярных графов с наименьшим собственным значением —3 из [33] и графов Шиллы с параметром Ь = 2 из [19]).

• Построены новые примеры изоспектральных графов как подграфов определенного вида в бирегулярных геодезических графах диаметра 2.

• Доказано, что граф, в котором объединение окрестностей любых двух различных смежных (несмежных) вершин содержит г\ (соотв. гг) вершин, является сильно регулярным, кроме некоторых явно построенных исключений.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в алгебраической теории графов и ее приложениях.

Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, семинаре кафедры компьютерной безопасности и прикладной алгебры Челябинского государственного университета, а также были представлены на следующих конференциях: международная конференция «Алгебра и ее приложения» (Красноярск, 2007); российско-китайский семинар по алгебре и логике, (Иркутск, 2007); молодежная школа-конференция «Проблемы теоретической и прикладной математики» (в наст, время «Современные проблемы математики») ИММ УрО РАН (Екатеринбург, 2005 - 2012); международные школы-конференции по теории групп (Нальчик, 2006, Челябинск, 2008); X Белорусская математическая конференция (Минск, 2008); международные конференции «Мальцевские чтения» (Новосибирск, 2007 -2010); международная конференция по теории графов (Блед (Словения), 2011); международная конференция «Геометрическая и алгебраическая комбинаторика» (GAC) (Оистервийк (Нидерланды), 2011).

Некоторые из основных результатов диссертации процитированы в статье Ван Дама, Кулена и Танаки [4] — обзоре результатов в теории дистанционно регулярных графов с 1989 г., т.е. с момента выхода монографии [1].

Отдельные результаты работы были получены в рамках выполнения исследовательских проектов, поддержанных грантами Президента РФ (МК-938.2011.1), Уральского отделения РАН и РФФИ.

Публикации. Материал диссертации был опубликован в цикле работ, состоящем из 14-ти статей (все опубликованы в журналах из перечня ВАК ведущих рецензируемых научных изданий), и 12-ти тезисов докладов. Из 14-ти статей 5 написаны без соавторов, 2 - тремя авторами (совместно с A.A. Мах-невым, Д.В. Падучих и A.A. Махневым, Го Вэнбинем соответственно). Все совместные работы написаны в нераздельном соавторстве.

Список литературы диссертационного исследования доктор физико-математических наук Гаврилюк, Александр Львович, 2012 год

1. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin, Heidelberg, New-York: Springer-Verlag, 1989.

2. E.R. van Dam, W.H. Haemers, J.H. Koolen Cospectral graphs and the generalized adjacency matrix // Linear Algebra and its Applications. — 2007.- V. 423. P. 33-41.

3. Delsarte P. An algebraic approach to the association schemes of codign theory 11 Philips Res. Rep. Suppl. 1973. - V. 10. - P. 1-97.

4. Van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs // препринт. Электронный ресурс]

5. Bannai E., Ro T. Algebraic combinatorics I: Association Schemes // Benjamin Cummings, 1984.

6. Cameron P. J., Praeger C.E., Saxl J., Seitz G.M. On the Sims conjecture and distance transitive graphs // Bull. London Math. Soc. — 1983. — V. 15.- P. 499-506.

7. Terwilliger P. Distance-regular graphs with girth 3 or 4. I // J. Combin. Theory Ser. B. 1985. - V. 39. - P. 265-281.

8. Bang S., Dubickas A., Koolen J.H., Moulton V. There are only finitely many distance-regular graphs of fixed valency greater than two // arXiv. org: 0909.5253. Электронный ресурс]

9. Terwilliger P. A class of distance-regular graphs that are Q-polynomial // J. Combin. Theory B. 1986. - V. 40. - P. 213-223.

10. Furedi Z. On the number of edges of quadrilateral-free graphs // J. Combin. Theory Ser. B. 1996. - V. 68. - P. 1-6.

11. Махнев А.А. О регулярных графах Тервиллигера с ц = 2 // Сибирский матем. ж. 1996. - Т. 37, №5. - С. 1132-1134.

12. Damerell R.M. On Moore graphs // Math. Proc. Cambr. Phil. Soc. — 1973. V. 74. - P. 227-236.

13. Махнев А. А., Падучих Д.В. Об автоморфизмах графа Ашбахера // Алгебра и логика. 2001. - Т. 40, №2. - С. 125-134.

14. Кабанов В.В., Махнев А.А. Графы без 3-лап с равномощными ц-подграфами. // Известия Уральского гос. университета. — 1998. — № 10. С. 44-68.

15. Nomura К. Homogeneous graphs and regular near polygons / / d. Combin. Theory Ser. B. 1994. - V. 60. - P. 63-71.

16. Jurisic, A., Koolen, J.H. A local approach to 1-homogeneous graphs // Des. Codes Cryptogr. 2000. - V. 21. - P. 127-147.

17. Koolen J.H., Bang S. On distance-regular graphs with smallest eigenvalue at least -тЦЗ. Combin. Theory Ser. B. 2010. - V. 100, №6. - P. 573-584.

18. Koolen J.H., Markowsky G., Park d. There are only finitely many distance-regular graphs with valency k ^ 3, fixed ratio k2/k, and large diameter // arXiv.org: 1012.2632. Электронный ресурс]

19. Koolen d.H., Park J. Shilla distance-regular graphs // European d. Comb. — 2010. V. 31, №8. - P. 2064-2073.

20. Зыков А.А. Теория конечных графов, I // M.: Наука, 1969.

21. Махнев А.А. Об автоморфизмах дистанционно регулярных графов // Фундаментальная и прикладная математика. — 2009. — Т. 15, №1. — С. 65-79.

22. Hiraki A., Koolen d.H. An improvement of the Ivanov bound // Annals of Combinatorics. 1998. - V. 2, №2. - C. 131-135.

23. Махнев А.А. О графах, в которых окрестность каждой вершины изоморфна графу Хоффмана Синглтона // Доклады РАН. — 2008. — Т. 422, Ж 6. - С. 735-737.

24. Van Dam E.R., Haemers W.H. Eigenvalues and the diameter of graphs // Linear Multilm. Alg. 1995. — V. 39. - P. 33-44.

25. Brouwer A.E., Haemers W.H. Spectra of graphs // Springer, 2012.

26. Махнев А.А., Кабанов В.В., Падучих Д.В. О сильно регулярных графах с собственным значением 2 и их расширениям / / Труды Института математики и механики УрО РАН. — 2010. — Т. 16, №3. — С. 105-116.

27. Jurisic A., Koolen J.H. 1-Homogeneous graphs with cocktail party /¿-graphs //J. Alg. Combm. 2003. - V. 18. - P. 79-98.

28. Fon-Der-Flass D. G. There exists no distance-regular graph with intersection array {5,4,3; 1,1,2} // European J. Combin. 1993. - V. 14. - P. 409-412.

29. Fon-Der-Flass D. G. There exists no distance-regular graph with intersection array {5,4,3,3; 1,1,1,2} // J. Algrebraic Combin. 1993. - V. 2. - P. 49-56.

30. Coolsaet K. A distance regular graph with intersection array (21,16,8; 1,4,14) does not exist // European J. Combin. — 2005. — V. 26. P. 709-716.

31. Coolsaet K., Jurisic A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Combin. Theory Ser. A. 2008. - V. 115, №6. - P. 1086-1095.

32. Jurisic A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3 // Designs, Codes and Cryptography. 2012. - V. 65, №1-2. - P. 29-47.

33. Bang S. Geometric distance-regular graphs without 4-claws // arXiv. org: 1101.0440. Электронный ресурс]

34. Bang S., Hiraki A., Koolen J.H. Delsarte clique graphs // European J. Combin. 2007. - V. 28, №2. - P. 501-516.

35. Cameron P.J., Goethals J.M., Seidel J.J., Shult E.E. Line graphs, root systems, and elliptic geometry // J. Algebra. — 1976. — V. 43. — P. 305—327.

36. Blokhuis A., Brouwer A.E. Determination of the distance-regular graphs without 3-claws // Discrete Math. 1997. - V. 16. — P. 225-227.

37. Bang S., Koolen J.H. Nonexistence of distance-regular graphs with intersection array {За + 3,2c*+ 2, a+ 2 — /3; 1,2, 3/3} // Shanghai Conference on Algebraic Combinatorics. — 2012. Электронный ресурс]

38. Abdollah Khodkar, Leach D., Robinson D. Every (2, ?')-Regular Graph is Regular // Utilitas Mathematica. — 2007. V. 73. — P. 169-172.

39. Ryser H.J. A generalization of the matrix equation A2 = J / / Linear Algebra and Appl. 1970. - V. 3. - P. 451-460.

40. Bose R.C., Dowling T.A. A generalization of Moore graphs of diameter 2 // J. Comb. Theory B. 1971. - V. 11. - P. 213-226.

41. Воробьев H.H. Числа Фибоначчи. — M.: Наука, 1978.

42. Brouwer А.Е., Koolen J.H. The vertex-connectivity of a distance-regular graph 11 Eur. J. Combm. 2009. - V. 30. - P. 668-673.

43. Махнев А.А. О расширениях частичных геометрий, содержащих малые /¿-подграфы // Дискр. анализ и исслед. операций. — 1996. — Т. 3, № 3. — С. 71-83.

44. Brouwer А.Е., Haemers W.H. Spectra of graphs. — Springer, 2012.

45. Dam E.R. van, Haemers W.H. Eigenvalues and diameter of graphs // Linear Multilin. Alg. 1995. - V. 39. - P. 33-44.

46. Soicher L.H. Three new distance-regular graphs // Europ. J. Comb. — 1993. V. 14. - P. 501-505.

47. Brouwer A.E., Mesner D.M. The connectivity of strongly regular graphs // Europ. J. Combm. 1985. - V. 6. - P. 215-216.

48. Cameron P.J. Permutation Groups. — London Math. Soc. Student Texts №45. — Cambridge: Cambridge Univ. Press., 1999.

49. Cameron P. J., van Lint J. Graphs, Codes and Desidns. — London Math. Soc. Student Texts №22. — Cambridge: Cambridge Univ. Press., 1991.

50. Macay M., Siran J. Search for properties of the missing Moore graph // Linear Algebra and its Appl. 2009. — V. 432. - P. 2381-2398.

51. Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra // Europ. J. Comb. 1993. - V. 14. - P. 397-407.

52. The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4.12; 2008. (http://www.gap-system.org)

53. Godsil C.D. Geometric distance-regular covers // New Zealand J. Math. — 1993. V. 22. - P. 31-38.

54. Haemers W.H., Kharaghani H., Meulenberg M.A. Divisible design graphs (Discussion paper № 2010-19) // Tiburg University. — 2010.Публикации автора по теме диссертации в журналах из перечня ВАК ведущих рецензируемых научных изданий

55. Гаврилюк А.Л., Махнев A.A. Графы Тервиллигера с ¡i ^ 3 // Математические заметки. — 2007. — Т. 82, № 1. — С. 14-26.

56. Гаврилюк А.Л., Махнев A.A. О проблеме регулярности в графах Тервиллигера // Доклады РАН. 2007. - Т. 417, № 2. - С. 151-155.

57. Гаврилюк А.Л., Махнев A.A. Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена // Доклады РАН. 2008. - Т. 421, № 4. - С. 445-448.

58. Гаврилюк А.Л., Вэнбинь Го, Махнев A.A. Об автоморфизмах графов Тервиллигера с ß = 2 // Алгебра и логика. — 2008. — Т. 47, № 5. — С. 584-600.

59. Гаврилюк А.Л., Махнев A.A. О графах Тервиллигера, в которых окрестности вершин изоморфны графу Хоффмана Синглтона // Математические заметки. - 2011. — Т. 89, № 5. - С. 673-685.

60. Гаврилюк А.Л., Махнев A.A. О дистанционно регулярных графах, в которых окрестность каждой вершины изоморфна графу Хоффмана Синглтона // Доклады РАН - 2009. - Т. 428, № 2. - С. 157-160.

61. Гаврилюк А.Л. Графы Тервиллигера с ß = 4 // Труды Института математики и механики УрО РАН. — 2009. — Т. 15, № 2. — С. 84-93.

62. Gavrilyuk A.b. On Terwilliger graphs and the Koolen Park inequality // Electronic Journal of Combinatorics. — 2010. — V. 17. — Paper №125.

63. Гаврилюк А.Л., Махнев A.A., Падучих Д.В. Дистанционно регулярные графы, в которых окрестности вершин изоморфны графу Гевиртца // Труды Института математики и механики УрО РАН. — 2010. — Т. 16, № 2. С. 35-47.

64. Гаврилюк А.Л. Дистанционно регулярные графы с массивами пересечений {55, 36,11,1; 4,45} и {56,36,9; 1,3,48} не существуют // Доклады РАН. 2011. - Т. 439, № 1. - С. 14-17.

65. Гаврилюк А.Л., Махнев A.A. Дистанционно регулярный граф с массивом пересечений {45,30, 7; 1,2, 27} не существует // Дискретная математика. 2012. - Т. 24, № 3.

66. Gavrilyuk A.L., Makhnev A.A. Distance-regular graphs with intersection arrays {52,35,16; 1,4,28} and {69,48, 24; 1,4,46} do not exist // Designs, Codes and Cryptography. 2012. - V. 65, № 1-2. - C. 49-54.

67. Гаврилюк А.Л. Классификация графов Райзера // Математические заметки. 2009. - Т. 86, № 1. - С. 14-21.

68. Гаврилюк А.Л. Об изоспектральных подграфах бирегулярных геодезических графов диаметра 2 // Труды Института математики и механики УрО РАН. 2007. - Т. 13, № 4. - С. 49-60.Прочие публикации автора по теме диссертации

69. Гаврилюк А.Л., Махнев A.A. О графах Крейна без треугольников // Доклады РАН. 2006. - Т. 403, № 6. - С. 727-730.

70. Гаврилюк А.Л. Дистанционно регулярный граф с массивом пересечений {55,36,11; 1,4,45} не существует // Соврем, пробл. математики: тез. 42-й Всерос. молодеж. шк.-конф. ИММ УрО РАН, 2011. - С. 189-190.

71. Гаврилюк А.Л. Дистанционно регулярные графы с массивами пересечений {55,36,11; 1,4,45} и {56,36,9; 1, 3,48} не существуют // Алгебра и геометрия: тр. Междунар. конф., посвящ. 80-летию А.И. Старостина. ИММ УрО РАН, 2011. - С. 46-48.

72. Гаврилюк А.Л., Махнев A.A. Дистанционно регулярный граф с массивом пересечений {45,30, 7; 1, 2, 27} не существует // Алгебра и геометрия: тр. Междунар. конф., посвящ. 80-летию А.И. Старостина. — ИММ УрО РАН, 2011. С. 51-53.

73. Гаврилюк А.Л., Махнев A.A. Дистанционно регулярный граф с массивом пересечений {52,35,16; 1,4,28} не существует // Алгебра и мат. логика: материалы междунар. конф., посвящ. 100-летию В.В.Морозова. — КФУ, 2011. С. 73-74.

74. Гаврилюк А.Л., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56,45,1; 1,9,56} // Доклады Г АН. 2010. - Т. 432, №5. - С. 583-587.

75. Гаврилюк А. Л. Об одном неравенстве Кулена-Парка и графах Тервилли-гера // Теория групп и ее прил: тр. 8-й Междунар. шк.-конф., посвящ. 15-летию В.А. Белоногова. ИММ УрО РАН, 2010. - С. 63-66.

76. Гаврилюк А.Л. Об одном неравенстве Кулена-Парка и графах Тервил-лигера // Проблемы теорет. и прикл. математики: тез. J^l-й Веерос. молодеж. конф. ИММ УрО РАН, 2010. - С. 10-13.

77. Гаврилюк А.Л. Об одном неравенстве Кулена-Парка и графах Тервил-лигера // Проблемы теорет. и прикл. математики: тр. 40-й Веерос. молодеж. конф. ИММ УрО РАН, 2009. - С. 15-17.

78. Гаврилюк А. Л., Махнев A.A., Падучих Д. В. О графах, в которых окрестности вершин изоморфны графу Гевиртца // Доклады РАН. — 2009. — Т. 428, №3. С. 300-304.

79. Гаврилюк А.Л., Махнев A.A. Геодезические графы с некоторыми условиями однородности // Доклады РАН. 2008. - Т. 422, №5. - С. 589-591.

80. Гаврилюк А.Л., Махнев A.A. О дистанционно регулярных графах, в которых окрестности вершин изоморфны графу Хофмана-Синглтона / / Теория групп: тез. сообщ. 7-ой Междунар. шк.-конф., авг. 2008 г. — Изд-во ЮУрГУ, 2008. С. 32-34.

81. Гаврилюк А.Л. О бирегулярных геодезических графах диаметра 2 // Пробл. теорет. и прикл. математики : тр. 38-й Регион, мол. конф., 29 янв.-2 февр. 2007. ИММ УрО РАН, 2007. - С. 14-17.

82. Гаврилюк А.Л., Махнев A.A. Графы Тервиллигера с ¡i ^ 3 // Пробл. теорет. и прикл. математики : тр. 38-й Регион, мол. конф., 29 янв.-2 февр. 2007. ИММ УрО РАН, 2007. - С. 18-22.

83. Гаврилюк А.Л., Махнев A.A. Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена // Междунар. конф. "Алгебра и ее прил.", Красноярск, 12-18 авг. 2007: тез. докл. — 2007. С. 35-36.

84. Гаврилюк А.Л., Махнев A.A. О проблеме регулярности в графах Тервиллигера // Междунар. конф. "Алгебра и ее прил.", Красноярск, 12-18 авг. 2007: тез. докл. 2007. - С. 36-37.