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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

005055554 ,

Гаврилюк Александр Львович

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

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

2 2 ноя тг

Екатеринбург 2012

005055554

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН

Научный консультант:

доктор физ.-мат. наук, члеп-корр. РАН Александр Алексеевич Махиев Официальные оппоненты:

доктор физ.-мат. наук, профессор Виталий Анатольевич Баранский доктор физ.-мат. наук Денис Станиславович Кротов доктор физ.-мат. паук Илья Николаевич Пономаренко

Ведущая организация:

Челябинский государственный университет

Защита состоится 27 ноября 2012 г. в 14 ч. 00 м. на заседании диссертационного совета Д 004.006.03 по защите диссертации тта соискание ученой степени доктора наук при Институте математики и механики Уральского отделения РАН по адресу: 620990, Екатеринбург, ул. Софьи Ковалевской, д. 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.

Автореферат разослан октября 2012 г.

Д 001.006.03 кандидат физ.-мат. наук

Ученый секретарь диссертационного совета

И.Н. Белоусов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

В диссертации проводится систематическое изучение класса графов Тер-виллигсра и связанных с ним вопросов в теории дистанционно регулярных графов. Разработаны методы изучения локального строения графов Тсрвил-лпгера, дистанционно регулярных графов с заданными окрестностями вершин, предложены доказательства несуществования дистанционно регулярных графов с некоторыми допустимыми массивами пересечений. Актуальность темы. Объектами исследования в настоящей работе являются дистанционно регулярные графы и графы с некоторыми более специфическими условиями такими, например, как запрет на подграфы определенного вида. Здесь и далее в работе рассматриваются только конечные неориентированные графы без петель и кратных ребер. Наша терминология и обозначения в основном стандартны, см. монографию |1|. Под подграфом понимается подграф, порожденный множеством вершин. Для графа Г = (V, Е) множество вершин V = V(Г) обозначается тем же символом, что и граф, т.е. Г.

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

Г,;(х) П Г, (?/) содержит точно р\ • вершин, причем число р[ - зависит только от

/

7,7,1, но не от выбора конкретной пары вершин х, у на расстоянии I. Числа называются числами пересечений графа. Обычно дистанционно регулярный граф описывается массивом, пересечений:

{Ьа, Ьи - ■ ■ ,Ь(1 си с2,. . ., с,/}, где = р\М1, с4 =

поскольку все числа пересечений могут быть вычислены из этого массива.

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

Классическими в некотором смысле примерами дистанционно регулярных (и дистанционно транзитивных) графов являются графы Хэмминга и графы Джонсона, см. [1, Глава 9|. Эти семейства графов связывают теорию дистанционно регулярных графов соответственно с алгебраической теорией кодирования и теорией блок-схем (дизайнов), что было показано в диссертации Ф.

Дельсарта [2]. Существует, однако, гораздо больше подобных связей: с теорией конечных групп, конечными геометриями, схемами отношений, ортогональными многочленами. В последнее время интсрсс к дистанционно регулярным графам наблюдается со стороны задач комбинаторной оптимизации, теоретической физики и квантовых вычислений, см. обзор [3]. В качестве завершения вступления можно сказать, что дистанционно регулярные графы, методы их исследования (комбинаторные и алгебраические) позволяют единообразно изучать объекты из различных областей дискретной математики и алгебры.

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

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

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

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

для каждого к ^ 3 существует лишь конечное 'число конечных дистанционно регулярных графов валентности к.

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

дистанционно регулярного графа, выполняются неравенства

^ ь а ^ 0 ^ г < ¿,

т.е. последовательности {Ь«}^}, {с,;}5'=1 не возрастают и не убывают, соответственно.

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

В работе [6| Тсрвнллигер показал, что для массива пересечений дистанционно регулярного графа, содержащего порожденный 4-цикл, выполняются неравенства

С,; - 6,; > С,;_1 - + + 2, 1 ^ I ^ й,

где по определению а,; = Ьо — — с,;.

Используя эти неравенства, можно показать, что для дистанционно регулярного графа, содержащего 4-цикл, верна граница Тервиллигера [1, Следствие 5.2.2]:

, , Ьо + сн 2Ьа

а ^ - < -,

сц + 2 щ + 2

и таким образом гипотеза Банпаи и Ито верна в этом случае.

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

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

<1 ^ .«У4''"-1.

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

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

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

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

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

Описанные выше конструкции графов Тервиллигера с р > 1 не представляют интереса. Мы исключим эти случаи из общего рассмотрения следующим образом. Для подмножества вершин £ графа Г положим И1 = П^.^х ,

где х1 — это шар радиуса 1 с центром в вершине х, т.е. х1 = {.т} U Г:(.г). В частном случае множество Г^.г)1" называется ядром, вершины х,

ВД1 = {у G Г : х^Су^}.

Нас будет интересовать окрестность вершины за вычетом ее ядра, т.е. подграф

А,:=Г1(.т:)\(Г,(.х)1).

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

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

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

Теперь упомянутое выше утверждение Тервиллигера [6| можно сформулировать следующим образом:

в регулярном графе Тервиллигера Г с ß. > 1, содержащем, хотя, бы одну вершину х с |Ti (ат)1 | < ß, подграфы, Ау регулярны для, вссх вершин у € Т.

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

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

виллигера диаметра 2 являются кликовыми расширениями дистанционно регулярных графов (дистанционно регулярные графы диаметра 2 называются также сильно регулярными).

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

Пятиугольник и граф Петерссна являются представителями еще одного интригующего класса графов — сильно регулярных графов Мура [11]. В этот класс входит также граф Хоффмапа - Сипглтопа и гипотетический граф па 3250 вершинах, вопрос о существовании которого не решен [12].

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

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

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

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

Прежде всего, отметим популярную задачу классификации графов без 3-лап, т.е. без порожденных полных двудольных графов с долями порядка 1 и 3, в процессе решения которой графы с кликовыми ¿¿-подграфами рассмат-

риваются как особый случал. Графы Тервиллигера без 3-лал были классифицированы В.В. Кабановым и Л.Л. Махпевым в работе [13].

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

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

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

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

я(а! + 1) - Ь0

ч,_15>—э—'

и заметили, что граф является графом Тервиллигера, сели для некоторого в достигается равенство и любая 2-лапа графа содержится в я-.папе.

Еще одним результатом первой главы диссертации является новая ха-рактеризация известных дистанционно регулярных графой Тервиллигера с

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

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

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

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

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

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

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

Пусть граф Г дистанционно регулярен и окрестность каждой его вершины является сильно регулярным графом с параметрами (ь, к, X. р). Первые элементы массива пересечений Г определяются локальным строением: 1>о = и

(степень вершины в Г), /)] = v — к — 1 (т.е. п\ = к). Но уже параметр с2 может принимать несколько значений (несложно показать, что для пары вершин х, у £ Г, находящихся на расстоянии 2, подграф ri(x) nTi(y) будет регулярным графом степени //, и делит bobi).

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

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

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

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

Таким образом, рассматриваемая задача классификации локально HoSi

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

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

Один из них основан на том, что матрица смежности графа HoSi имеет спектр Т1^28, —З21. Теперь, рассматривая изолированные подграфы С : — r.;_i(a;) П ri(y) и В : = Г^+х(х) П Ti(y) для пары вершин х,у £ Г, находящихся на расстоянии г ^ 2, по теореме о переплетении спектров [24, Теорема 2.5.1 ] имеем, что максимальное собственное значение по крайней мере одного из графов В или С не больше 2 (т.е. второго по величине собственного значения графа HoSi). По теореме Смита [1, Теорема 3.2.5] граф, максимальное собственное значение которого не превосходит 2, является объединением изолированных подграфов из графов X, где X £ {An,Dn.Ee,Ej,Es}. Далее, комбинаторными рассуждениями удастся показать, что в случае сМат(Г) ^ 8 и i = 4 и граф В, и граф С содержат порожденный подграф, не являющийся подграфом из X, что приводит нас к противоречию.

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

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

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

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

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

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

тех же самых графов было показано С. Банг [32].

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

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

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

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

{За + 3, 2а + 2, а + 2 — /3; 1, 2, 3/3}, (1)

где а ^ /3 > 1 — целые числа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завершается четвертая глава диссертации решением задачи, поставленной в работе [37]. Часто исследуемые классы графов, в том числе и рассматриваемые в данной диссертации, определяются через наложение различных ограничений па подграфы, индуцированные пересечениями подмножеств вершин

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

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

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

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

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

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

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

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

• Вопрос существования дистанционно регулярных локально НоБ1 графов сведен к вопросу существования графов с массивами пересечений

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

• Классифицированы массивы пересечений дистанционно регулярных графов, в которых окрестности вершин изоморфны графу Гевиртца (7. Показано, что диаметр любого связного локально (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 из |32| и графов Шпллы с параметром 6 = 2 из |18|).

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

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

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

Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались па алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, семинаре кафедры компьютерной безопасности и прикладной алгебры Челябинского государственного университета, а также были представлены на следующих конференциях: международная конференция «Алгебра и ее приложения» (Красноярск, 2007); российско-китайский семинар по алгебре и логике, (Иркутск, 2007); молодежная школа-конференция

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

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

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе диссертации изучается локальное строение графов Тсрвиллигсра и характсризапии известных графов Тсрвиллигсра с /х = 2. Результаты главы опубликованы в статьях [39, 40, 41, 45, 46].

Для подмножества вертпин Е графа Г определим

где х1 — это шар радиуса 1 с центром в вершине х, т.е. х1 := {х} и Г^х), а для вершины х € Г определим подграф

Д, := Г1(ж)\(Г1(ж)1).

Теорема 1.1. Если, Г являет,ся регулярным, графом, Тсрвиллигсра, содержащим хотя бы, одну вершину х с условием, ]Г!(.т)-1-1 < //(Г), то подграфы, Д,у регулярны для всех вершин у ё Г.

Теорема 1.1 дает положительный ответ па вопрос, сформулированный в [1, стр. 35]. Рапсе это утверждение было некорректно доказано П. Тсрвилли-гером в [6].

Известны только три графа Тсрвиллигсра с ц > 1: икосаэдр, граф Доро и граф Конвея - Смита. Все они имеют параметр /х, равный 2, и являются локально графами Мура: икосаэдр является единственным связным локально пятиугольным графом, а в графах Доро и Конвея - Смита окрестность каждой вершины — это граф Петерсепа.

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

Если Г — сильно регулярный граф Тервиллигера с /х = 2, то окрестность всякой вершины в Г — сильно регулярный граф Тервиллигера с /г = 1, т.е. граф из класса ?{з,г) для подходящих я, г, причем параметры в, г не будут зависеть от выбора вершины из Г. Поэтому через г) обозначим класс

сильно регулярных графов Тсрвиллигсра с р. = 2, в которых окрестность каждой вершины — граф из класса

Следующая доказанная в работе теорема описывает все возможности для графов Тсрвиллигсра с д = 2.

Теорема 1.2. Пусть Г — связный граф Тервиллигера с р = 2 и Г1 = 0. Тогда выполняется одно из следующих утверждений:

(1) подграф Ф па миоэ/сестве вершин из Г с. не.кликовыми окрестностями является 2-кликовым расширением графа Ф с /л(Ф) = 1;

(2) найдутся натуральные числа а, г такие, что Г является локально ^(в, г) графом;

(3) диаметр Г больше 2; Г является бирегулярпым графом, и если А (если В) — множество его вершин меньшей (большей) степени, то окрестность вершины а из А содержится в В, окрестность каэ/сдой вершины, Ь из В пересекает А по непустому множеству и верно одно из утверждений:

(г) Г^а) является графом Петерсена, а 1^(6) — граф, отвечающий полярности проективной плоскости порядка 3,

(гг) Г^а) является графом Хоффмаиа-Сииглтона, а Г^Ь) — граф, отвечающий полярности проективной плоскости порядка 7,

(т) Г^а) является графом Мура степени 57, а Г^б) — граф на мно-о/сестве точек и прямых аффинной плоскости порядка 56, в котором множество ■точек совпадает с А П ГцЬ), точка и прямая смежны, села они инцидентны в плоскости, и две прямые смежны, если они параллельны,

(гг>) ГЦа) является. графом Мура степени 57, а Г^Ь) — граф, полученный добавлением к подграфу из предыдущего пункта 57-клики, вершины которой отвечают классам параллельных прямых аффинной плоскости, и каждая прямая смежна с классом параллельных прямых, содержат,им эту прямую,

(и) Г} (а) является графом Мура степени 57, а — бирегулярный

геодезический граф диаметра 2, в котором меньшая степень вершины равна 57, а большей — 66 или 82.

Граф икосаэдра, Доро и Копвея - Смита являются единственными известными примерами графов из утверждения (2). В четвертой главе диссертации показано, что бирегулярные геодезические графы диаметра 2, упомянутые в утверждении (З.и), не существуют.

Слс/1ующая теорема из первой главы диссертации показывает, что случай (З.г) также не возможен.

Теорема 1.3. Если в графе Тервиллигера Г найдется хотя бы одна вершина

х такая, что Г, (.г) — граф Пст.ерсена, то либо Г = х1, л,ибо Г является графом, Доро или графом Конвея - Смита.

Существование графов, удовлетворяющих утверждениям (З.гг)-(З.ги) теоремы 1.2, является открытым вопросом.

Вершину х графа Г назовем редуцированной, если Г^х)1 = {х}, и нередуцированной в противном случае.

Теорема 1.4 описывает возможное локальное строение графов Тервилли-гера с р = 3.

Теорема 1.4. Пусть Г - связным граф Тервиллигера с р = 3 иГ1 - пуст,ой граф. Тогда верно одно из следующих утверждений:

(1) подграф Ф на множестве вершин из Г с некликовыми окрестностями является, З-кликовым расширением, графа Ф с /х(Ф) = 1;

(2) найдутся такие натуральные числа я,г, что Г является локально С?(я, г) графом;

(3) Г содержит, иередуцирова,ни,ую верит,ну, ди,ам,ет,р Г больше 2; найдутся, такие натуральные числа ,ч,г, что для любой нередуцированной вершины а подграф Аа принадлежит классу а для любой редуцированной вершины, Ь подграф А/, является. 2-кл,и,ковы,м расширением графа, из

Л«/2, г);

(4) найдутся такие натуральные числа в, г, что для любой вершины и подграф Аи является 2-кликовы.м. расширением графа из Т{з,г), где + 1) делится на 3.

В еще одной теореме из первой главы диссертации описывается возможное локальное строение графов Тервиллигера е /4 = 4; в целом, этот результат аналогичен теореме 1.4.

Первая глава диссертации завершается новой характсризацисй известных графов Тервиллигера с ¡л — 2. Напомним, что граф Г называется вполне регулярным с параметрами (у,к,\,ц), если Г содержит V вершин, регулярен степени к, и для любой пары его смежных (соотв. находящихся на расстоянии 2) вершин х,у, подграф Г^х) П Г г (у) содержит точно Л (соотв. точно у) вершин. В частности, вполне регулярный граф диаметра 2 является сильно регулярным.

Теорема 1.5. Пусть Г — вполне регулярный граф с парам,ет,рам,и, (и, к, А, р) с у > 1. Пусть в > 2 — максимальное число такое, что для любой вершины х е Г и любой пары несмежных вершин у, г из Г^х), существует в-коклика

в Г^а;), содержащая у, г. Тогда

гв'(Л + 1) - к , , (.2/

и в случае равенства Г является графом икосаэдра, Доро или Конвея - Смита.

Отмстим, что самостоятельный интерес могут представлять некоторые вспомогательные результаты из первой главы диссертации. Например, следующая лемма из [40| может быть полезна при изучении графов, в которых /¿-подграфы являются (<7 + 1) х (г/ + 1)-решетками (в частности, графы Гроссмана, ^¡{ь, с1) удовлетворяют этому свойству). Напомним, что тхп-решеткой называется прямое произведение двух клик порядков т и п. Лемма 1.6. Пусть диаметр графа Тервиллигера Г равен 2 и подграф Г1-пустп. Если Г нерегулярен, то Г является кликовым расширением бирегу-лярного геодезического графа диаметра 2.

Фактически, эта лемма обобщает теорему 1.17.1 из [1], классифицирующую графы Тервиллигера диаметра 2 с ¡1 = 1.

Во второй главе диссертации изучается вопрос существования графов, окрестности вершин в которых изоморфны сильно регулярным графам Хоффмана- Синглтона с параметрами (50, 7, 0,1) или Гевиртца с параметрами (56,10,0,2): предложены некоторые методы оценки диаметра таких графов и перечислены все возможные массивы пересечений. Результаты главы опубликованы в статьях [42], [43], [44], [47].

Теорема 2.1. Пусть Г дистанционно регулярный граф, в котором окрестности вершин изоморфны графу Хоффмана - Синглтона. Тогда Г имеет массив пересечений {50,42,1; 1,2,50} или {50,42,9; 1,2,42}.

Таким образом, проблема существования дистанционно регулярных локально HoSi графов, сформулированная в [1, стр. Зб|. сводится к вопросу существования графов с массивами пересечений из теоремы 2.1. Теорема 2.2. Пусть Г — дистанционно регулярный граф) Тервиллигера, имеющий массив пересечений {50,42,1; 1,2,50}, (7 = Аи1;(Г), д — элемент из С простого порядка р и П = Пх(г7). Тогда р нечетно и верно одно из утверо/сдеиий:

(1) р = 3,11 или 17 и 12 пустой граф;

(2) р = 5, состоит из вершин, попарно находящихся на расстоянии 3 и |П| е {2,7,12,17}.

Теорема 2.3. Пусть Г — дистанционно регулярный граф Тервиллигера, имеющий массив пересечений {50,42,9; 1,2,42}, <2 = Аи^Г), д - элемент из С простого порядка р и П = ¥'\х(д). Тогда р нечетно и верно одно из утверждений:

(1) р = 3,13 или 17 и 12 — пустой граф;

(2) р = 7 и является объединение,и пяти изолированных 2-клик; (2) р = 5 и 12 является одновершинной кликой.

Следствие 2.4. Дистанционно регулярные графы Тервиллигера, имеющие массив пересечений {50,42,1; 1,2,50} или {50,42,9; 1,2,42}, не являются всршинно транзитивными.

Ранее Дж. ван Бон показал, см. [1, Глава 1.16], несуществование дистанционно транзитивных локально НоБг графов.

Доказательство следующего предложения основано на том факте, что второе по величине собственное значение графа Яо5г равно 2. Предложение 2.5. Диаметр связного локально НоБг графа не больше 7.

Теорема 2.6 позволяет ограничить диаметр дистанционно регулярного графа, в котором окрестности вершин сильно регулярны с известными параметрами. Предположим, что Г является дистанционно регулярным локально £ графом диаметра с1 > 3, с массивом пересечений {6П, Ьь ... , 6</_ 1; сь с2,.. ., с,/} и различными собственными значениями во = > 0\ ... > в^, где 5 — класс сильно регулярных графов с параметрами (60, А,/'■)• Обозначим через г, в неглавные собственные значения (т.е. отличные от валентности 0.1) графов из класса 5. Заметим, что г > 0 и в < 0. Положим М тах{г|1гу -1, ^ + 1} и в := тах{#ь |0й|}. Через к,, как обычно, обозначим число вершин в подграфе Г,-(х), которое не зависит от выбора вершины 1бГ. Пусть граф Г содержит точно V вершин.

Далее, для г 6 {1, ...,(1 - 1} определим функцию и^х):

, , , (¿7 + 1 + ^ГХ1 ~

'(1+! +¿Г»'

Теорема 2.6. Выполняется неравенство аг ^ в ^ М, и если для некоторого

С' Ь'

г £ {1, ...,й— 1} выполняется неравенство в2(-— 4-1-1--—) < Щ, то верны.

Щ-1 Й+1

следующие ут.веро/сдения:

с» Ь-

(1) V ^ г>;(0) и, в частности, ссли + 1 Н--—) < Ь1, то

Ьг-\ С(> 1

^ к

(5а7 + 1 + А-)(1-(^)

, ^ 1п(2 • - 1)) , , . ,

(2) а ^----ь 1, гае /г — минимум функции

Н(х,у) := 1п((\/6о — у + А - /(А) " У ~ А) " а.')) в области [а\, — 1] х [-у1-^ — 1,6'].

Теорема 2.7. Пусть Г — дистанционно регулярный граф, в котором окрестности вершин изоморфны грифу Гевиртца. Тогда выполняется одно из следующих ут.верэ1сденигг.

(1) Г — сильно регулярный граф) с паральетрами (162, 56, 10, 24) или (372, 56, 10,8);

(2) диаметр Г равен 3 и Г граф с массивом пересечений {56, 45, 1; 1, 9, 56};

(3) диаметр Г равен 4 и Г — аитиподальиое г-иакрыгпие сильно регулярного графа с параметрами (162,56,10,24), имеющее массив пересечений {56,45, 24(г - 1 )/г, 1; 1,24/г, 45, 56}, г 6 {2,3}.

Существует единственный сильно регулярный граф с параметрами (162, 56, 10,24), в котором окрестности вершин изоморфны графу Гевпртца. Это вторая окрестность вершины в графе Маклафлина. Известно существование дистанционно регулярного графа, являющегося 3-пакрытисм второй окрестности вершины в графе Маклафлина (это граф Сойчсра). Существование сильно регулярного графа с параметрами (372, 56,10, 8) неизвестно.

Дистанционно регулярный граф с массивом пересечений {56,45,24(г — 1)/г, 1; 1, 24/т-, 45, 56} не существует в случае г = 2. В этом случае граф Гз,4, т.е. граф с множеством вершин графа Г, в котором две вершины смежны, если находятся па расстоянии 3 или 4 в Г, является сильно регулярным с параметрами (324,57,0,12) и по теореме из |53| не существует.

В работе показано, что дистанционно регулярный граф {56,45,1; 1, 9, 56}, в котором окрестность некоторой вершины изоморфна графу Гевиртца, пе существует.

Получена оценка для диаметра связного графа, в котором окрестности вершин изоморфны графу Гевиртца.

Предложение 2.8. Пусть Г — связный граф, в котором окрестности вершин изоморфны ?.рафу Гевиртца. Тогда диаметр Г не больше 5.

Третья глава диссертации посвящена доказательству результатов, которые можно объединить в виде следующей теоремы; см. статьи [48, 49, 50].

Теорема 3.1. Дистанционно регулярные, графы, с массивами пересечений {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} не существуют,.

Несуществование графов с массивами пересечений {45,30,7; 1,2, 27} и {69, 48,24; 1,4,46} уточняет результаты работ [32] и [18], соответственно.

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

Графы Г] и Г2 с матрицами смежности соответственно А1 и А2 называются Л-изоспектральными, если для любого у е К обобщенные матрицы смежности уЗ - А] и уЗ - А2, где Л — матрица из единиц, имеют одинаковый спектр.

Пусть Г — бирег.улярный геодезический граф диаметра 2, А — множество его вершин меньшей степени с*, тп := |А|, п В — множество его вершин большей степени 0.

Теорема 4.1. Для любого г е {1,..,т - 1} и любой пары подмножеств АиА2 из А таких, что ¡А^ = |Л2| = г, подграфы А\ и В и А2иВ являются И-из оспе ктральн ыми.

Следующее предложение позволяет уточнить возможности для графов Тервиллигера с /г = 2 (см. теорему 1.2 выше).

Предложение 4.2. Положим в = 0-а+1 ид = 0 (тос! я). Выполняются следующие утверждения:

(1) т = а - 1 = д (тос1 а);

(2) число я делит д2(д- 1) и <?3(1 + 2Ь) + д2(1 - Ь- За) + д{а + Ъ) + с{д - 1), где а = (т - Ь - (а - д - 1)/б', с = д2(<? - 1)/в.

Следствие 4.3. Вирегулярные геодезические графы диаметра 2 со степенями. вершин а и 0, где а < 0, не существуют, при (а,0) е {(11,13), (57,66), (57,82)}.

Далее через Кпхт. будем обозначать полный многодольпый граф с п долями порядка т. Кликой А'; порядка I называется полный граф на I вершинах.

Для натуральных чисел г\ и г2 рассмотрим класс графов И(г 1,7-2) со следующим свойством: для любого графа Г из этого класса и для любой пары различных вершин х,у графа Г число вершин в объединении их окрестностей, Г^ж) и Г1 (у), равно т'1, сели вершины х,у смежны, и 7'2, в противном случае.

В работе [37| было показано, что нетривиальный (не являющийся кликой) граф из класса 7Z{r, г) является регулярным и, как следствие, даже сильно регулярным. В своем доказательстве авторы [37] существенно использовали теорему Райзера |38| о решении матричного уравнения вида А2 = В + АЛ, где А — (0,1)-матрица некоторой схемы, ассоциированной с графом, Ю — диагональная матрица с диагональными элементами, связанными со степенями вершин в графе, Л — матрица, все элементы которой равны 1. Из теоремы Райзера следует, что Ю — скалярная матрица (за конечным числом исключений). Простым следствием этого факта является сильная регулярность графов из И(г, г). Поэтому далее графы класса г2) будем называть графами Райзера с параметрами (г1,г2).

Для графов Л', У с У(Х) П У(У) = 0 через X ® У обозначим граф, называемый прямой сулшой графов X и У, полученный объединением множеств вершин X и У, причем каждая вершина X смежна со всеми вершинами У. Теорема 4.4. Пусть Г — граф Райзера с параметрами (г1,г2). Тогда выполняется одно из следующих утверждений:

(1) Г — сильно регулярный граф с параметрами (ь,к,Х,/л), причем г\ — 2к - X, г2 = 2к- /1;

(2) Г = А'пхш © К[ для подходящих значений п,т,1, п ^ 1, таких, что Г\ = п ■ т + I, го — (п — 1) ■ т + I;

(3) Г является объединением изолированных клик порядка I, и г 1 — I,

Г2 = 2 ■ (г -1).

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

Список литературы

[1| Brouwer А.Е., Cohen A.M., Neumaier A. Distancc-rcgular graphs // Berlin, Heidelberg, New-York: Springcr-Verlag, 1989.

|2| Dels arte P. An algebraic approach to the association schemes of codign theory 11 Philips Res. Rep. Suppl. - 1973. - V. 10. - P. 1-97.

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

[4] Bannai R., Ito T. Algebraic combinatorics I: Association Schemes // Benjamin - Cummings, 1984.

[5| Cameron P.J., Praegcr C.E., Saxl ./., Seitz C.M. On the Sims conjecture and distance transitive graphs // Bull. London Mal.h. Soc. — 1983. — V. 15.

- P. 499-506.

[6| Terwilliger P. Distancc-rcgular graphs with girth 3 or 4. I // J. Combin. Theory Sar. B. - 1985. - V. 39. - P. 265-281.

[7] Bang S., Dubickas A., Koolen J.H., Moulton V. There are only finitely many distancc-rcgular graphs of fixed valency greater than two // arXiv.org: 0909.5253. [Электронный pccypc|

|8] Terwilliger P. A class of distance-regular graphs that are Q-polynoinial // J. Combin. Theory B. - 1986. - V. 40. - P. 213-223.

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

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

|11| Dam.ere,ll R.M. On Moore graphs // Math. Proc. Cam.br. Phil. Soc. — 1973.

- V. 74. - P. 227-236.

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

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

[14] Nomura К. Homogeneous graphs and regular near polygons // J. Combin. Theory Ser. B. - 1994. - V. 60. - P. 63-71.

[15] Jurisic, A., Koolen, J.H. A local approach to 1-homogcncous graphs // Des. Codes Cryptoyr. - 2000. - V. 21. - P. 127-147.

[16[ Koolen J.H., Bang S. On distance-regular graphs with smallest eigenvalue at least -m // ,/. Combin. Theory Ser. B. — 2010. — V. 100, №6. — P. 573-584.

[17] Koolen J.H., Markowsky G., Park .1. There arc only finitely many dislancc-rcgular graphs with valency к ^ 3, fixed ratio k2/k, and large diameter ,// aiXiv.org: 1012.2632. [Электронный pecypc|

[18| Koolen J.H., Park ,J. Shilla distance-regular graphs // European ,1. Comb. — 2010. - V. 31, №8. - P. 2064-2073.

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

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

[21] Hiraki A., Koolen J.H. An improvement of the Ivanov bound // Annals of Combinatorics. — 1998. — V. 2, №2. — C. 131-135.

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

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

[24] Brouwer A.E., Haemers W.H. Spectra of graphs // Springer, 2012.

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

[26] Jurisic A., Koolen J.H. 1-Homogeneous graphs with cocktail party /x-graphs // J. Alg. Combin. - 2003. - V. 18. - P. 79-98.

[27[ 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.

[28] Fon-Der-Flass D.G. There exists no distancc-rcgular graph with intersection array {5,4,3,3; 1,1,1,2} // ,/. Algrebraie Com,bin. - 1993. - V. 2. - P. 49-56.

[29] Coolsaet, K. A distance regular graph with intersection array (21,16,8; 1,4,14) docs not exist If Ev.rope.an J. Com,bin. — 2005. — V. 26. - P. 709-716.

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

[311 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.

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

[33] Bang S., Hiraki A., Koolen J.H. Dclsarte cliquc graphs // European J. Combin. - 2007. - V. 28, X°-2. - P. 501-516.

[34] Cameron P..J., Goet.hals J.M., Seidel J.J., Shult E.E. Line graphs, root systems, and elliptic geometry // J. Algebra. — 1976. — V. 43. — P. 305—327.

[35] BI.okh.ms A., Brouwcr A.E. Determination of the distancc-rcgular graphs without 3-claws 11 Discrete. Math. - 1997. - V. 16. - P. 225-227.

|36) Bang S., Koolen J.H. Nonexistence of distance-regular graphs with intersection array {3a+ 3, 2a+ 2, a + 2 -/3\ 1,2,3/3} // Shanghai Conference on Alqcbraic Com.binat.orics. — 2012. [Электронный ресурс]

[37] Abdollah Khodkar, Leach D., Robinson D. Every (2, r)-Regular Graph is Regular // Utilitas Mathematica. - 2007. - V. 73. - P. 169-172.

[38] Ryscr H.J. A generalization of the matrix equation A2 = J // Linear Algebra and. Appl. - 1970. - V. 3. - P. 451-460.

Публикации автора по теме диссертации в журналах из перечня ВАК ведущих рецензируемых научных изданий

[391 Гаврилюк Л.Л., Махнев A.A. Графы Тервиллигера с ц < 3 // Математические заметки. — 20U7. — Т. 82, № 1. — С. 14-26.

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

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

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

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

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

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

[46j Gavrilyuk A.b. Oil Terwilliger graphs and the Koolen - Park inequality // Electronic Journal of Combinatorics. — 2010. — V. 17. — Paper №125.

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

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

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

¡50] Gnvrilyuk A.L., Mnkhnc.v 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.

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

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

Прочие публикации автора но теме диссертации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписано в печать 22.10.2012 Формат 60x84 1/16

Усл. печ. л. 2,0 Тираж 80 экз. Заказ 3692

Отпечатано в типографии ООО "Издательство УМЦ УПИ" г. Екатеринбург, ул. Гагарина, 35 а, оф. 2 Тел.: (343) 362-91-16, 362-91-17

Введение

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

Обозначения

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

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

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

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

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. Махневым, Го Вэнбинем соответственно). Все совместные работы написаны в нераздельном соавторстве.

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.