Авторефераты по всем темам  >>  Авторефераты по разным специальностям РОССИЙСКАЯ АКАДЕМИЯ НАУК Уральское отделение РАН Институт математики и механики им. Н.Н. Красовского

На правах рукописи

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

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

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

АВТОРЕФЕРАТ

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

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

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

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

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

Официальные оппоненты:

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

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

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

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

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

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

Ученый секретарь диссертационного совета Д 004.006.кандидат физ.-мат. наук И.Н. Белоусов

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

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

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

Напомним одно из нескольких эквивалентных определений дистанционной регулярности графа. Для графа и его вершины x обозначим через i(x) множество вершин из , находящихся на расстоянии i от x. Граф называется дистанционно регулярным, если для любого l = 0,..., d := diam() и любой пары вершин x, y, находящихся на расстоянии l в , множество i(x) j(y) содержит точно pl вершин, причем число pl зависит только от ij ij i, j, l, но не от выбора конкретной пары вершин x, y на расстоянии l. Числа pl ij называются числами пересечений графа. Обычно дистанционно-регулярный граф описывается массивом пересечений:

{b0, b1,..., bd-1; c1, c2,..., cd}, где bi = pi, ci = pi, 1,i+1 1,i-поскольку все числа пересечений могут быть вычислены из этого массива.

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

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

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

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

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

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

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

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

Данная гипотеза верна в предположении дистанционной транзитивности графа, см. [5]. Ее сложность в общем случае можно пояснить следующим образом. Известно [1, Предложение 4.1.6], что в массиве пересечений любого дистанционно регулярного графа выполняются неравенства bi bi+1, ci ci-1, 0 i d, т.е. последовательности {bi}d-1, {ci}d не возрастают и не убывают, соответi=0 i=ственно.

Поскольку b0 это валентность графа, то выполнение неравенства bi > bi+1 (или ci > ci-1) для всех i означало бы, что граф имеет диаметр не больше b0 и тогда очевидно, что число графов с ограниченными валентностью и диаметром конечно. Поэтому проблема заключается в доказательстве строгих неравенств или ограничении числа повторения нестрогих неравенств bi bi+1, ci ci-1.

В работе [6] Тервиллигер показал, что для массива пересечений дистанционно регулярного графа, содержащего порожденный 4-цикл, выполняются неравенства ci - bi ci-1 - bi-1 + a1 + 2, 1 i d, где по определению ai = b0 - bi - ci.

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

b0 + cd 2bd, a1 + 2 a1 + и таким образом гипотеза Баннаи и Ито верна в этом случае.

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

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

d g4b -1.

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

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

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

Для его формулировки нам понадобятся некоторые обозначения и поясне ния. Для произвольного графа определим его -кликовое расширение как граф , полученный заменой каждой вершины x графа на клику Lx порядка : Lx Ly = , если x = y, и попарным соединением всех вершин из двух таких клик Lx, Ly, если их прообразы x, y смежны в . Теперь, если это граф Тервиллигера с = 1 (класс таких графов не поддается описанию), то операция кликового расширения позволяет построить граф Тервиллигера с произвольным заданным = > 1.

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

Описанные выше конструкции графов Тервиллигера с > 1 не представляют интереса. Мы исключим эти случаи из общего рассмотрения следующим образом. Для подмножества вершин графа положим = xx, где x это шар радиуса 1 с центром в вершине x, т.е. x = {x} 1(x).

В частном случае множество 1(x) состоит из x и всех вершин y графа , смежных с вершиной x и всеми остальными вершинами из 1(x):

1(x) = {y : x y}.

Такое множество будем называть ядром вершины x. Нас будет также интересовать окрестность вершины за вычетом ее ядра, т.е. подграф x := 1(x) \ (1(x)).

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

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

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

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

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

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

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

Рассмотрим теперь подробнее класс графов Тервиллигера с = 2 при условии, что они не являются кликовыми расширениями и = . Окрестность вершины в графе из этого класса является графом Тервиллигера диаметра 2 с = 1. Графы Тервиллигера диаметра 2 с = 1, в свою очередь, представляют самостоятельный интерес и называются геодезическими графами диаметра 2 [1, Глава 1.17]. Некоторые свойства этих графов изучаются в четвертой главе диссертации.

Известны лишь три графа Тервиллигера с = 2, все они дистанционно регулярны: граф икосаэдра с массивом пересечениий {5, 2, 1; 1, 2, 5}, граф Доро {10, 6, 4; 1, 2, 5} и граф Конвея - Смита {10, 6, 4, 1; 1, 2, 6, 10}. В графе икосаэдра окрестность каждой вершины изоморфна пятиугольнику, а в двух других графах окрестность каждой вершины изоморфна графу Петерсена.

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

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

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

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

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

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

А. Юришич и Дж. Кулен [15] показали, что икосаэдр, графы Доро и Конвея - Смита являются единственными 1-однородными графами Тервиллигера с > 1. Напомним, что граф обладает свойством h-однородности, если для всех пар вершин x, y , находящихся на расстоянии h, всех индексов i, j = 0,..., diam() и всех вершин z i(x) j(y) число вершин в 1(z) i(x) j(y) зависит только от i, j, но не от выбора вершин x, y, z с указанными свойствами. Очевидно, что 0-однородность эквивалентна дистанционной регулярности. К. Номура [14] показал, что 1-однородные графы содержатся в классе дистанционно регулярных графов.

Дж. Кулен и С. Банг [16] доказали, что для всякого натурального числа m существует лишь конечное число дистанционно регулярных графов Тервиллигера с c2 2 и наименьшим собственным значением графа d -m (этот результат является частным случаем их более общего результата, см.

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

В [17] Дж. Кулен и др. показали, что для всякого вещественного числа T 1 существует конечное множество дистанционно регулярных графов bТервиллигера с c2 > 1 и вторым собственным значением 1 -1 (известно, T см. [1, Теоремы 4.4.3, 4.4.11], что для любого дистанционно регулярного графа выполняется неравенство 1 b1 - 1, и все графы, для которых достигается равенство в последнем неравенстве, охарактеризованы). В той же работе ее авторы доказали, что дистанционно регулярный граф Тервиллигера с c2 > bи 1 - 1 является икосаэдром, графом Доро или Конвея - Смита.

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

s(a1 + 1) - bc2 - 1, s и заметили, что граф является графом Тервиллигера, если для некоторого s достигается равенство и любая 2-лапа графа содержится в s-лапе.

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

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

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

Первая глава диссертации завершается изучением локального строения гипотетических графов Тервиллигера с {3, 4}.

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

Граф Хоффмана - Синглтона является единственным сильно регулярным графом с параметрами (v, k, , ) = (50, 7, 0, 1), где v число вершин в графе, k валентность, (соотв. ) число общих соседей пары смежных (соотв. несмежных) вершин. В обозначениях дистанционно регулярного графа имеем k = b0, = a1, = c2.

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

Пусть граф дистанционно регулярен и окрестность каждой его вершины является сильно регулярным графом с параметрами (v, k, , ). Первые элементы массива пересечений определяются локальным строением: b0 = v (степень вершины в ), b1 = v -k -1 (т.е. a1 = k). Но уже параметр c2 может принимать несколько значений (несложно показать, что для пары вершин x, y , находящихся на расстоянии 2, подграф 1(x) 1(y) будет регулярным графом степени , и c2 делит b0b1).

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

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

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

Махнева и др. [20].

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

Если содержит 4-цикл, то для оценки диаметра можно использовать границу Тервиллигера, не очень эффективную, если параметр a1 мал в сравнении с b0. Если же может не содержать 4-циклов, то граница Иванова дает оценку диаметра, экспоненциально зависящую от b0, а некоторые уточнения этой границы, например, Хираки - Кулена [21], зависимость вида b3.

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

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

Один из них основан на том, что матрица смежности графа HoSi имеет спектр 71, 228, -321. Теперь, рассматривая изолированные подграфы C := i-1(x) 1(y) и B := i+1(x) 1(y) для пары вершин x, y , находящихся на расстоянии i 2, по теореме о переплетении спектров [24, Теорема 2.5.1] имеем, что максимальное собственное значение по крайней мере одного из графов B или C не больше 2 (т.е. второго по величине собственного значения графа HoSi). По теореме Смита [1, Теорема 3.2.5] граф, максимальное собственное значение которого не превосходит 2, является объединением изолированных подграфов из графов X, где X {An,Dn,E6,E7,E8}. Далее, комбинаторными рассуждениями удается показать, что в случае diam() и граф B, и граф C содержат порожденный подграф, не являющийся под графом из X, что приводит нас к противоречию.

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

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

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

Как упоминалось ранее, одним из наиболее общих в теории дистанционно регулярных графов является вопрос существования графа с заданным массивом пересечений. Известно, см. [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(i)] границу Хоффмана - Дельсарта, согласно которой клика в дистанционно регулярном графе с наименьшим собk ственным значением -m и валентностью k имеет порядок не более чем 1+.

m Клика называется кликой Дельсарта, если ее порядок достигает этой границы. Дистанционно регулярный граф называется геометрическим, если в нем существует множество L клик Дельсарта такое, что любое ребро графа принадлежит единственной клике из L. Геометрическими являются многие УклассическиеФ семейства графов: Хемминга, Джонсона, Грассмана, двойственных полярных пространств, отношений билинейных форм и др. Название УгеометрическийФ обусловлено тем, что множество вершин такого графа, рассматриваемое как множество точек, и множество клик Дельсарта, рассматриваемых как прямые, образуют систему инцидентности на точках и прямых, удовлетворяющую аксиомам частичной геометрии [33].

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

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

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

Одно из семейств имеет вид {3 + 3, 2 + 2, + 2 - ; 1, 2, 3}, (1) где > 1 целые числа.

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

существуют ли дистанционно регулярные графы с массивом (1) при > 1? В 2012 г. Дж. Кулен и С. Банг [36] показали, что ответ на этот вопрос отрицателен за исключением случая = 14, = 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.1], что любой такой граф является либо объединением клик с одной общей вершиной, либо сильно регулярным графом, либо графом, в котором встречаются только две степени вершин, т.е. бирегулярным графом. Графы первого типа не представляют интереса, среди графов второго типа известно существование только графов Мура: пятиугольника, графа Петерсена и графа Хоффмана - Синглтона.

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

Х граф на 2l +1 вершинах, в котором подграф A это l-коклика, подграф B является объединением изолированной вершины (смежной со всеми вершинами из A) и l-клики;

Х для натурального l такого, что существует аффинная плоскость (X, L) порядка l, вершины подграфа A точки плоскости, а подграф B это граф, дополнительный к графу коллинеарности прямых плоскости, и точка смежна с прямой, если точка лежит на этой прямой;

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

Х для натурального l такого, что существует проективная плоскость (X, L) порядка l, и полярности этой плоскости определим граф на множестве точек X, в котором две вершины x, y смежны тогда и только тогда, когда x y.

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

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

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

Показано, что для любого r = 1,..., |A| и любых двух r-элементных подмножеств A1, A2 A графы, индуцированные множествами A1 B и A2 B, изоспектральны (причем легко привести пример, когда такие графы будут неизоморфными). Кроме того, получены некоторые новые необходимые условия существования бирегулярных геодезических графов диаметра 2, которые позволили уточнить классификацию графов Тервиллигера с = 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

международная конференция по теории графов (г. Блед (Словения), 2011);

международная конференция Геометрическая и алгебраическая комбинаторика (GAC) (г. Оистервийк (Нидерланды), 2011).

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

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

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

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

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

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

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

Результаты главы опубликованы в статьях [39, 40, 41, 45, 46].

Для подмножества вершин графа определим := xx, где x это шар радиуса 1 с центром в вершине x, т.е. x := {x} 1(x), а для вершины x определим подграф x := 1(x) \ (1(x)).

Теорема 1.1. Если является регулярным графом Тервиллигера, содержащим хотя бы одну вершину x с условием |1(x)| < (), то подграфы y регулярны для всех вершин y .

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

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

Заметим, что в сильно регулярном графе с параметрами (v, k, , 1) окрестность любой вершины состоит из r = k/( + 1) изолированных s-клик, где s = + 1. Обозначим через F(s, r) класс сильно регулярных графов с параметрами (v, rs, s - 1, 1). В частности, класс сильно регулярных графов Мура совпадает с классом F(1, r) (и r {2, 3, 7, 57}). Примеры графов из класса F(s, r) при s > 1 не известны.

Если сильно регулярный граф Тервиллигера с = 2, то окрестность всякой вершины в сильно регулярный граф Тервиллигера с = 1, т.е.

граф из класса F(s, r) для подходящих s, r, причем параметры s, r не будут зависеть от выбора вершины из . Поэтому через G(s, r) обозначим класс сильно регулярных графов Тервиллигера с = 2, в которых окрестность каждой вершины граф из класса F(s, r).

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

Предложение 1.2. Пусть связный граф Тервиллигера с = 2 и = .

Тогда выполняется одно из следующих утверждений:

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

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

(3) диаметр больше 2; является бирегулярным графом, и если A (если B) множество его вершин меньшей (большей) степени, то окрестность вершины a из A содержится в B, окрестность каждой вершины b из B пересекает A по непустому множеству и верно одно из утверждений:

(i) 1(a) является графом Петерсена, а 1(b) граф, отвечающий полярности проективной плоскости порядка 3, (ii) 1(a) является графом Хоффмана-Синглтона, а 1(b) граф, отвечающий полярности проективной плоскости порядка 7, (iii) 1(a) является графом Мура степени 57, а 1(b) граф на множестве точек и прямых аффинной плоскости порядка 56, в котором множество точек совпадает с A 1(b), точка и прямая смежны, если они инцидентны в плоскости, и две прямые смежны, если они паралльлельны, (iv) 1(a) является графом Мура степени 57, а 1(b) граф, полученный добавлением к подграфу из предыдущего пункта клики из 57 вершин, отвечающих классам параллельных прямых аффинной плоскости, и каждая прямая смежна с классам параллельных прямых, содержащим эту прямую, (v) 1(a) является графом Мура степени 57, а 1(b) бирегулярный геодезический граф диаметра 2, в котором меньшая степень вершины равна 57, а большей 66 или 82.

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

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

Теорема 1.3. Если в графе Тервиллигера найдется хотя бы одна вершина x такая, что 1(x) граф Петерсена, то либо = x, либо является графом икосаэдра, графом Доро или графом Конвея - Смита.

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

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

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

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

(1) подграф на множестве вершин из с некликовыми окрестностями является 3-кликовым расширением графа с () = 1;

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

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

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

Заметим, что по теореме 1.4 в графе Тервиллигера с = 3 подграфы x также регулярны для всех x , при этом сам граф может не быть регулярным.

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

Первая глава диссертации завершается новой характеризацией известных графов Тервиллигера с = 2. Напомним, что граф называется вполне регулярным с параметрами (v, k, , ), если содержит v вершин, регулярен степени k, и для любой пары его смежных (соотв. находящихся на расстоянии 2) вершин x, y, подграф 1(x) 1(y) содержит точно (соотв. точно ) вершин. В частности, вполне регулярный граф диаметра 2 является сильно регулярным.

Теорема 1.5. Пусть вполне регулярный граф с параметрами (v, k, , ) с > 1. Пусть s 2 максимальное число такое, что для любой вершины x и любой пары несмежных вершин y, z из 1(x), существует s-коклика в 1(x), содержащая y, z. Тогда s ( + 1) - k - 1 max{ | 2 s s}, s и в случае равенства является графом икосаэдра, Доро или Конвея - Смита.

Отметим, что самостоятельный интерес могут представлять некоторые вспомогательные результаты из первой главы диссертации. Например, следующая лемма из [40] может быть полезна при изучении графов, в которых -подграфы являются (q + 1) (q + 1)-решетками (в частности, графы Грассмана Jq(v, d) удовлетворяют этому свойству). Напомним, что mn-решеткой называется прямое произведение двух клик порядков m и n.

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

Фактически, эта лемма обобщает теорему 1.17.1 из [1], классифицирующую графы Тервиллигера диаметра 2 с = 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, стр. 36], сводится к вопросу существования графов с массивами пересечений из теоремы 2.1.

Теорема 2.2. Пусть дистанционно регулярный граф Тервиллигера, имеющий массив пересечений {50, 42, 1; 1, 2, 50}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда p нечетно и верно одно из утверждений:

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

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

Теорема 2.3. Пусть дистанционно регулярный граф Тервиллигера, имеющий массив пересечений {50, 42, 9; 1, 2, 42}, G = Aut(), g элемент из G простого порядка p и = Fix(g). Тогда p нечетно и верно одно из утверждений:

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

(2) p = 7 и является объединением пяти изолированных 2-клик;

(2) p = 5 и является одновершинной кликой.

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

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

Доказательство следующего предложения основано на том, что второе по величине собственное значение графа HoSi равно 2.

Предложение 2.5. Диаметр связного локально HoSi графа не больше 7.

Теорема 2.6 позволяет ограничить диаметр дистанционно регулярного графа, в котором окрестности вершин сильно регулярны с известными параметрами. Предположим, что является дистанционно регулярным локально S графом диаметра d > 3, с массивом пересечений {b0, b1,..., bd-1; c1, c2,..., cd} и различными собственными значениями 0 = b0 > 1... > d, где S класс сильно регулярных графов с параметрами (b0, a1, , ). Обозначим через r, s неглавные собственные значения (т.е. отличные от валентности a1) графов из b1 bкласса S. Заметим, что r > 0 и s < 0. Положим M := max{-s-1 -1, +1} и 1+r := max{1, |d|}. Через ki, как обычно, обозначим число вершин в подграфе i(x), которое не зависит от выбора вершины x . Пусть граф содержит точно v вершин.

Далее, для i {1,..., d - 1} определим функцию vi(x):

bi x i (bc + 1 + )(1 - (b )2) ci+i-1 vi(x) := ki.

x bi i (1 - (b )2(bc + 1 + )) ci+0 i-Теорема 2.6. Выполняется неравенство a1 M, и если для некоторого ci bi i {1,..., d-1} выполняется неравенство 2( + 1 + ) < b2, то верны bi-1 ci+1 следующие утверждения:

ci bi (1) v vi() и, в частности, если M2( + 1 + ) < b2, то bi-1 ci+1 bi i (bc + 1 + )(1 - (a )2) ci+1 bi-vi() ki ;

bi i (1 - (M )2(bc + 1 + )) b0 i-1 ci+ln(2 (vi() - 1)) (2) d + 1, где h минимум функции h H(x, y) := ln(( b0 - y + b0 - x)/( b0 - y - b0 - x)) b1 bв области [a1, - 1] [-1-r - 1, s].

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

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

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

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

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

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

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

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

Предложение 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].

Графы 1 и 2 с матрицами смежности соответственно A1 и A2 называются R-изоспектральными, если для любого y R обобщенные матрицы смежности yJ-A1 и yJ-A2, где J матрица из единиц, имеют одинаковый спектр.

Пусть бирегулярный геодезический граф диаметра 2, A множество его вершин меньшей степени , m := |A|, и B множество его вершин большей степени .

Теорема 4.1. Для любого r {1,.., m - 1} и любой пары подмножеств A1, A2 из A таких, что |A1| = |A2| = r, подграфы A1 B и A2 B являются R-изоспектральными.

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

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

(1) m - 1 q (mod s);

(2) число s делит q2(q - 1) и q3(1 + 2b) + q2(1 - b - 3a) + q(a + b) + c(q - 1), где a = (m - q)/s, b = ( - q - 1)/s, c = q2(q - 1)/s.

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

Далее через Knm будем обозначать полный многодольный граф с n долями порядка m. Кликой Kl порядка l называется полный граф на l вершинах.

Для натуральных чисел r1 и r2 рассмотрим класс графов R(r1, r2) со следующим свойством: для любого графа из этого класса и для любой пары различных вершин x, y графа число вершин в объединении их окрестностей, 1(x) 1(y), равно r1, если вершины x, y смежны, и r2, в противном случае.

В работе [37] было показано, что нетривиальный (не являющийся кликой) граф из класса R(r, r) является регулярным и, как следствие, даже сильно регулярным. В своем доказательстве авторы [37] существенно использовали теорему Райзера [38] о решении матричного уравнения вида A2 = D+J, где A (0, 1)-матрица некоторой схемы, ассоциированной с графом, D диагональная матрица с диагональными элементами, связанными со степенями вершин в графе, J матрица, все элементы которой равны 1. Из теоремы Райзера следует, что D скалярная матрица (за конечным числом исключений). Простым следствием этого факта является сильная регулярность графов из R(r, r). Поэтому далее графы класса R(r1, r2) будем называть графами Райзера с параметрами (r1, r2).

Для графов X, Y с V (X) V (Y ) = через X Y обозначим граф, называемый прямой суммой графов X и Y, полученный объединением множеств вершин X и Y, причем каждая вершина X смежна со всеми вершинами Y.

Теорема 4.4. Пусть граф Райзера с параметрами (r1, r2). Тогда выполняется одно из следующих утверждений:

(1) сильно регулярный граф с параметрами (v, k, , ), причем r1 = 2k - , r2 = 2k - ;

(2) = Knm Kl для подходящих значений n, m, l, n 1, таких, что r1 = n m + l, r2 = (n - 1) m + l;

(3) является объединением изолированных клик порядка l и r1 = l, r2 = 2 (l - 1).

Список литературы [1] Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin, Heidelberg, New-York: Springer-Verlag, 1989.

[2] Delsarte P. An algebraic approach to the association schemes of codign theory // Philips Res. Rep. Suppl. 1973. V. 10. P. 1Ц97.

[3] Van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs // препринт.

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

[5] 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.

[6] Terwilliger P. Distance-regular graphs with girth 3 or 4. I // J. Combin.

Theory Ser. B. 1985. V. 39. P. 265Ц281.

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

[8] Terwilliger P. A>

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] Damerell R.M. On Moore graphs // Math. Proc. Cambr. Phil. Soc. 1973.

V. 74. P. 227Ц236.

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

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

№ 10. C. 44Ц68.

[14] Nomura K. 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-homogeneous graphs // Des.

Codes Cryptogr. 2000. V. 21. P. 127 147.

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

[17] Koolen J.H., Markowsky G., Park J. There are only finitely many distanceregular graphs with valency k 3, fixed ratio k2/k, and large diameter // arXiv.org:1012.2632.

[18] Koolen J.H., Park J. Shilla distance-regular graphs // European J. Comb.

2010. V. 31, №8. P. 2064Ц2073.

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

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

C. 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.

[23] 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. T. 16, №3. C. 105Ц116.

[26] Jurisic A., Koolen J.H. 1-Homogeneous graphs with cocktail party -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 distance-regular graph with intersection array {5, 4, 3, 3; 1, 1, 1, 2} // J. Algrebraic Combin. 1993. V. 2. P.

49Ц56.

[29] 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.

[30] 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.

[31] 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. Delsarte clique graphs // European J.

Combin. 2007. V. 28, №2. P. 501Ц516.

[34] 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.

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

[36] Bang S., Koolen J.H. Nonexistence of distance-regular graphs with intersection array {3+3, 2+2, +2-; 1, 2, 3} // Shanghai Conference on Algebraic Combinatorics. 2012.

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

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

Публикации автора по теме диссертации в журналах из перечня ВАК ведущих рецензируемых научных изданий [39] Гаврилюк А.Л., Махнев А.А. Графы Тервиллигера с 3 // Математические заметки. 2007. Т. 82, № 1. C. 14Ц26.

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

[41] Гаврилюк А.Л., Махнев А.А. Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена // Доклады РАН.

2008. Т. 421, № 4. C. 445Ц448.

[42] Гаврилюк А.Л., Вэнбинь Го, Махнев А.А. Об автоморфизмах графов Тервиллигера с = 2 // Алгебра и логика. 2008. Т. 47, № 5. C.

584Ц600.

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

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

[45] Гаврилюк А.Л. Графы Тервиллигера с = 4 // Труды Института математики и механики УрО РАН. 2009. Т. 15, № 2. C. 84Ц93.

[46] Gavrilyuk A.L. On Terwilliger graphs and the Koolen - Park inequality // Electronic Journal of Combinatorics. 2010. V. 17. Paper №125.

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

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

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

[50] 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.

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

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

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

[54] Гаврилюк А.Л. Дистанционно регулярный граф с массивом пересечений {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] Гаврилюк А.Л., Махнев А.А. Дистанционно регулярный граф с массивом пересечений {45, 30, 7; 1, 2, 27} не существует // Алгебра и геометрия:

тр. Междунар. конф., посвящ. 80-летию А.И. Старостина. ИММ УрО РАН, 2011. С.51Ц53.

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

КФУ, 2011. С.73Ц74.

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

2010. Т. 432, №5. С.583Ц587.

[59] Гаврилюк А.Л. Об одном неравенстве Кулена-Парка и графах Тервиллигера // Теория групп и ее прил: тр. 8-й Междунар. шк.-конф., посвящ.

75-летию В.А. Белоногова. ИММ УрО РАН, 2010. С.63Ц66.

[60] Гаврилюк А.Л. Об одном неравенстве Кулена-Парка и графах Тервиллигера // Проблемы теорет. и прикл. математики: тез. 41-й Всерос.

молодеж. конф. ИММ УрО РАН, 2010. С.10Ц13.

[61] Гаврилюк А.Л. Об одном неравенстве Кулена-Парка и графах Тервиллигера // Проблемы теорет. и прикл. математики: тр. 40-й Всерос.

молодеж. конф. ИММ УрО РАН, 2009. С.15Ц17.

[62] Гаврилюк А.Л., Махнев А.А., Падучих Д.В. О графах, в которых окрестности вершин изоморфны графу Гевиртца // Доклады РАН. 2009.

Т. 428, №3. С.300Ц304.

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

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

Изд-во ЮУрГУ, 2008. С.32Ц34.

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

[66] Гаврилюк А.Л., Махнев А.А. Графы Тервиллигера с 3 // Пробл.

теорет. и прикл. математики : тр. 38-й Регион. мол. конф., 29 янв.-февр. 2007. ИММ УрО РАН, 2007. С.18Ц22.

[67] Гаврилюк А.Л., Махнев А.А. Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена // Междунар.

конф. УАлгебра и ее прил.Ф, Красноярск, 12-18 авг. 2007: тез. докл.

2007. С.35Ц36.

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

   Авторефераты по всем темам  >>  Авторефераты по разным специальностям