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

• Горяинов, Сергей Викторович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Горяинов, Сергей Викторович

Содержание

Введение

1 Определения, обозначения и предварительные результаты

1.1 Сильно регулярные и дистанционно регулярные графы

1.2 Схемы отношений

1.3 Графы Деза

2 Об изоморфизме между дистанционно-регулярными графами

2.1 Предварительные определения и результаты

2.2 Графы Мэтона М(2,д) и графы Мухаметьянова Гв и ^

2.3 Гв — М{2, д)

2.4

3 О вершинной связности одного класса графов Деза

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

3.2 Вершинная связность графов Деза из класса V

3.2.1 Сведение задачи к трем случаям

3.2.2 Графы Деза, полученные из графов п х п-решетки

3.2.3 Графы Деза, полученные из Т(п)

3.2.4 Графы Деза, полученные из спорадических графов Зей-деля

3.2.5 Доказательство теоремы

3.3 Заключение

4 Точные графы Деза, имеющие 14, 15 и 16 вершин

4.1 Отбор допустимых наборов параметров

4.2 Перебор матриц смежности

4.3 Отбор попарно неизоморфных графов

4.4 Поиск конструкций для найденных графов Деза

4.5 Заключение

5 Кэли-Деза графы, имеющие менее 60 вершин

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

5.2 Описание алгоритма

5.2.1 Получение вспомогательной информации из системы GAP

5.2.2 Нумерация подмножеств элементов групп

5.2.3 Построение дерева перебора

5.3 Результаты

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

Приложения

Приложение А: Основные процедуры

Приложение Б: Результаты перебора Кэли-Деза графов

Для фиксированной группы

Для фиксированного графа

Введение диссертации (часть автореферата) на тему «О некоторых классах вершинно-транзитивных графов»

Введение

Комбинаторика — раздел математики, изучающий различные задачи построения и перечисления дискретных объектов и отношения на них. Задача построения заключается в построении и изучении необходимых и достаточных условий существования множеств с заданными свойствами.

Одними из первых в этой области были исследования, связанные с вероятностными аспектами азартных игр (кости, карты).

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

На стыке комбинаторики с анализом возникла самостоятельная аналитическая комбинаторика, использующая, в частности, аппарат теории функций комплексного переменного и теории производящих функций. На стыке с линейной алгеброй и теорией групп появилась так называя алгебраическая комбинаторика, включающая в себя, в большей степени, теорию дизайнов (блок-схем), теорию кодирования и теорию графов. Так, язык линейной алгебры оказался удобным для описания самих дискретных объектов, тогда как теория групп (и теория конечных групп, в частности) естественным образом описывает определенного рода симметрии этих объектов. Классическим примером "богатых" с точки зрения количества симметрий объектов являются Платоновы тела. Отметим свойства эквивалентности как вершин, так и ребер этих фигур. На языке теории групп эти свойства носят название вершинной и реберной транзитивности графа, отвечающего илатонову телу, вершинами которого являются вершины нлатонова тела, а ребра этого графа соотвеству-ют ребрам Платонова тела. Свойства вершинной и реберной транзитивности графа определяются через транзитивное действие группы автоморфизмов на

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

Помимо групповой симметрии, примеры которой приведены выше, можно определить комбинаторную симметрию, связанную с регулярностью внутренней структуры объекта. Конкретизируем эти понятия о симметрии на примере графов и установим их взаимосвязь. Вершинная регулярность заключается в том, что любая вершина в графе имеет одно и то же число общих соседей, а реберная регулярность заключается в том, что число общих соседей двух смежных вершин не зависит от выбора смежных вершин. Ясно, что вершинная транзитивность влечет вершинную регулярность, а реберная транзитивность влечет реберную регулярность. Также отметим ещё одно следствие такого рода: дистанционная транзитивность влечет дистанционную регулярность графа. Таким образом, групповая симметрия всегда влечет комбинаторную симметрию. Обратное в общем случае неверно. Так, например, хорошо известный граф Фрухта является минимальным асимметричным регулярным графом. Можно привести пример реберно регулярного, но не реберно транзитивного графа. Примером дистанционно регулярных графов, не являющихся вершинно транзитивными, а, значит, не являющихся дистанционно транзитивными, служит бесконечная серия так называемых скрученных графов Грассмана.

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

Таким образом, в алгебраической комбинаторике и в алгебраической теории графов, в частности, представляет интерес следующая задача: влечет ли данная комбинаторная симметрия групповую симметрию?

В качестве ещё одной иллюстрации связи комбинаторной симметрии с групповой отметим предложенную Бюкенхаутом [51] идею построения единой геометрической теории, в соответствии с которой каждая конечная простая группа представима группой автоморфизмов некоторой геометрической структуры из определенного, поддающегося описанию, класса конечных геометрий. Например, спорадические простые группы Фишера, Судзуки, Ма-клафлина, Холла-Янко, Рудвалиса и Хигмена-Симса были впервые построены как группы автоморфизмов сильно регулярных графов.

Известно, что если (7 — транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф Г ранга 3 с множеством вершин X, группа автоморфизмов которого допускает С в качестве подгруппы. Обратно, каждый граф ранга 3 является сильно регулярным графом.

Отметим другие задачи алгебраической комбинаторики.

В качестве примера задачи построения объектов с заданными свойствами можно упомянуть задачу построения дистанционно регулярного графа с заданным массивом пересечения. Если задача построения решена, то естественным образом возникает вопрос перечисления всех неизоморфных объектов с заданными свойствами. Например, задача перечисления вершинно транзитивных графов, не являющихся графами Кэли. В качестве примера такого графа можно привести граф Петерсена.

Самостоятельный интерес представляет изучение свойств объектов с заданными свойствами. Примерами таких задач могут служить поиск необходимых условий существования, задача проверки графа или класса графов на гамильтоновость (упомянем здесь гипотезу Ловаса о гамильтоновости связ-

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

Классической задачей в комбинаторике и в математике вообще является задача различения объектов по их инвариантам. Например, в случае дистанционно регулярных графов различие массивов пересечений влечет неизоморфизм графов, хотя совпадение не обязательно влечет изоморфизм. Решение такой задачи составляет главу 2 настоящей диссератции. В работе [48] были предложены две новых конструкции антиподальных дистанционно регулярных графов, связанных с группой PSL2(q), при этом автор оставил открытым вопрос об изоморфизме полученных графов уже известным с тем же массивом пересечений. В данной главе мы покажем, что дистанционно-регулярные графы, построенные в [48], изоморфны графам Мэтона при подходящих значениях параметров.

Графы Мэтона M(2,q) и графы Мухаметьянова Гв и Tj

Напомним, что группа PSL,2(q), q — рп, содержит точно два класса сопряженных элементов порядка р (см. лемму 2.2.1 ниже). Определим граф Г в, множеством вершин которого является множество В = gG U {g~l)G, где gG — класс сопряженных элементов порядка р в группе G = PSL2(рп), а множеством ребер является множество {{ж, у}\ху~1 £ В}, где р — нечетное простое число и q = рп > 5. Обозначим через Г^ граф, полученный из графа Г в удалением ребер, соединяющих коммутирующие элементы из В.

Следующий результат был получен в недавней работе И.Т. Мухаметьянова.

Теорема 0.1 (Теорема 1, Теорема 2, [48]). Если q = 1 (mod 4), то граф Тв является дистанционно-регулярным с массивом пересечения {q, q—3,1; 1,2, q}.

Определим также Tj — граф, множеством вершин которого является мно-

жество всех элементов порядка р группы G, а множество ребер — множество {{ж, y)\xy~l е </}, где J — класс сопряженных инволюций группы G.

Следующий результат также был получен в упомянутой работе И.Т. Му-хаметьянова.

Теорема 0.2 (Следствие 1, [48]). Если q = 1,3 (mod 8), то граф Г/ не связен, и компонентами связности являются два изоморфных друг другу дистанционно-регулярных графа T'j, T"j с массивом пересечений {q, q —

Теперь мы напомним ещё один результат из теории дистанционно регулярных графов — конструкцию графов Мэтона M(2,q).

Теорема 0.3 (Proposition 12.5.3, [3]). Пусть q = rm + 1 — степень простого числа, где г > 1, при этом либо т четно, либо q является степенью 2. Пусть V — векторное пространство размерности 2 над полем F = снабженное невырожденной симплектической формой /. Пусть К — подгруппа индекса г мультипликативной группы F* и пусть Ъ € F*. Тогда граф М(т, q) с множеством вершин {Kv | v € V \ {0}}, где К и ~ Kv тогда и только тогда, когда f(u, v) € ЬК, является дистанционно-регулярным диаметра 3, имеет r{q+1) вершин и массив пересечений {q, q—m—1,1; 1, m, q}.

Заметим, что при т = 2 граф М(2, q) имеет массив пересечений {q, q —

Отметим, что граф М(т, q) не зависит(с точностью до изоморфизма) от выбора подгруппы К, формы В и Ь. Не теряя общности, мы можем положить

и вершины Ки, Kv £ V(r) смежны тогда и только тогда, когда f(u, v) = U\V2 — U2V1 G К = {±1}.

3,1; 1,2>9}.

3,1; 1,2, q}.

Ъ := 1, где 1 — единица группы F*, I Тогда для и, v € V \ {0}, f(u, v) = ( щ

Далее сформулируем первую проблему, естественно следующую из результатов работы [48].

Проблема 1.

1) Верно ли, что графы Г в и М(2,д) изоморфны?

2) Верно ли, что графы Г^ и М(2,<?) изоморфны?

В данной диссертации был получен положительный ответ на оба вопроса, сформулированный в виде следующей теоремы.

Теорема 0.4. Графы ГГ'} и граф Г(д) изоморфны М(2,д).

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

Графы Деза

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

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

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

Далее в работах Ермаковой и Кабанова 2006-2009 гг. [27-31] изучались графы Деза без 3-коклик.

В работах Шалагинова и Кабанова [44-46] изучались точные графы Деза, полученные с помощью автоморфизма порядка 2 из треугольных графов и дополнительным к ним, из решетчатых графов и дополнительных к ним. В частности, доказано, что графы Деза, полученные из треугольных графов и дополнительных к ним графов, с помощью этих автоморфизмов, однозначно определяются по своим параметрам и строению окрестностей;

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

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

Фундаментальным подклассом вершинно-транзитивных графов являются графы Кэли. В работах [33-36] были исследованы дистанционно-регулярные и сильно регулярные графы, являющиеся графами Кэли. В частности, получена классификация сильно регулярных графов Кэли циклических и диэд-ральных групп.

Напомним конструкцию графов Деза, которые являются неориентированными графами Кэли.

Теорема 0.5 (Proposition 2.1, [42]). Пусть D — подмножество элементов группы G такое, что (г) \G\=nu = k;

(и) единица е группы G не содержится в D; (Hi) D'1 = D;

(iv) 3 такие натуральные а,Ъ и к, что DD~l = аА+ЬВ+ке, где множества А, В и {е} образуют разбиение G;

(v) Пусть Г — граф, вершинами которого являются все элементы группы G, и вершины и и v смежны тогда и только тогда, когда v~xu €Е D.

Тогда Г — граф Деза с параметрами (п, k, Ъ, а), где Ь > а.

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

Пусть Гх и Гг — графы. Композицией Гх [Г2] графов Гх и Г2 называется граф с множеством вершин V^Ti) х V(Г2), и вершины (щ,и2) и (vj,v2) смежны тогда и только тогда, когда либо щ смежна с v\, либо щ = v\, и «2 смежна с г>2, см. [43].

Теорема 0.6 (Proposition 2.3, [42]). Если Ti — сильно регулярный граф с параметрами (n, fc, Л, д) и G2 — граф Деза с параметрами (п',к\Ь,а), то Гх [Г2] — регулярный граф степени (к' + кп') на пп' вершинах. Этот граф является графом Деза тогда и только тогда, когда

|{о + кп', Ъ + кп', /in', An' + 2к'}\ < 2.

Пример 0.1 (Example 2.4, [42]). Если Г1 = Кх (полный граф на х вершинах) и Г2 = уК2 (у копий К2), тогда граф Г1РГ2] является графом Деза с параметрами (2ху, 1 + 2у(х — 1), 2у(х — 1), 2 + 2у(х — 2)).

Пример 0.2 ( Example 2.5, [42]). Если Г1 — (п,к,Х) граф (сильно регулярный граф cfi = X)ur2 — Кп> (вполне несвязный граф), тогда Г^Гг] — граф Деза с параметрами (пп', kn', кп', An'). Эти графы однозначно определяются своими параметрами, что видно из следующей теоремы.

Теорема 0.7 (Theorem 2.6, [42]). Пусть Г граф Деза с параметрами (п, к, Ь, а). Тогда к = Ь в том и только том случае, если Г изоморфен Гх[Гг], где Гх — (nx, к\, Лх) и Г2 = КП2 для некоторых п\, П2, ki, Лх- При этом его параметры равны

п = П1П2, k = Ь = к\П2, а — ЛхП2.

Пусть Гх и Г2 — графы. Произведением Гх х Г2 называется граф на множестве вершин V(rx) х У(Г2), в котором вершины («х,«2) и (^1,^2) смежны тогда и только тогда, когда либо щ = v\ и щ смежна с V2, либо U2 = V2 и щ смежна с г>х, см. [43]. Будем называть произведение нетривиальным, если оба графа Гх и Г2 имеют хотя бы по 2 вершины. Заметим, что Гх х Г2 — Г2 х Гх, поэтому ниже в теореме порядок сомножителей не играет роли.

S

Теорема 0.8 (Theorem 2.8, [42]). Нетривиальное произведение графов Гх ХГ2 является графом Деза тогда и только тогда, когда выполняется одно из следующих условий:

1. Гх х Г2 = Кп х Кп, п >2, в этом случае Гх х Г2 — это сильно регулярный граф с параметрами (п2,2п — 2, п — 2,2);

2. Гх х Г2 = Кп х К^, п > 2, в этом случае Гх х Г2 — это граф Деза с параметрами (4п, 2п + 2, п — 2,2);

3. Гх = Кп, п > 2, и Г2 — граф Деза с параметрами (n',k,b,0), в этом случае Гх х Г2 —это граф Деза с параметрами (пп', k, Ь, 0);

4. Гх — граф Деза с параметрами (п, к, 2,0) и Г2 — граф Деза с параметрами (пк', 2,0), в этом случае Гх х Г2 — это граф Деза с параметрами (пп',к +к',2,0).

Пусть Г — граф Деза (не обязательно точный) с матрицей смежности М. Если перестановкой строк матрицы М мы можем получить симметричную матрицу М', то М2 = МТМ -- М^М' - М'2. Следовательно М' также

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

Теорема 0.9 (Theorem 3.1, [42]). Пусть Г — сильно регулярный граф с параметрами (п,к,\,р) с к ф ¡г, ц и с матрицей смежности М. Пусть Р — перестановочная матрица размера vxv, тогда РМ — матрица смежности графа Деза А с параметрами (п, к, тах{А, /л}, min{A, ц}) тогда и только тогда, когда Р задает инволютивный автоморфизм графа Г, переставляющий только несмежные вершины. Кроме того А — точный граф Деза в том и только том случае, если Р Ф I, А ^ О и цф 0.

Напомним определение схемы отношений Пусть X множество с п элементами и Ro,Ri,...,Rd — бинарные отношения, определенные на X. Пусть Ло, А\,..., Ad — (0,1) матрицы соответствующие этим отношениям, то есть (.х, у) принимает значение 1 в матрице Ai, тогда и только тогда, когда (х, у) € Ri. Тогда (X, {Ri}f=Q) называется симметричной схемой отношений с d классами, если

1. А> = /; 2- £< Ai = J;

3. Ai — Aj ;

4. для каждой пары индексов i и j верно равенство AiAj = YlkPijAk, Для некоторых констант р^.

Пусть Г — дистанционно регулярный граф и отношения Rq, Ri, ..., R^ определим так, что Ri состоит из пар вершин, находящихся в Г на расстоянии г, и d — диаметр графа Г, это дает нам схему отношений (см. [3]).

Пример 0.3. Дистанционно регулярный граф является графом Деза, если и только если выполняется одно из следующих условий: (г) d — 2 (граф

сильно регулярный); (и) А = О (гиперкубы и обобщения нечетных графов); (ш) \ = ц (обобщенные многоугольники с реберным размером 3 и реберный граф графа Петерсена).

Теорема 0.10 (Theorem 4.2, [42]). Пусть (X, {Ri}f=0) — симметричная схема отношений и F С {1,2,... ,d}. Граф Г с матрицей смежности YlfeF Af является графом Деза тогда и только тогда, когда сумма

принимает не более двух значений при к, пробегающем {1,2,... ,d}.

Пример 0.4 (Example 4.3, [42]). В случае схемы отношений с тремя классами необходимо выполнение только одного условия, чтобы Г был графом Деза. Учитывая результаты Ван Дама [Ц], видим, что это довольно частый случай. В этом случае Г иногда сильно регулярный или дистанционно-регулярный граф диаметра 3 (что легко проверить), но в остальных случаях Г — точный граф Деза. Для примера рассмотрим псевдоциклическую схему отношений с тремя классами. Псевдоциклические схемы на 28 точках (существует две такие схемы, найденные Мэтоном и Холманом) дают точные графа Деза с параметрами (28,9,4,2) и (28,18,12,10), псевдоциклическая схема на 13 точках дает граф Деза с параметрами (13,8,5,4). В последнем примере псевдоциклическая схема в действительности циклическая, и поэтому граф может быть также получен как граф Кэли с помощью теоремы 0.5. Еще один пример можно получить из треугольного графа Т{8) с правильной раскраской Хоффмана, при этом вершины покрашены в семь цветов. Здесь объединение двух классов дает точный граф Деза с параметрами (28,15, 8,6).

f,geF

Пример 0.5 (Example 4.46, [42]). Существует схема отношений с 4 классами, имеющая в качестве множества точек множество X пар вида (5, в).

Где Б — подмножество, содержащее два элемента из {1,2,3}, ив— отображение из Б в {0,1}. Свяжем с каждой парой (Б, в), (Б', в') пару чисел (п, т), где

т = |5 П Б'\, п = \{х : х 6 5 П 5', в(х) = в'(х)}\.

Существуют 5 пар чисел, возникающих таким образом, которые мы можем использовать для описания отношений на X:

Яо К-4

(ш,п): (2,2) (1,1) (2,1) (1,0) (2,0)

Оказывается, что (X, — симметричная схема отношений и, применяя

конструкцию из последней теоремы для этой схемы, получим при /^ = {1,2} и .Р = {2,3} два изоморфных графа Деза с параметрами (12,6,3,2).

Точные графы Деза, имеющие не более 13 вершин

В статье [42] приводится следующая таблица, полученная компьютерным перебором и содержащая все точные графы Деза, имеющие не более 13 вершин. Для каждого графа указана конструкция из числа приведенных ранее.

Таблица 0.0.1: Параметры точных графов Деза с п < 13

Параметры Комментарий

(8,4,2,0) 0.8.

(8,4,2,1) 0.5

(8,5,4,2) 0.5, 0.6

(9,4,2,1) 0.5

(9,4,2,1) 0.9

(10,5,4,2) 0.5, 0.6

(12,5,2,1) 0.5, 0.8

(12,6,3,2) 0.5, 0.5

(12,6,3,2)

(12,7,4,3) 0.5

(12,7,6,2) 0.5, 0.6

(12,9,8,6) 0.6, 0.8

(13,8,5,4) 0.5, 0.4

Отметим, что в работе [42] в таблице была сделана опечатка — для набора параметров (9,4, 2,1) обе конструкции были приписаны к одному графу.

Точные графы Деза, имеющие 14, 15 или 16 вершин

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

Проблема 2.

Найти и конструктивно описать неизомофрные точные графы Деза, имеющие Ц, 15 или 16 вершин.

В Главе 4 настоящей диссертации с помощью перебора были получены все неизоморные точные графы Деза, имеющие 14, 15 или 16 вершин. После чего была приведена конструкция для каждого из них. Таким образом результат Главы 4 расширяет указанный выше список.

Точные графы Деза, являющиеся графами Кэли

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

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

Проблема 3.

Описать неизоморфные точные графы Деза, являющиеся графами Кэли и имеющие менее 60 вершин.

Также отметим, что в работах [33-36] были исследованы некоторые свойства дистанционно-регулярных и сильно регулярных графов, которые являются графами Кэли. В частности, получена классификация сильно регулярных графов Кэли циклических и диэдральных групп.

В данной главе с помощью компьютерного перебора найдены все точные графы Деза, являющиеся графами Кэли и имеющие менее 60 вершин. Основным результатом Главы 5 является следующая теорема

Теорема 0.11. Точные графы Деза, которые являются графами Кэли, и имеют менее 60 вершин исчерпываются графами, представленными в Приложении Б к настоящей диссератции, в таблицах 1 и 2.

Вершинная связность графов Деза

Вершинная связность графа является одной из его характеристик, интересных и с практической, и с теоретической точек зрения. Для отдельных классов графов известны оценки и точные результаты: например, вершинная связность ^-регулярного графа Кэли не меньше |(к + 1) (см. [39]), а вершинная связность дистанционно регулярного графа равна его валентности, как следует из работы Браувера и Кулена [40] (для сильно регулярных графов аналогичное утверждение доказано Браувером и Меснером в [41]).

В связи с этими результатами представляет интерес вопрос о вершинной связности графов Деза.

Проблема 4.

Какова вершинная связность графов Деза?

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

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

Основным результатом Главы 3 является следующая теорема.

Теорема 0.12. Пусть А — граф Деза, полученный из сильно регулярного графа Г с помощью теоремы 0.9. Пусть Г имеет неглавные собственные значения г, s. Тогда имеет место один из следующих трех случаев:

(1) если г > 2 и s < —2, то вершинная связность графа А равна его валентности, а наименьшим разделяющим множеством является окрестность какой-либо вершины;

(2) s = —2, вершинная связность А равна его валентности за исключением случая, когда Г — это граф 3 х 3-решетки (б этом случае вершинная связность А равна 3);

(3) г < 2.

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

Работа состоит из введения, пяти глав и списка цитированной литературы, содержащего 59 наименования и двух приложений А и Б. Работа изложена на 118 страницах. Главы диссертации подразделяются на параграфы.

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

В главе 2 изучается вопрос изоморфизма графов Мэтона и дистанционно регулярных графов, полученных из двух других конструкций. Получен по-

ложительный ответ на вопрос об изоморфизме. Результаты этой главы представлены в теореме 2.4.

В главе 3 изучается вершинная связность одного класса графов Деза, полученных с помощью конструкции 0.9. Результатом этом главы является теорема 3.1

В главе 4 с помощью компьютерного перебора получена классификация точных графов Деза, имеющих 14,15 или 16 вершин.

В главе 5 с помощью компьютерного перебора получена классификация точных графов Деза, являющихся графами Кэли и имеющих менее 60 вершин.

Основные результаты, полученные в работе, являются новыми.

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

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

Основные результаты диссертации опубликованы в работах [52]- [59]. Работы [52], [54], [56], [57], выполнены в нераздельном соавторстве с JI.B. Ша-лагиновым. Работы [53], [58] выполнены в нераздельном соавторстве с A.JI. Гаврилюком и В.В. Кабановым.

Работы [53]- [55] опубликованы в печатных и электронных изданиях из списка ВАК. Работа [56] опубликована в тезисах всероссийской конференции. Работа [57] опубликована в материалах международного семинара. Работа [58] опубликована в тезисах международной конференции. Работа [59]

опубликована в материалах международной конференции.

Основные результаты работы докладывались на: 42-й Всероссийской молодежной школе-конференции «Современные проблемы математики» ИММ УрО РАН (Екатеринбург, 2011 г.), Международной (43-ей Всероссийской) молодежной школе-конференции «Современные проблемы математики» ИММ УрО РАН (Екатеринбург, 2012 г.), Международной(44-ой Всероссийской) молодежной школе-конференции «Современные проблемы математики» ИММ УрО РАН (Екатеринбург, 2013 г.), Международную конференции "Мальцев-ские чтения" (Новосибирск 2012 и 2013 гг), Одиннадцатом международном семинаре "Дискретная математика и ее приложения", посвященном 80-летию со дня рождения академика О.Б. Лупанова (Москва 2012), Международной конференции по теории групп, посвященной 70-летию со дня рождения профессора В.Д. Мазурова (Новосибирск 2013).

Список литературы диссертационного исследования кандидат наук Горяинов, Сергей Викторович, 2014 год

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

[1] М. Hall, Jr.: Combinatorial theory // Wiley, New-York, 1986.

[2] E. Bannai, T. Ito: Algebraic combinatorics I: Association schemes // Benjamin, New-York, 1984.

[3] A.E. Brouwer, A. Neumaier, A.M. Cohen: Distance-regular graphs // Springer-Verlag: Berlin, New-York, Heidelberg, 1989.

[4] P.J. Cameron, J.H. van Lint: Designs, graphs, codes and their links // London Math. Soc. Student Texts, Vol. 22. Cambridge: Cambridge Univ. Press, 1991.

[5] J.H. van Lint: Intoduction to coding theory // Springer-Verlag: Berlin, New-York, Heidelberg, 1998.

[6] M.D. Gordon: Perfect single error-correcting codes in the Johnson scheme // IEEE Trans. Inform. Theory., Vol. 52, No. 10 (2006), pp. 4670-4672.

[7] A. Neumaier: Completely regular codes // Discrete Math., Vol. 106/107 (1992), pp. 353-360.

[8] Bannai E. Ito Т.: Algebraic combinatorics I: Association schemes//Benjamin-Cummings Lecture Note Series 58, Benjamin/Cummings, London, 1984.

[9] Bose R.C.: Strongly regular graphs, partial geometries and partially balanced designs// Pacific J. Math., 1963, V.13, P.389-419.

[10] Cameron P. J.: Partial lambda - geometries of small nexus/Cameron P. J. and Drake D. F// Combinatorial mathematics, optimal designs and their applications, J. Srivastava (Editors), Fort Collins, 1978, Ann Discrete Math 6, NorthHolland, 1980.

[11] Chang L.C.: The uniqueness and nonuniqueness of triangular association schemes// Sci. Record, 1959, Vol.3, P.604-613.

[12] Chang L.C.: Association schemes of partially balanced block designs with parameters v = 28, ni = 12, n0 = 15 and p2n = 4// Sci. Record, 1950, Vol.4, P.12-18.

[13] Cigic V.: Some new partial symmetric designs derived from symmetric designs with 1 > 1// Glasnik Matematicki, 1996, V.31(51), P.47-51.

[14] Van Dam E. R.: Graphs with few eigenvalues - An interplay between combinatorics and algebra// PhDthesis, Tilburg University, Tilburg, 1996.

[15] Deza A.: The ridge graph of the metric polytope and some relatives / Deza A. and Deza M// NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 440, Kluwer Acad. Publ., Dordrecht, 1994.

[16] Gropp H.: On symmetries patial configurations// Discrete Math, 1994, V.125, P.201-209.

[17] Higman D. G.: Finite permutations group of rank 3// Math. Z., 1964, V.86, P. 145-156.

[18] Higman D.G.: Strongly regular designs and coherent configurations of type

3 2 3

// European J. Combin., 1988, V.9, P.411-422.

[19] Hoffman A.J.: On the line-graphs of the complete bipartite graph // Ann. Math. Stat., 1964, V.35, P.883-885.

[20] Hoffman A.J.: On the uniqueness of the triangular association scheme// Ann. Math. Stat., 1960, Vol.31, P.492-497.

[21] Hoffman A.J.: On the exceptioal case in a characterization of the arcs of complete graphs// IBM J. Res. Develop., 1960, Vol.4, P.487-496.

[22] Hughes D. R.: On designs// Geometries and designs, Lecture Notes in Math., 1981, V. 893, P.43-67.

[23] Moon J.: On the line-graph of the complete bigraph // Ann. Math. Stat., 1963, V. 34, P.664-667.

[24] Mulder H. M.: The interval function of a graph// PhD Thesis, Free University Amsterdam, 1980, MCTractl32, CWI, Amsterdam, 1980.

[25] Shrickhande, S.S.: The uniqueness of the association scheme // Ann. Math. Stat., 1959, V.30, P.781-798.

[26] Guo J.: Deza graphs based on symplectic spaces/ Guo J., Wang K. and Li F.// European Journal of Combinatorics, 2010, V.31, P. 1969-1980.

[27] Ермакова Г. M.: Две задачи алгебраической теории графов// Автореферат диссертации на соискание ученой стетпени кандидата ф.-м. н., УрО РАН, Екатеринбург, 2009.

[28] Ермакова Г. М.: Графы Деза, которые являются кликовыми расширениями сильно регулярных графов/ Ермакова Г. М., Кабанов В. В// Проблемы теоретической и прикладной математики: труды 37-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2006, С. 27-29.

[29] Ермакова Г. М.: Точные графы Деза без 3-коклик с большим fi/ Ермакова Г. М., Кабанов В. В// Проблемы теоретической и прикладной математики: труды 38-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2007, С. 31-34.

[30] Ермакова Г. М.: Точные графы Деза, которые являются соединением сильно регулярных графов или точных графов Деза/ Ермакова Г.

М., Кабанов В. В// Проблемы теоретической и прикладной математики: труды 39-й Всероссийской моложежной конференции, Екатеринбург: УрО РАН, 2008, С. 11-15.

[31] Ермакова Г. М.: Некоторые свойства точных графов Деза без 3-коклик с ¡л— Ь// Проблемы теоретической и прикладной математики: труды 40-й Всероссийской моложежной школы-конференции, Екатеринбург: УрО РАН, 2009, С. 19-27.

[32] Гаврилюк A.JL, Шалагинов Л.В.: О графах Деза с 4-мя различными собственными значениями // Тезисы Международной (43-ей Всероссийской) молодежной школы-конференции. Екатеринбург, 2012. С. 20-23.

[33] Bridges W.G., Mena R.A.: Rational circulants with rational spectra and cyclic strongly regular graphs, // Ars Combin. 1979. Vol. 8. P. 143-161. .

[34] Ma S.L.: Partial difference sets, // Discrete Math. 1984. Vol. 52. P. 75-89.

[35] Miklavic S., Potocnik P.: Distance-regular circulants, // European Journal of Combinatorics. 2003. Vol. 24. P. 777-784.

[36] Miklavic S., Potocnik P.: Distance-regular Cayley Graphs on Dihedral Groups, // Journal of Combinatorial theory. 2D07. Vol. 97, Is. 1. P. 14-33.

[37] Muzychuk M.: A solution of the isomorphism problem for circulant graphs // Proc. London Math. Soc. 2004. Vol. 88(3), P. 1-41.

[38] Beineke L.W., Wilson R.J., Cameron P.J.:Topics in algebraic graph theory. Cambridge University Press, 2004. 276 p.

[39] Godsil C., Royle G. Algebraic Graph Theory. New-York: Springer-Verlag, 2001. 439 p.

[40] Brouwer A.E., Koolen J.H. The vertex-connectivity of a distance-regular graph // Europ. J. Combin. 2009. Vol. 30. P. 668-673.

[41] Brouwer A.E., Mesner D.M. The connectivity of strongly regular graphs // Europ. J. Combin. 1985. Vol. 6. P. 215-216.

[42] Erickson M., Fernando S., Haemers W.H., Hardy D., Hemmeter J.

Deza graphs: A generalization of strongly regular graphs //J. Comb. Des. 1999. Vol. 7. P. 359-405.

[43] Харари Ф. Теория графов. M.: Мир, 1973. 300 с.

[44] Кабанов В.В, Шалагинов JI.B. О графах Деза с параметрами решетчатых графов // Тр. Ин-та математики и механики УрО РАН. 2010. Т. 16, № 3. С. 117-120.

[45] Шалагинов JI.B. О графах Деза с параметрами треугольных графов // Тр. Ин-та математики и механики УрО РАН. 2011. Т. 17, № 1. С. 294298.

[46] Горяинов С.В., Шалагинов JI.B. О графах Деза с параметрами графов, дополнительных к треугольным и решётчатым // Дискретн. анализ и исслед. опер. 2013. Т. 20, № 2. С. 3-14.

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

[48] Mukhametyanov I. Т. , On distance-regular graphs on the set of nonidentity p-elements of the group Ь2{рп) // Tr. Inst. Mat. Mekh. UrO RAN, 18, N3 (2012), 164-178.

[49] Belonogov V.A. , Representations and charactcrs in finite group theory, // Sverdlovsk: Ural Branch of Academy of Science, USSR. (1990). 380 p.

[50] The GAP Group, GAP — Groups, Algorithms, and Programming, Ver. 4.7.4. 2014. URL: http://www.gap-system.org.

[51] Buekenhout F. Diagrams for geometries and groups// J. Combin. Theory. Ser. A. 1979. Vol. 27. P.121-151.

Работы автора по теме диссертации

[52] С. В. Горяинов, JI. В. Шалагинов: О графах Деза на 14, 15 и 16

вершинах // Сиб. электрон, матем. изв., 8 (2011), 105-115

[53] A. Л. Гаврилюк, С. В. Горяинов, В. В. Кабанов: О вершинной связности графов Деза// Тр. ИММ УрО РАН, 19, № 3, 2013, 94-103

[54] С. В. Горяинов, Л. В. Шалагинов: Кэли-Деза графы, имеющие менее 60 вершин// Сиб. электрон, матем. изв., 11 (2014), 268-310

[55] S. V. Goryainov: On isomorphism between distance-regular graphs// Сиб. электрон, матем. изв., 11 (2014), 311-320

[56] С. В. Горяинов, Л. В. Шалагинов: О графах Деза на 14, 15 и 16

вершинах // Соврем, пробл. математики: тез. 42-й Всерос. молодеж. шк.-конф.- ИММ УрО РАН, 2011.- С.192-194.

[57] С. В. Горяинов, Л. В. Шалагинов: О графах Деза, являющихся графами Кэли // Материалы XI международного семинара "Дискретная математика и ее приложения", посвященного 80-летию со дня рождения О.Б.Луианова, Москва, 18-23 июня 2012 г., С. 277-278

[58] А. Л. Гаврилюк, С. В. Горяинов, В. В. Кабанов: О вершинной связности одного класса графов Деза// Соврем, проблемы математики: тез. Междунар. (44-й Всерос.) молодеж. шк.-конф.- ИММ УрО РАН, 2013.-С.10-12.

[59] S. V. Goryainov: On isomorphism between two constructions of antipodal distance-regular graphs // The International Conference on Group Theory

in Honor of the 70th Birthday of Professor Victor D. Mazurov, Novosibirsk, July 16 - 20, 2013