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

Циовкина, Людмила Юрьевна

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

Циовкина, Людмила Юрьевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Екатеринбург МЕСТО ЗАЩИТЫ

2012 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

Диссертация по математике на тему «Симметричные дистанционно регулярные графы и их автоморфизмы»

Автореферат диссертации на тему "Симметричные дистанционно регулярные графы и их автоморфизмы"

005055551

м—

На правах рукописи УДК 519.17+512.54

ЦИОВКИНА Людмила Юрьевна

СИММЕТРИЧНЫЕ ДИСТАНЦИОННО РЕГУЛЯРНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ

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

2 2 НОЯ 2012

Автореферат

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

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

005055551

Работа выполнена в отделе алгебры и топологии Федерального государственного бюджетного учреждения науки Института математики и механики Уральского отделения Российской академии наук.

Научный руководитель: доктор физико-математических наук,

профессор, чл.-корр. РАН МАХНЕВ A.A.

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

профессор АЛЕЕВ Р.Ж.

кандидат физико-математических наук ЕФИМОВ К.С.

Ведущая организация: ФГАОУ ВПО «УрФУ имени первого

Президента России Б.Н.Ельцина»

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

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, Д. 16).

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

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

БЕЛОУСОВ И.Н.

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

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

денные классом 3-транспозиций (сопряженным классом инволюций группы, в котором произведение любых двух элементов имеет порядок < 3), и доказал, что все они являются группами ранга 3 на ассоциированных грат фах, вершинами которых являются элементы класса 3-транспозиций и две вершины смежны, если соответствующие инволюции коммутируют. Среди таких групп оказались все симметрические группы, некоторые классические (симплектические, ортогональные, унитарные) группы, и три спорадические группы, обнаруженные Фишером в процессе исследования, две из которых (^¿22, Рггл) являются простыми, а содержит простую группу индекса 2.

Известно, что если С — транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф Г ранга 3 с У (Г) = X, группа автоморфизмов которого допускает С? в качестве подгруппы; к тому же, каждый граф ранга 3 является сильно регулярным графом. Таким образом, внутренняя геометрия целого ряда групп, как показал Фишер, выразима с помощью сильно регулярных графов. Свое развитие теория групп подстановок ранга 3 получила в работах Д.Г. Хигмена ([17Ц19]).

Важным комбинаторным обобщением понятия сильно регулярного графа является понятие дистанционно регулярного графа. Для вершины а графа Г через Г$(а) обозначим подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии i от а. Граф Г диаметра <1 называется дистанционно регулярным с массивом пересечений {¿>о,£>ь- • • ,Ь<г_1;с1,... если значения = |1\+1(и) П Г(го)| и

С{(и, го) = ЛГ(-ш)| не зависят от выбора вершин и, ги, находящихся

на расстоянии г в Г для любого г € {0,..., ¿}. Положим сц — 60 — Ы — е^ р, — С2, А = <ц. Заметим, что для дистанционно регулярного графа Ьо — это степень графа, с\ = 1. Дистанционно регулярный граф диаметра 2 это

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

В диссертационной работе исследуются реберно симметричные дистанционно регулярные графы. Граф назовем реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер). Каждый реберно симметричный граф может быть построен на основе сравнительно небольшой информации о своей группе автоморфизмов следующим образом. Пусть даны неинвариантпая подгруппа Я группы Є и элемент д Є Є. Через Г = Г(б7, Н, НдН) обозначим граф с множеством вершин У(Є, Н) — {Нх | х Є С} и ребрами {Нх, Ну} такими, что ху~1 є НдН. Тогда (см. [24] или [15]) (1) если Є действует точно на У(С, Я), д2 є Я и С = (Я, д), то Г - связный граф, (? < Аиі(Г) и (3 действует точно и транзитивно на вершинах и на дугах графа Г; (2) если О действует транзитивно на дугах связного графа Е, Я — стабилизатор вершины е Є Е, д является 2-элементом и вершины с, еа смежны в Е, то Е ~ Т(0,Н,НдН), д2 Є II и С ~ (Н,д). Более симметричными объектами (обладающими большими группами автоморфизмов) являются дистанционно транзитивные графы. Если Г — граф диаметра <1, то через Г,-, где і Є {1,..., сі], обозначается граф с тем же множеством вершин, что и Г, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии г в Г. Граф Г диаметра (1 называется дистанционно транзитивным, если для любого г Є {1,..., с?} группа Аи^Г) действует транзитивно на множестве дуг графа Гг (в частности, каждый граф Г і является реберно симметричным). Легко попять, что каждый дистанционно транзитивный граф является дистанционно регулярным графом. При этом, дистанционно транзитивные графы диаметра 2 суть в точности связ-

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

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

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

Пусть 7- — некоторый класс графов. Граф Г назовем локально Т графом, если Г(а) лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Л, то граф Г назовем локально А-графом.

Пусть Г - реберно симметричный граф без изолированных вершин и С = Аи1,(Г) - его группа автоморфизмов. Ясно, что группа б действует транзитивно на вершинах графа Г, поэтому Г — локально А-граф. Более того, для каждой вершины а графа Г ее стабилизатор (7а действует транзитивно на окрестности Г(а), поэтому Г(а) является локально Дг(а)-графом. Таким образом, свойство реберной симметричности можно рассматривать

как локальное свойство графа.

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

Граф назовем локально циклическим, если окрестность каждой его вершины является объединением изолированных циклов. Например, граф Шрикханде это единственный сильно регулярный локально Сб-граф на 16 вершинах с А = ц = 2. Граф Шрикханде является реберно симметричным, к тому же, это граф наименьшего порядка, который является дистанционно регулярным, но не дистанционно транзитивным [8].

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

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

Предложение 1 ([1], теорема 2). Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если А = 2 u /j > 1, то верно одно из утверждений:

(1) Г — примитивный граф с массивом пересечений

{15,12,6; 1,2,10}, {19,16,8; 1,2,8}, {24,21,3; 1,3,18}, {35,32,8; 1,2,28} или {51,48,8; 1,4,36};

(2) Г — антиподальный граф с ¡1 = 2 и массивом пересечений

{2г + 1,2г - 2,1; 1, 2,2г +1}, г € {3,4,..., 21} - {10,16} и V = 2г(г + 1);

(3) Г — антиподальный граф с ¡1>Ъ и массивом пересечений

{15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8,27}, {35,32,1; 1,4,35}, {45,42,1; 1,6,45}, {42,39,1; 1,3,42} или {75,72,1; 1,12,75}.

Известно существование реберно симметричных дистанционно регулярных графов из пункта (2) предложения 1, получаемых с помощью конструкции Мэтона, если 2г + 1 — степень простого числа [8]. В частности, в случае г = 3 получается граф Клейна, единственный дистанционно регулярный локально С7-граф диаметра 3 на 24 вершинах, являющийся 3-накрытием 8-клики. Граф Клейна является реберно симметричным, но не дистанционно транзитивным [8].

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

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

В [15] К. Годсил, Р. Либлер и Ч. Прэгер получили описание анти-подальных дистанционно транзитивных графов диаметра 3. Более общей является задача описания реберно симметричных антиподальных дистанционно регулярных графов диаметра 3. Антиподальный дистанционно регулярный граф диаметра 3 имеет (см. [8]) массив пересечений {&, //(г — 1), 1; 1, ¡-I, к}, является г-накрытием (к + 1)-клики и для параметров г, \,ц, к справедливо тождество к — \ — г[х = X — ц. Положим 5 = А — ц.

В работе [16] доказано, что для фиксированных г, <5 имеется лишь конечное число допустимых массивов, кроме случаев 6 £ {—2,0,2}. В диссертации исследуются реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае А = ¡1.

Цель диссертации. Целью данной работы является решение следующих задач:

1)Изучить возможные автоморфизмы гипотетических дистанционно регулярных графов с массивами пересечений {42,39,1; 1,3,42}, {35,32,1; 1,2,28}, {35,32,1; 1,2,35} и исследовать реберно симметричные дистанционно регулярные графы с этими массивами пересечений.

2) Исследовать реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае А =

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

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

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

УрО РАН (Екатеринбург, 2012 г.), на Международной конференции "Алгебра и линейная оптимизация", посвященной 100-летию со дня рождения проф. С.Н. Черникова (Екатеринбург, 2012 г.), на Международной школе-конференции по теории групп, посвященной 90-летию со дня рождения проф. З.И.Боревича (Владикавказ, 2012 г.). Результаты работы неоднократно докладывались и обсуждались на алгебраическом семинаре Института математики и механики УрО РАН.

Публикации. Результаты диссертации были опубликованы в 4 статьях (три статьи опубликованы в журналах из списка ВАК) и 4 тезисах докладов. Из них 1 статья и 1 тезисы написаны без соавторов, 1 статья и 1 тезисы - тремя авторами (Махнев A.A., Падучих Д.В., Циовкина Л.Ю.), остальные — в соавторстве с Махневым A.A. Все совместные работы написаны в нераздельном соавторстве.

Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 33 наименования. Общий объем диссертации составляет 80 страниц.

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

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

Вторая глава посвящена изучению автоморфизмов дистанционно регулярных локально циклических графов для следующих массивов пересечений из пунктов (1)-(3) предложения 1: {42,39,1; 1,3,42}, {35,32,1; 1,2,28}, {35,32,1; 1,2,35}. В ней определяются возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно ре-

гулярпых графов с этими массивами пересечений. Исследуются реберно симметричные дистанционно регулярные графы с вышеперечисленными массивами пересечений.

Пусть для произвольного автоморфизма д графа Г число точек я: из Г таких, что й{х,х9) =■ і обозначается через щ(д). Основными результатами второй главы являются следующие теоремы и следствия.

Теорема 1. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {42,39,1; 1,3,42}, Є = АиЦГ), д — элемент из <7 простого порядка р ий = Ріх(^). Тогда 7г(С?) С {2,3,7,13,43} и выполняется одно из следующих утверждений:

(1) — пустой граф и либо

(г) р = 43, а1(д) = 43, а2(д) = 559;

(гг) р = 7, а3(д) = 985 + 14, аі(д) = 91/ + 42й + 49 и 13/ + 20з < 77; (ггг) р = 2, а3(д) = 28й +14, аг{д) = 261 + 12д + 62 и 13/ + 20я < 263;

(2) р = 13, П является 4-кликой, <*з(д) = 52, аі(д) = 169/ + 65 и І Є {0,1,2};

(3) р = 7, П лежит в антиподальном классе Г и либо (г) |П| = 7, ац(д) = 911 - 7Ґ и а3(д) = 7+ 14£', либо (гг) = 14, а1(д) = 91/ - 7Ґ + 49 и а3(д) = 14£';

(4) р = 3, Г содержит і антиподалъных классов, пересекающих (2 по 5 вершинам, а3(д) = 14 — в и либо

(г) і = 1, в € {2,5,8,11,14} и а^д) = 391 + - 3, либо (гг) і = 4, Г2 является объединением в изолированных 4-клик, з Є {2,5,8} и аі(д) = 39/ - 15в + 15;

(5) р = 2, Г содержит і антиподалъных классов, пересекающих по 5 вершинам, а3(д) = ¿(14 — в) + 14£' и либо

(і) і = 1, |П| = я, а Є {2,4,6,8,10,12,14} иаі(р) = 26/ + 65 + 6і'+Ю,

либо

(й) / — З, П — шестиугольник и аі(д) = 261 4- 6/' + 6, либо (Ні) / = 5, П является графом К^ с удаленным максимальным паросочетанием и аі(д) = 261 + 6/' — 2.

Следствие. Дистанционно регулярный граф с массивом пересечений {42,39,1; 1,3,42} не является реберно симметричным.

Теорема 2. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {35,32,8; 1,2,28}, С = Аи1;(Г), д — элемент из Є простого порядка р и П = Кіх(д). Тогда тг(С) С {2,3, 5,7} и выполняется одно из следующих утверждений:

(1) П — пустой граф и либо

(i)р = 7, а3(д) = 1685, аі(д) = 98/+425-42 иа2(д) = 798—98/—210^; (И) р = 3, а3(д) = 72й, а^) = 42/ + Ш и а2(д) = 756 - 421 - 90я; (гіі) р = 2, а3(д) = 48я, а і (з) = 28/ + 12в и а2{д) = 756 - 28/ - 60з,-

(2) £7 состоит из вершин, попарно находящихся на расстоянии 3 а Г и либо

(г) р = Ъ, |П| = 1, а3(д) = 120в + 40 и аг(д) = 70/ + ЗОв + 5, либо (и) р = 7, |П| = 7г, а3(д) = 168з + 112/г и а^д) = 98/ + 42в - 49г, з < 2/г, г Є {1, 2} или |П| = 21, а3{д) = 0 и сц(д) = 98/ +49, / < 6;

(3) р = 2, |П| = 21, а3(д) = 48/ - 16/, ах(д) = 28в + 12/ - 14/ и либо (г) для любой вершины а из П подграф Гз(а) не пересекает П и <

36, либо

(ii) П содержит вершину степени 1 и |Г2| < 50, либо

(гіг) степень любой вершины в £1 не меньше 3 и не больше 19, а |П| < 82.

Следствие. Дистанционно регулярный граф с массивом пересечений {35,32,8; 1,2,28} не является реберно симметричным.

Теорема 3. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {35,32,1; 1,2,35}, <7 = Аи1;(Г), д — элемент из С простого порядка р и П = РЬс(д). Тогда тг(С) С {2,3, 5,7,17} и выполняется одно из следующих утверждений:

(1) Г2 — пустой граф и либо

(г) р = 17, 0:1(5) = аз(д) =34 и аг(<7) — 544 или аз(д) = 612, либо (й) р 6 {2,3}, а3(з) = 0, о2(5) = 576 и ац(д) = 36;

(2) лежит в аптиподальном классе Г и либо (г) р= 7, |0| = 3,17, либо

(И) Р = 5,\П\ = 7,17;

(3) р =■ 3,5 и П — граф икосаэдра;

(4) р — 2, П — объединение двух антиподальных классов, аз (д) = 0 и ац(д) = 34.

Следствие. Дистанционно регулярный граф с массивом пересечений {35,32,1; 1,2,35} не является реберно симметричным.

Таким образом, во второй главе диссертации найдены возможные порядки и подграфы неподвижных точек автоморфизмов простых порядков дистанционно регулярных локально циклических графов для каждого из следующих массивов пересечений: {42,39,1; 1,3,42}, {35,32,1; 1,2,28}, {35,32,1; 1,2,35}. Для каждого из перечисленных массивов пересечений установлено, что дистанционно регулярные графы с соответствующим массивом пересечений не являются реберно симметричными. Полученные теоремы будут полезны при дальнейшем изучении дистанционно регулярных локально циклических графов с указанными массивами пересечений.

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

Перечислим далее известные бесконечные классы антиподальных ди-

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

A. Конструкция Мэтона, к = г[1+1 — степень простого числа р (/I четно или р = 2).

Б. Конструкция Камерона, к = д3, ц — (д2 — 1)(д + 1 )/г, д — степень простого числа р, г делит (д + 1)/(2,р + 1).

B. Конструкция Бонда, к — г+1, ц = 1, г нечетно, существует дезаргова проективная плоскость порядка к.

Г. Конструкция Броувера, к = = ¿'+1, /х = ¿ —1, существует псевдогеометрический граф для имеющий спред (разбиение множества вершин (в + 1)-кликами).

Д. Конструкция Годсила-Хензеля, к — ръ — 1, г = = рг+1, р —

простое число, 0 < / < г.

Е. Конструкция де Каена-фон дер Флаасса, к = <?!+1 — 1 ,г = д1,/л = д, д = 2К

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

1. Серия Судзуки. Граф 5иг{д) имеет массив пересечений {д2, д2 — д — 2,1; 1,д + 1,52}, д = 22е+1 >8,г = 9-1,С = Аи1(5иг(д)) - Ап^Бг^)) и Ста — расширение силовской 2-подгруппы Р порядка д2 с помощью циклической группы порядка 2е + 1.

В предположении существования графа Биг(д) для любого делителя в числа д— 1, 1 < з < д—1 существует граф в) с массивом пересечений

{д\ (5-1)(^-1)/5,1; 1, (д2-1 )/з,д2}, д = 22е+1 > 8, С = АиЬ(5ш(д, *)) = АхЛ(Бг(д)) и Са — расширение силовской 2-подгруппы Р порядка д2 с

помощью абелевой группы порядка (д — 1)(2е + 1)/,ч.

2. Серия Ри. Граф 71ее(д) имеет массив пересечений {д3, д3 — 2д2 — 2д — 3,1; 1,2(д2 + д + 1),д3}, д = 32е+1 > 3, г = (д - 1)/2, О = АпЬ(Пее(д)) = Аиі(2Сг(д)) и Са — расширение силовской 3-подгруппы Р (цоколя группы) порядка д3 с помощью циклической группы порядка 4е + 2.

В предположении существования графа Иее{д) для любого делителя я числа (д — 1)/2, 1 < з < — 1)/2 существует граф Т1ее(д,а) с массивом пересечений {д2, (в - 1)(д3 - 1 1; 1, (д3 - 1)/«, д2>, д = 32е+1 > 3, С? = Аиі(7£ее(д, в)) = Аиі(2С2(д)) и Са — расширение силовской 3-подгруппы (цоколя группы) Р порядка д3 с помощью группы порядка (д— 1)(2е+1)/а.

3. Унитарная серия. Граф Ыз(д) имеет массив пересечений {д3, д3 — д2 — д-2,1; 1,д2 + д +1, д3}, д = ре > 3, г = д-1, в = АиЬ{Ы3(д)) = Аи1;(17з(д)) и Са — расширение силовской р-подгруппы Р (цоколя группы) порядка д3 с помощью абелевой группы порядка (д2 — \)е/т.

В предположении существования графа Ыз{д) для любого делителя в числа д— 1, 1 < я < д — 1 существует граф ІЛ${д, з) с массивом пересечений {д3, (з - 1)(73 - 1)/а, 1; 1, (д3 - 1)/з, д3}, д = ре > 3, О = АиЬ(Щд, а)) = Лиі(?7з(д)) и Са — расширение силовской р-подгруппы Р (цоколя группы) порядка д3 с помощью абелевой группы порядка (д2 — 1)е/в.

Следующая теорема уточняет некоторые утверждения основной теоремы Годсила, Либлера и Прэгер из [15].

Теорема 4. Пусть Г — реберно симметричный дистанционно регулярный граф с массивом пересечений (г — 1; 1, /і, к} и Є = АиЦГ). Тогда выполняются следующие утверждения:

(1) если Г — двудольный граф, то Г получается удалением из Кк+і к+1 максимального паросочетания, Є <2 х

(2) если г = к, то либо к = 2 и Г — шестиугольник, либо к = 6, Г —

вторая окрестность вершины в графе Хофмана-Синглтопа иб< ¿7; (3) если г — 2, то либо

(г) к+1 — 22т~1 ±2т~1, в < 2 х Зр2т{2), т > 3, либо (и) & = д3, £ < 2 х РГ£/3(д), з > 3 или С < 2 х АиЬ(2С2(д)), д = 32е+1; е > 1, либо

(ш) k — q>G< 2 х Р£1,2(д), д = 1 (то<1 4), либо

(ги) к = 175, б = 2 х Яг5" или к = 275, С = 2 х Со3, либо

(«) & = 22< - 1, С = 2 ■ 2).

В случае (и) граф Г имеет параметры и = 2(д3 + 1), /с = д3, А = (д-1)(д2 + 1)/2, /х = (д + 1)(д2-1)/2. В этом случае для группы Ри 2С2(д) в основной теореме из [15] допущена опечатка: вместо п = 32е+1 +1 должно быть п = З6е+3 + 1.

Основным результатом третьей главы диссертации является следующая

Теорема 5. Пусть Г — реберно симметричный дистанционно регулярный граф с массивом пересечений {гц + 1, (г — 1)^, 1;1,р,г/х + 1} и <7 = Аи1;(Г). Если г > 2, то выполняется одно из следующих утверждений:

(1) к = д — степень простого числа, г делит д — 1, Г имеет массив пересечений {д, (г — 1)(д— 1)/г, 1; 1, (д— 1)/г, д} и £2(д)<С или £1<2(д)<С;

(2) Г 6 {Зиг(д,8),Пее(9,з),Ы3(я,з)}-

Таким образом, теоремы 4 и 5 дают описание класса реберно симметричных антиподальных дистанционно регулярных графов диаметра 3, для которых параметры А и /г равны. При этом, выделены новые допустимые бесконечные серии антиподальных дистанционно регулярных графов диаметра 3 с А — (1. Для графов из этих серий, удовлетворяющих свойству реберной симметричности, определены их группы автоморфизмов и указаны строения стабилизаторов вершин.

Благодарности.

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

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

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

[1] Буриченко В. П., Махнев А. А. О вполне регулярных локально циклических графах // Соврем, проблемы математики: тез. Междунар. 42-й Всерос. мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2011.-С. 181-183.

[2] Буриченко В.П., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12,1; 1,2,15} // Доклады академии наук.-2012.-Т. 445, № 4. С. 375-379.

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

[4] Мазуров В.Д. Минимальные подстановочные представления конечных простых классических групп. Специальные линейные, симплектиче-ские и унитарные группы // Алгебра и логика.-1993.-Т. 32, № 3. С. 267287.

[5] Махнев A.A., Падучих Д.В. О группе автоморфизмов графа Ашбахера // Доклады академии наук.-2009.-Т. 426, № 3. С. 310-313.

[6] Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24,21,3; 1,3,18} // Доклады академии наук.-2011.-Т. 441, № 1. С. 14-18.

[7] Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {81,60,1; 1,20,81} // Доклады академии наук.-2010.-Т. 435, № 3. С. 305-309.

[8] Brouwer А.Е., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin etc: Springer-Verlag. 1989.

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

[10] Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.

[11] Cameron P.J., van Lint J.H. Graphs, Codes and Designs. London Math. Soc. Student Texts №22. Cambridge: Cambridge Univ. Press. 1991.

[12] Conway J., Curtis R., Norton S., Parker R., Wilson R. Atlas of finite groups. Oxford: Clarendon Press, 1985.

[13] Dixon J.D., Mortimer, B. Permutation Groups. Graduate Texts in Mathematics.- Vol.163. Berlin etc: Springer-Verlag. 1996.

[14] Frucht, R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe// Compositio Math. 1938. Vol. 6. P.239-250.

[15] Godsil C.D., Liebler R.A., Praeger C.E. Antipodal distance transitive covers of complete graphs // Europ. J. Comb. 1998. Vol. 19, № 4. P. 455478.

[16] Godsil C.D., Hensel A.D. Distance regular covers of the complete graphs // J. Comb. Theory Ser. B. 1992. Vol. 56, P. 205-238.

[17] Higman D.G. Finite permutation groups of rank 3// Math. Z. 1964. Vol.86. P. 145-156.

[18] Higman D.G. Primitive rank 3 groups with a prime subdegree// Math. Z. 1966. Vol.91. P.70-86.

[19] Higman D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II// Arch. Math. Basel. 1970. Vol.21.- P.151-156; 353-361.

[20] Mendelsohn, E. Every (finite) group is the group of automorphisms of a (finite) strongly regular graph// Ars. Combinatoria. 1978. Vol. 6. P,75-86.

[21] Neukirch J. Algebraic Number Theory// Grundlehren der mathematischen Wissenschaften. Vol.322. Berlin etc: Springer-Verlag. 1999.

[22] Praeger C.E., Soicher L.H. Low rank representations and graphs for sporadic groups// Lecture series 8. Cambridge: Cambridge Univ. Press. 1997.

[23] Sabidussi G. Graphs with given automorphism group and given graph theoretical properties// Canad. J. Math. 1957. Vol.9. P. 515-525,

[24] Sabidussi G. Vertex-transitive graphs// Monatsh. Math. 1964. Vol.68. P. 426-438.

[25] Weiss R.M. The nonexistence of 8-transitive graphs// Combinatorica. 1981. Vol.1. P. 309-311.

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

[26] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42,39,1; 1,3,42}/ А. А. Махнев, Л. Ю. Циовкина// Алгебра и геометрия: тр. Междунар. конф., посвящ. 80-летию со дня рождения А.И. Старостина,- Изд-во УМЦ-УПИ. Екатеринбург,

2011,- С.112-115.

[27] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42,39,1; 1,3,42}/ А. А. Махнев, Л. Ю. Циовкина// Доклады Академии Наук,- 2011.- Т. 441, N'-3. С. 305-309.

[28] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2,28}/ А. А. Махнев, Л. Ю. Циовкина// Соврем, проблемы математики: тез. Междунар. 43-й Всерос. мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2012,- С.69-71.

[29] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2,28}/ А. А. Махнев, Л. Ю. Циовкина/ / Труды Института математики и механики УрО РАН.- 2012.Т. 18, №1. С. 235-241.

[30] Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,1; 1,2,35} / Л.Ю. Циовкина // Алгебра и линейная оптимизация: тез. Междунар. конф., посвящ. 100-летию со дня рождения С.Н. Черникова.- Изд-во УМЦ-УПИ. Екатеринбург,

2012,- С.172-174.

[31] Циовкина Л.Ю. Об автоморфизмах графа с массивом пересечений {35,32,1; 1,2,35} // Сиб. электрон, матем. изв.- 2012.- Т. 9. С. 285-293.

[32] Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с А = ц / A.A. Махнев, Д.В. Падучих, Л.Ю. Циовкина //Теория групп и ее прил.: тез. 9-й Междунар. шк.-конф., посвящ. 90-летию со дня рождения проф. З.И. Боревича.- Изд-во СОГУ. Владикавказ, 2012.- С.86-88.

[33] Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с А = ц / A.A. Махнев, Д.В. Падучих, Л.Ю. Циовкина // Доклады Академии Наук.- 2012,- Т. , № . С. - .

Подписано в печать 15.10.2012. Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,2 Тираж 100 экз. Заказ

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Циовкина, Людмила Юрьевна

Введение

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

1.1 Метод Хигмена и вспомогательные результаты.

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

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

2.1 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42,39,1; 1,3,42}.

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

2.1.2 Автоморфизмы графа с массивом пересечений

42,39,1; 1,3,42}.

2.1.3 Граф с массивом пересечений {42,39,1; 1,3,42} не является реберно симметричным.

2.2 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2, 28}.

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

2.2.2 Автоморфизмы графа с массивом пересечений

35,32,8; 1,2,28}.

2.2.3 Граф с массивом пересечений {35,32,8; 1,2,28} не является реберно симметричным.

2.3 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,1; 1,2,35}.

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

2.3.2 Автоморфизмы графа с массивом пересечений

35,32,1; 1,2,35}.

2.3.3 Граф с массивом пересечений {35,32,1; 1,2,35} не является реберно симметричным.

3 Реберно симметричные дистанционно регулярные накрытия клик с Л = д

3.1 Автоморфизмы графа с массивом пересечений г}1 + 1, (г - 1)11,1; 1,}1,г/1+ 1}.

3.2 Случай точного действия Аи^Г) : Е.

3.3 Случай неточного действия Аи1(Г) : Е.

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

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

Класс /С графов (под графом здесь и далее будем понимать неориентированный граф без петель и кратных ребер) назовем универсальным, если каждая конечная группа представима группой автоморфизмов некоторого конечного графа из /С. Известный результат Р. Фрухта [14] послужил выделению ряда универсальных подклассов графов, в числе которых оказались следующие: регулярные графы степени к для произвольного фиксированного к > 2, двудольные графы, гамильтоновы графы, ¿-хроматические графы для £ > 1, сильно регулярные графы (регулярные графы, у которых число вершин в пересечении окрестностей любой пары различных вершин зависит только от того, смежны эти вершины или нет)([23],[20]). В [9] Ф. Бюкенхаутом была предложена идея построения единой геометрической теории, согласно которой каждая конечная простая группа была бы представима группой автоморфизмов некоторой геометрической структуры из определенного, поддающегося описанию, класса конечных геометрий. Отметим, что спорадические простые группы Фишера, Судзуки, Маклафлина, Холла-Янко, Рудвалиса и Хигмена-Симса были впервые построены как группы автоморфизмов сильно регулярных графов. Например, Б. Фишер исследовал почти простые группы, порожденные классом 3-транспозиций (сопряженным классом инволюций группы, в котором произведение любых двух элементов имеет порядок < 3), и доказал, что все они являются группами ранга 3 на ассоциированных графах, вершинами которых являются элементы класса 3-транспозиций и две вершины смежны, если соответствующие инволюции коммутируют. Среди таких групп оказались все симметрические группы, некоторые классические (симплектические, ортогональные, унитарные) группы, и три спорадические группы, обнаруженные Фишером в процессе исследования, две из которых (.Рггг, -^23) являются простыми, а -/Р?24 содержит простую группу индекса 2.

Известно, что если С — транзитивная группа подстановок ранга 3 на множестве X и имеет четный порядок, то можно построить граф Г ранга 3 с У"(Г) = X, группа автоморфизмов которого допускает С в качестве подгруппы; к тому же, каждый граф ранга 3 является сильно регулярным графом. Таким образом, внутренняя геометрия целого ряда групп, как показал Фишер, выразима с помощью сильно регулярных графов. Свое развитие теория групп подстановок ранга 3 получила в работах Д. Г. Хигмена ([17]-[19]).

Важным комбинаторным обобщением понятия сильно регулярного графа является понятие дистанционно регулярного графа. Для вершины а графа Г через Г ¿(а) обозначим подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии г от а. Граф Г диаметра (I называется дистанционно регулярным с массивом пересечений {&о, &ъ • ■ •, Ьсг-ъ сг,., са}, если значения Ъ{(и, ио) = |Гг+1(г/) Г) Г(ги)| и Сг(и, гю) — |Гг1 (гг) П Г(гу)| не зависят от выбора вершин и, т, находящихся на расстоянии г в Г для любого г £ {0,., <!}. Положим аг= Ьо—6«—с^, р, = С2, Л = <21. Заметим, что для дистанционно регулярного графа &о — это степень графа, с\ = 1. Дистанционно регулярный граф диаметра 2 это в точности то же, что и связный сильно регулярный граф (случай несвязного сильно регулярного графа не представляет особого интереса, так как несвязный сильно регулярный граф является объединением изолированных равномощных клик). Введем еще некоторые необходимые определения. Если Г — граф диаметра с1, то через Гг-, где г € {1,., с?}, обозначается граф с тем же множеством вершин, что и Г, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии г в Г. Граф Г диаметра (I называется примитивным, если граф Г; связен для любого % е {1,., в противном случае граф Г называется импримитивным. Граф Г диаметра с1 > 1 называется антиподальным, если соответствующий граф Г^ является объединением изолированных клик. Согласно основной теореме Д. Смита, каждый импримитивный дистанционно регулярный граф является двудольным или антиподальным[8].

В диссертационной работе исследуются реберно симметричные дистанционно регулярные графы. Граф назовем реберно симметричным, если его группа автоморфизмов действует транзитивно на множестве его дуг (упорядоченных ребер). Более симметричными объектами (обладающими большими группами автоморфизмов) являются дистанционно транзитивные графы. Граф Г диаметра d называется дистанционно транзитивным, если для любого i 6 {1,., d} группа Aut(r) действует транзитивно на множестве дуг графа (в частности, каждый граф r¿ является реберно симметричным). Легко понять, что каждый дистанционно транзитивный граф является дистанционно регулярным графом. При этом, дистанционно транзитивные графы диаметра 2 суть в точности связные графы ранга 3. Группами автоморфизмов дистанционно транзитивных графов предста-вимы многие конечные простые группы. Необходимо отметить также, что дистанционно регулярные графы и реберно симметричные графы используются в различных приложениях, в том числе, в алгебраической теории кодирования и при моделировании сетей. В связи с этим представляют интерес задача полного описания класса дистанционно транзитивных графов, и связанная с ней задача описания более широкого класса - класса реберно i симметричных дистанционно регулярных графов.

Изучение реберно симметричных графов началось с двух важных работ У. Татта 1947 и 1959 годов о конечных кубических графах. Татт рассмотрел класс графов, группы автоморфизмов которых действуют транзитивно на s-дугах графа, то есть графов с вершинно транзитивной группой автоморфизмов и стабилизатором вершины, действующем транзитивно на множестве исходящих из нее s-дуг (s-дугой называется путь (vq, vs)1 в котором Vi-1 ф Vi+i для любого i € {1,., s — 1}). Как оказалось, для регулярных графов степени 3 с транзитивной на s-дугах группой автоморфизмов, число s не превосходит 5 и граница достигается на графе Татта-Кокстера. Впоследствии Р. Вейсс обобщил результат Татта, доказав, что для регулярных графов произвольной степени к > 3 с транзитивной на й-дугах группой автоморфизмов, число 5 не превосходит 7 и граница достигается на 12-клетке Татта[25].

Г. Сабидусси в работе [24] предложил следующий метод построения всех реберно симметричных графов на основе сравнительно небольшой информации об их группах автоморфизмов, который, в частности, оказался полезным в классификации дистанционно транзитивных графов. Пусть даны неинвариантная подгруппа Н группы б? и элемент д € <7. Через Г = Г (С, Я, НдН) обозначим граф с множеством вершин Я) = {Нх | х е <3} и ребрами {Нх, Ну} такими, что ху~1 € ЯдЯ. Тогда (см. [24] или [15]) (1) если (7 действует точно на Я), Е Н и С = (Я, то Г — связный граф, <7 < Аи1;(Г) и С действует точно и транзитивно на вершинах и на дугах графа Г; (2) если С действует транзитивно на дугах связного графа Е, Н — стабилизатор вершины е б Е, д является 2-элементом и вершины е, е9 смежны в Е, то Е ~ Г(£, Н, НдН), д2 е Я и (7 = (Я, 5).

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

Пусть Г - реберно симметричный граф без изолированных вершин и <2 = АцЦГ) - его группа автоморфизмов. Ясно, что группа (7 действует транзитивно на вершинах графа Г, поэтому Г - локально А-граф. Более того, для каждой вершины а графа Г ее стабилизатор (?а действует транзитивно на окрестности Г (а), поэтому Г (а) является локально Аг(а)-графом. Таким образом, свойство реберной симметричности можно рассматривать как локальное свойство графа.

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

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

Шрикханде это единственный сильно регулярный локально Сб-граф на 16 вершинах с Л = ß = 2. Граф Шрикханде является реберно симметричным графом, к тому же, это граф наименьшего порядка, который является дистанционно регулярным, но не дистанционно транзитивным [8].

Предложение 1 ([1], теорема 2). Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если А = 2 и ß > 1, то верно одно из утверждений:

1) Г — примитивный граф с массивом пересечений {15,12,6; 1,2,10}, {19,16,8; 1,2,8}, {24,21,3; 1,3,18}, {35,32,8; 1,2,28} или {51,48, 8; 1,4, 36};

2) Г — антиподальный граф с ¡1 — 2 и массивом пересечений

2 г + 1,2 г- 2,1; 1,2,2 г + 1}, г € {3,4,., 21} - {10,16} и v = 2 г (г + 1);

3) Г — антиподальный граф с /л > 3 и массивом пересечений

15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8,27}, {35,32,1; 1,4,35}, {45,42,1; 1,6,45}, {42,39,1; 1,3,42} или {75,72,1; 1,12,75}.

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

В [15] К. Годсил, Р. Либлер и Ч. Прэгер получили описание антиподаль-ных дистанционно транзитивных графов диаметра 3. Более общей является задача описания реберно симметричных антиподальных дистанционно регулярных графов диаметра 3. Антиподальный дистанционно регулярный граф диаметра 3 имеет (см. [8]) массив пересечений /¿(г — 1), 1; 1, А;}, является г-накрытием (А;+1)-клики и для параметров г, Л, к справедливо тождество к — 1 — г/2 = Х — {I. Положим 5 = \ — ц. В [16] доказано, что для фиксированных г, 5 имеется лишь конечное число допустимых массивов, кроме случаев 5 € {—2,0,2}. В работе исследуются реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае Л =

Цель диссертации. Целью данной работы является решение следующих задач:

1) Изучить возможные автоморфизмы гипотетических дистанционно регулярных графов с массивами пересечений {42,39,1; 1,3,42}, {35,32,1; 1,2, 28}, {35,32,1; 1,2,35} и исследовать реберно симметричные дистанционно регулярные графы с этими массивами пересечений.

2) Исследовать реберно симметричные антиподальные дистанционно регулярные графы диаметра 3 в случае А = /¿.

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

Апробация работы. Основные результаты работы докладывались на Международной конференции по алгебре и геометрии, посвященной 80-летию со дня рождения А.И. Старостина (Екатеринбург, 2011 г.), на Международной (43-й Всероссийской) молодежной школе-конференции ИММ УрО РАН (Екатеринбург, 2012 г.), на Международной конференции "Алгебра и линейная оптимизация", посвященной 100-летию со дня рождения проф. С.Н. Черникова (Екатеринбург, 2012 г.), на Международной школеконференции по теории групп, посвященной 90-летию со дня рождения проф. З.И.Боревича (Владикавказ, 2012 г.). Результаты работы докладывались и обсуждались на алгебраическом семинаре Института математики и механики УрО РАН.

Публикации. Результаты диссертации были опубликованы в 4 статьях (три статьи опубликованы в журналах из списка ВАК) и 4 тезисах докладов. Из них 1 статья и 1 тезисы написаны без соавторов, 1 статья и 1 тезисы - тремя авторами (Махнев A.A., Падучих Д.В., Циовкина Л.Ю.), остальные - в соавторстве с Махневым A.A. Все совместные работы написаны в нераздельном соавторстве.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Циовкина, Людмила Юрьевна, Екатеринбург

1. Буриченко В. П., Махнев A.A. О вполне регулярных локально циклических графах // Соврем, проблемы математики: тез. Междунар. 42-й Всерос. мол. шк.-конф.- Изд-во ИММ УрО РАН. Екатеринбург, 2011.-С.181-183.

2. Буриченко В.П., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12,1; 1,2,15} // Доклады академии наук.-2012.-Т. 445, № 4. С. 375-379.

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

4. Мазуров В.Д. Минимальные подстановочные представления конечных простых классических групп. Специальные линейные, симплектиче-ские и унитарные группы // Алгебра и логика.-1993.-Т. 32, № 3. С. 267287.

5. Махнев A.A., Падучих Д.В. О группе автоморфизмов графа Ашбахера // Доклады академии наук.-2009.-Т. 426, № 3. С. 310-313.

6. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24,21,3; 1,3,18} // Доклады академии наук.-2011.-Т. 441, № 1. С. 14-18.

7. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {81,60,1; 1,20,81} // Доклады академии наук.-2010.-Т. 435, № 3. С. 305-309.

8. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-Regular Graphs. Berlin etc: Springer-Verlag. 1989.

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

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

11. Cameron P.J., van Lint J.H. Graphs, Codes and Designs. London Math. Soc. Student Texts №22. Cambridge: Cambridge Univ. Press. 1991.

12. Conway J., Curtis R., Norton S., Parker R., Wilson R. Atlas of finite groups. Oxford: Clarendon Press, 1985.

13. Dixon J.D., Mortimer, B. Permutation Groups. Graduate Texts in Mathematics.- Vol.163. Berlin etc: Springer-Verlag. 1996.

14. Frucht, R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe// Compositio Math. 1938. Vol. 6. P.239-250.

15. Godsil C.D., Liebler R.A., Praeger C.E. Antipodal distance transitive covers of complete graphs // Europ. J. Comb. 1998. Vol. 19, № 4. P. 455478.

16. Godsil C.D., Hensel A.D. Distance regular covers of the complete graphs // J. Comb. Theory Ser. B. 1992. Vol. 56, P. 205-238.

17. Higman D.G. Finite permutation groups of rank 3// Math. Z. 1964. Vol.86. P. 145-156.

18. Higman D.G. Primitive rank 3 groups with a prime subdegree// Math. Z. 1966. Vol.91. P.70-86.

19. Higman D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II// Arch. Math. Basel. 1970. Vol.21.- P.151-156; 353361.

20. Mendelsohn, E. Every (finite) group is the group of automorphisms of a (finite) strongly regular graph// Ars. Combinatoria. 1978. Vol. 6. P.75-86.

21. Neukirch J. Algebraic Number Theory// Grundlehren der mathematischen Wissenschaften. Vol.322. Berlin etc: Springer-Verlag. 1999.

22. Praeger C.E., Soicher L.H. Low rank representations and graphs for sporadic groups// Lecture series 8. Cambridge: Cambridge Univ. Press. 1997.

23. Sabidussi G. Graphs with given automorphism group and given graph theoretical properties// Canad. J. Math. 1957. Vol.9. P. 515-525.

24. Sabidussi G. Vertex-transitive graphs// Monatsh. Math. 1964. Vol.68. P. 426-438.

25. Weiss R.M. The nonexistence of 8-transitive graphs// Combinatorica. 1981. Vol.1. P. 309-311.Работы автора по теме диссертации

26. Циовкина Л. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {42,39,1; 1,3,42}/ А. А. Махнев, JI. Ю. Циовкина// Доклады Академии Наук.- 2011.- Т. 441, №3. С. 305-309.

27. Циовкина J1. Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35,32,8; 1,2,28}/ А. А. Махнев, JI. Ю. Циовкина// Труды Института математики и механики УрО РАН,- 2012 Т. 18, №1. С. 235-241.

28. Циовкина JI. Ю. Об автоморфизмах графа с массивом пересечений {35,32,1; 1,2,35} // Сиб. электрон, матем. изв.- 2012,- Т. 9. С. 285-293.

29. Циовкина Л. Ю. Реберно симметричные дистанционно регулярные накрытия клик с А = /2 / A.A. Махнев, Д.В. Падучих, Л.Ю. Циовкина // Доклады Академии Наук,- 2012,- С. .