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

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

Горяинов Сергей Викторович

О НЕКОТОРЫХ КЛАССАХ ВЕРШИННО-ТРАНЗИТИВНЫХ ГРАФОВ

Специальность 01.01.06 - математическая логика, алгебра и теория чисел

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

5 чед 2015

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

005558408

005558408

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

Научный руководитель:

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

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

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

Пономаренко Илья Николаевич,

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

Федеральное государственное бюджетное учреждение науки Санкт-Петербургское отделение Математического института им. В.А.Стеклова Российской академии наук, ведущий научный сотрудник.

Константинова Елена Валентиновна,

кандидат технических наук,

Федеральное государственное бюджетное учреждение науки Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, старший научный сотрудник.

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

Федеральное государственное автономное образовательное .учреждение высшего профессионального образования

«Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

Защита состоится 24 февраля 2015 года в 1530ни заседании диссертационного совета Д 004.006.03 при Федеральном государственном бюджетном учреждении науки Институте математики и механики им. H.H. Красовского Уральского отделения Российской академии наук (ИММ УрО РАН) по адресу: ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990.

С диссертацией можно ознакомиться в библиотеке и на сайте Федерального государственного бюджетного учреждения науки Института математики и механики им. H.H. Красовского Уральского отделения Российской академии наук (ИММ УрО РАН), http://www.imin.uran.ru/. Автореферат разослан^Зянваря 2015 года.

Ученый секретарь диссертационного совета, кандитат физ.-мат. наук

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

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

Постановка задачи и актуальность темы диссертации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Напомним, что группа РЙХгС*?), q = рп, содержит точно два класса сопряженных элементов порядка р Определим граф Гд, множеством вершин которого является множество В = да и (<7_1)с, где д° — класс сопряженных элементов порядка р в группе С = РБЬ2{рп), а множеством ребер являстся множество {{х, т/Цху-1 6 В}, где р — нечетное простое число и q = рп > 5. Обозначим через Г в граф, полученный из графа Гв удалением ребер, соединяющих коммутирующие элементы из В.

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

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

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

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

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

3,1; 1,2,?}.

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

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

Заметим, что при то = 2 граф М(2, q) имеет массив пересечений {q, q-3,1; 1,2, g}.

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

Тогда для и, v <= V \ {0}, f(u, v) = ( щ щ j

:= {±1} < F*, / :=

О 1 -1 О

щ

V2

= U\V2 — U2Vu

и вершины Ки,Ки € У(Г) смежны тогда и только тогда, когда f(u,v) = ЩУ2 ~ € К = {±1}.

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

Проблема 1.

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

2) Верно ли, что графы Г'7 и М{2, д) изоморфны?

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

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

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

Графы Деза

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

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

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

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

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

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

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

(i) |G| = п и \D\ = k;

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

(ni) D~l = D;

(iv) В такие натуральные а,Ъ и к, что DD~l = аА + ЬВ + ке,

где множества А, В и {е} образуют разбиение G;

(v) Пусть Г -- граф, вершинами которого являются все элементы группы G, и вершины и uv смежны тогда и только тогда, когда г>_1м € D. Тогда Г граф Деза с параметрами (n, k, b, а), где Ь > а.

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

Пусть Ti и Гг —• графы. Колтозицией Гх[Г2] графов и Г2 называется граф с множеством вершин V'(r'i) х У(Г2), и вершины {щ,и2) и (г>1,г»г) смежны тогда и только тогда, когда либо щ смежна с vi, либо щ = v\, и «2 смежна с v2, см. [43].

Теорема 6 (Proposition 2.3, [42]). Если Г1 — сильно регулярный граф с параметрами (п, к, А, /х) и Gi —- граф Деза с параметрами (п', к', Ь, а), то Г^Гг] — регулярный граф степени (к'+кп') на пп' вершинах. Этот граф является графом Деза тогда и только тогда, когда

\{а + кп',Ь + кп',цп',\п' + 2к'}\ < 2.

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

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

Теорема 7 (Theorem 2.6, [42]). Пусть Г граф Деза с параметрами (п, к, 6, а). Тогда к = b в том и только том случае, если Г изоморфен Г^Гг], где Г^ -— (щ, k\, Ai) и Гг ■ ■ КП2 для некоторых щ, п2, k\, Ai- При этом его параметры равны

п = П1П2, к = b = к\п2, а — А1П2.

Пусть Г1 и Г2 - графы. Произведением Tj х Гг называется граф на множестве вершин V(ri) х К(Г2), в котором вершины (щ,и2) и (wi,^) смежны тогда и только тогда, когда либо щ = Vi и и2 смежна с v2, либо и2 = v2 и и\ смежна с г>1, см. [43]. Будем называть произведение нетривиальным, если оба графа Tj и Г2 имеют хотя бы но 2 вершины. Заметим, что Tj х Г2 ~ Г2 х Г1, поэтому ниже в теореме порядок сомножителей не играет роли.

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

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

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

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

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

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

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

Напомним определение схемы отношений Пусть X множество с п элементами и До, Ri,..., Rd — бинарные отношения, определенные на X. Пусть Aq,Ai, ... ,Ad - - (0,1) матрицы соответствующие этим отношениям, то есть (х, у) принимает значение 1 в матрице Л¿, тогда и только тогда, когда (х,у) е Ri. Тогда (X, {/i,;}f,a0) называется симметричной схемой отношений с d классами, если

1. А„ = /;

2. Е; 4 = J;

3. Ai = Af\

4. для каждой нары индексов i и j верно равенство A{Aj = YlkPij^k, для некоторых констант р

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

Пример 3. Дистанционно регулярный граф является графом Деза, если и только если выполняется одно из следующих условий: (г) d = 2 (граф сильно регулярный); (И) А = 0 (гиперкубы и обобщения нечетных графов); (ill) А = ¡1 (обобщенные многоугольники с реберным размером 3 и реберный граф графа Петерсена).

Теорема 10 (Theorem 4.2, [42]). Пусть (X, {Rj}f=0) — симметричная схема отношений и F С {1,2, Граф Г с лштрицей смежности Y^feF-^f

является графом Деза тогда и только тогда, когда сумма

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

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

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

f.UZF

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

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

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

Яо Д2 Яз Щ

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

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

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

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

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

(8,4,2,0) 8

(8,4,2,1) 5

(8,5,4,2) 5, 6

(9,4,2,1) 5

(9,4,2,1) 9

(10,5,4,2) 5, 6

(12,5,2,1) 5, 8

(12,6,3,2) 5, 5

(12,6,3,2)

(12,7,4,3) 5

(12,7,6,2) 5, 6

(12,9,8,6) 6, 8

(13,8,5,4) 5,4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблема 4. Какова вершинная связность графов Деза?

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

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

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

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

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

(3) г <2.

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

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

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

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

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

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

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

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

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

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

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

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

Работа [58] опубликована в тезисах международной конференции. Работа [59] опубликована в материалах международной конференции.

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

Содержание диссертации

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

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

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

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

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

графов с помощью конструкции, описанной в Теореме 9). Основным результатом главы является следующая теорема.

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

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

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

(3) г < 2.

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

Параметры Количество

неизоморфных

точных графов

Деза

(14,9,6,4) 1

(15,6,3,1) 1

(16,5,2,1) 1

(16,7,4,2) 2

(16,8,4,2) 1

(16,9,6,4) 2

(16,9,8,2) 1

(16,11,8,6) 1

(16,12,10,8) 1

(16,13,12,10) 1

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

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

Теорема 4г получена автором лично. Теорема 12 получена автором в нераздельном соавторстве с A.JI. Гаврилюком и В.В. Кабановым. Результаты четвертой и пятой главы получены в нераздельном соавторстве с Л.В.Шалагиновым.

Я выражаю глубокую признательность своему научному руководителю доктору физико-математических наук Александру Львовичу Гаврилюку за постановку задач, всестороннюю помощь и поддержку во время работы над диссертацией. Также я хотел бы поблагодарить сотрудников отдела алгебры и топологии Института математики и механики им. Н.Н. Красовского УрО РАН за полезные обсуждения результатов диссертации. В особенности хочу поблагодарить доктора физико-математических наук, профессора Владислава Владимировича Кабанова и кандидата физико-математических наук Наталью Владимировну Маслову за поддержку в процессе работы над диссертацией.

Литература

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

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

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

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

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

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

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

8. Bannai E. Ito T. 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,71! = 12, no = 15 and = 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 // 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, MCTYactl32, 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-коклик с большим /х/ Ермакова Г. М., Кабанов В. В// Проблемы теоретической и прикладной математики: труды 38-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2007, С. 31-34.

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

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

32. Гаврилюк А.Д., Шалагинов JI.B. О графах Деза с 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 Caylcy Graphs on Dihedral Groups, // Journal of Combinatorial theory. 2007. 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. С. 294 -298.

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-elcmcnts of the group L2(pn) // TV. Inst. Mat. Mekh. UrO RAN, 18, N3 (2012), 164 178.

49. Belonogov V.A. Representations and characters 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. Гаврилюк А. Л., Горяинов С. В. , Кабанов В. В. О вершинной связности графов Деза// Тр. ИММ УрО РАН, 19, № 3, 2013, 94-103

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

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

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

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

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

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

59. Goryainov S. V. 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

Подписано в печать 20.01.15.

Формат 60x84 716. Усл. печ. л. 1,4. Уч.-изд. л. 1,0. Тираж 150 экз. Заказ 2.

ФГБОУ ВПО «Челябинский государственный университет» 454001 Челябинск, ул. Братьев Кашириных, 129

Издательство Челябинского государственного университета 454021 Челябинск, ул. Молодогвардейцев, 57 б