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

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

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

БЕЛОУСОВ Иван Николаевич

РЕБЕРНО РЕГУЛЯРНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ

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

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

Екатеринбург — 2007

003071 гь <

003071767

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

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

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

профессор, чл -корр РАН МАХНЕВ Александр Алексеевич Официальные оппоненты

доктор физико-математических наук, профессор РОЖКОВ Александр Викторович

кандидат физико-математических наук НОСОВ Виталий Валерьевич

Ведущая организация Уральский государственный университет

Защита состоится 26 июня 2007 года в 12 30 часов на заседании специализированного совета Д 004 006 03 в Институте математики и механики УрО РАН по адресу 620219, г Екатеринбург ул С Ковалевской, 16

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

Автореферат разослан { Ь мая 2007 года

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

доктор физ -мат наук

В В Кабанов

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

Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([7]-[11], [26], [27]) Например, класс билдингов Титса характеризует группы лиева типа [30] Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [7]

Пусть G — транзитивная группа подстановок на множестве Q Если стабилизатор Gp точки р 6 П, имеет г орбит на Q, то говорят, что G имеет постановочный ранг г (является группой подстановок ранга г) Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р) Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого П и две вершины р, q смежны в Г, если q е Г(р) [16]

Д Хигман ([16]-[22]) развил теорию групп ранга 3 Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин Такие графы являются дистанционно транзитивными графами диаметра 2

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

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п) Этот граф является сильно регулярным гра-

фом с параметрами ((£), 2(п — 2),п — 2,4) В работах 1959-60 годов Л Чанг [14] и А Хоффман ([23], [24]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8 Для случая п — 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л Чангом в 1949 году [13]

Реберный граф Ь(Кт<п) полного многодольного графа Кт%п является кореберно регулярным графом с параметрами (тп, т + п — 2, 2) Граф Кт,п называют т х п решеткой При т = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2,2) С Шрикханде в [29] показал, что граф, имеющий параметры пхп решетки является либо решеткой, либо графом Шрикханде (п = 4)

Результаты Л Чаига, С Шрикханде и А Хоффмана [25] были объединены Дж Зейделем [28], который определил все сильно регулярные графы с наименьшим собственным значением —2 Дж Зей-дель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, I рафы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чан-га

В работе рассматриваются неориентированные графы без петель и кратных ребер Если а, Ь - вершины графа Г, то через ¿(а, Ь) обозначается расстояние между а и 6, а через Г, (а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а

Подграф 14 (а) называется окрестностью вершины а и обозначается через [а] Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а

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

Граф Г называется реберно регулярным графом с параметрами (у,к,Х), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках

Граф Г называется вполне регулярным графом с параметрами (и, к, А, /1), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [6] содержит р. вершин в случае ¿(а, Ь) — 2 Вполне регулярный граф диаметра 2 называется сильно регулярным графом

Число вершин в [а] П [6] обозначим через А(а, Ь), если (1{а, Ь) = 1, а соответствующий подграф назовем Х-подграфом

Если ¿(а,Ь) = 2, то число вершин в [а] Г) [Ь] обозначим через ц(а,Ь), а соответствующий подграф назовем ц-подграфом

Если вершины и, и> находятся на расстоянии г в Г, то через Ьг(и, го) (через Сг(и, ги)) обозначим число вершин в пересечении Г!+1(и) (Гг_1(и)) с Г(ги) Заметим, что в реберно регулярном графе число 61 (и, и>) не зависит от выбора смежных вершин и,ги и обозначается через Ъ\ Граф Г диаметра д. называется дистанционно регулярным с массивом пересечений {Ьо,Ьъ )Ьй-ъсъ если значения

Ьг(и,и)) и Сг(и,1и) не зависят от выбора вершин и, ю на расстоянии г в Г для любого г = О, , й

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

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

1) Изучить связные реберно регулярные графы с параметрами (у, к, А) и к > 3&1 - 3

2) Найти возможные автоморфизмы сильно регулярных графов с малыми параметрами А и ц

3) Найти возможные автоморфизмы дистанционно регулярных графов диаметра 3 с малым числом вершин

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

Научная новизна Основные результаты, полученные в работе, являются новыми Выделим из них следующие

1 Исследованы связные реберно регулярные графы с параметрами (у, к, А) и к > 3Ьх - 3

2 Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (ь, к, 3,1) и изучены группы автоморфизмов графов с параметрами (3905,64, 3,1) и (9705,100,3,1)

3 Найдены возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с массивом пересечений {8,7,5,1,1,4}

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

Апробация работы. Основные результаты работы докладывались на

Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения А И Старостина (Нальчик, 2006 г) и на 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2006-2007 гг),

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

Публикации Основные результаты диссертации опубликованы в работах [31]—[36] Работы [31]—[35] выполнены в нераздельном соавторстве с А А Махневым

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

Результаты диссертации.

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы В главе I рассматриваются связные реберно регулярные графы с параметрами (и, к, Л) и к > 3&1 - 3

При изучении реберно регулярных графов с к > /(61) для некоторых функций / удается установить оценку V < д(к) (или получить описание графов, для которых не выполняется оценка V < д(к)) Так, в [7, лемма 14 2] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (ь,к, А), в котором к > 36ь то диаметр Г равен 2 и V < 2к — 2 Фактически доказано, что у < к — 2 + 3&1 + 3/(&1 +1), и уточнение границы для числа вершин потребует описания графов с малыми значениями и графов, насыщенных хорошими парами вершин В следствии из [1] доказано, что если Г — связный реберно регулярный граф с параметрами (и, к, Л), в котором ЗА > 2к — 5 (равносильно, к > 3&1 — 2), то либо Г — многоугольник или граф икосаэдра, либо к — 4 и каждое ребро графа Г лежит в единственном треугольнике, либо Г — граф диаметра 2 с не более чем 2к вершинами, пятиугольник, 3x3 решетка или треугольный граф Т(7) Через Т(к) обозначим класс регулярных графов степени к без треугольников, а через 8(к) — класс реберных графов для графов из Т(к) Пусть расстояние между вершинами и,и) в реберно регулярном графе Г равно 2 Пару (и,ги) назовем хорошей, если /л(и,ги) = к — 2Ь\ + 1, назовем почти хорошей, если ц{и,ы) = к — 2Ъ\ + 2

Граф Р{т) си — 5т2, к = 4т — 2 и 61 = 2т — 1 получается заменой вершин пятиугольника на попарно непересекающиеся тхтп решетки

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

Теорема 1 Пусть Г — связный реберно регулярный граф с параметрами (ь,к,\) и Ъ\ ~ к — А — 1 Если и € Г, и), г — две несмежные вершины из Г2(и) и ц{и,ги) — ц(и,г) = к — 2Ьх + 2, то для 7 = |[ы]П [и/] П [л]| выполняются следующие утверждения

(1) к < 61(3 - (27 - 6)/(72 - З7 + 2)) + 7 - 6, причем в случае равенства = 261 — 2 + 7 и каждая вершина из ([и] — [гу] и [г]) и ([ги] П [г]) — [и]) смежна с одной или с двумя вершинами из [и] Л И П [г],

(2) к < 2ЬХ + 7 — 6 + 461/(7 + 1)> причем в случае равенства г) — 2Ь\ — 2 + 7 и каждая вершина из ([м] — [ад] и [г]) и ([т] П

[г]) — [ы]) смежна с (7 — 1)/2 вершинами из [и] П [и/] П [г],

(3) если 7 > 1, то к < — 4, причем в случае к = ЗЬа — 4 получим 7 = 2

Следствие 1 Пусть Г — вполне регулярный граф с параметрами (и, к, А, д) и (1 = к — 2&1 + 2 Тогда Г — либо гра§6 Зейделя, либо тривалентный граф без треугольников диаметра, большего 2, с /* = 1

Теорема 2 Пусть Г — связный реберно регулярный граф с параметрами (у, к, А) и А > 2&/3 — 2 (равносильно, Л; > ЗЬх — Тогда выполняется одно из следующих утверждений

(1) диаметр Г не больше 2 и либо число вершин V не превосходит 2к + 4, либо граф Г совпадает с графом Р(2) или локально шестиугольным графом на 17 или 19 вершинах,

(2) диаметр Г не меньше 3 и Г является тривалентнъим графом без треугольников, реберным графом четырехвалентного графа без треугольников или локально шестиугольным графом,

(3) Г — граф диаметра 3 с |Гз(и)| < 1 для любой вершины и

Следствие 2 Пусть Г — связный вполне регулярный граф диаметра, большего 2, с параметрами (г>, к, А, /х) и к > З&х — 3 Тогда выполняется одно из следующих утверждений

(1) Г б £(4) иц = Ъ 1-2 = 1,

(2) Г 6 Т(3) и £(3) и /х = 61 - 1 = 1,

(3) /г = и Г является п-угольником, п > 6, полным двудольным графом К4 4 с удаленным максимальным паросочетанием, графом икосаэдра, графом Джонсона 7(6,3), локально Т(6)-графом Тэйлора на 32 вершинах или локально Шлефли-графом Тэйлора на 56 вершинах

Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А, /г) = (3,1)

Автоморфизмы сильно регулярных графов с (л — 1 рассматривались в [4, 6] для графов Мура и в [5] для графов с А = 2 (хорошо известно, что сильно регулярные графы с А = ц — 1 не существуют)

Известно (предложение 112 [7]), что сильный граф с р, > 2 регулярен Поэтому непустые подграфы неподвижных точек 2-автоморфизмов сильно регулярного графа с шах{А, ц} < 2 либо являются кликами, либо сильно регулярны с этими же параметрами

Пусть Г - сильно регулярный граф с параметрами (г>, к, 3,1), (5 = А1й(Г) Тогда п2 = (А—р)2+4{к —/х) = 4к, причем окрестность любой вершины является объединением изолированных 4-клик Поэтому к = 4и2,п = 4и и Г имеет неглавные собственные значения п — т — 2и-|-1 и —7П = 1—2и Далее, V = 1 + 4и2 + 16и2(и2 — 1), условие целочисленности выполнено, и так как число 5-клик в Г равно ук/20, то V? сравнимо с 0 или 1 по модулю о Для д € С через а\(д) обозначим число пар вершин {и, и9) таких, что и,и9 смежны

Через 1?1х(з) обозначим подграф индуцированный на множестве вершин графа Г, неподвижных относительно автоморфизма д

Мельницей называется граф Г, совпадающий с а-1 для некоторой вершины а, в котором [а] является объединением изолированных клик одинаковых порядков

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

Теорема 3 Пусть Г — сильно регулярный граф с параметрами (у, к, 3,1), д — элемент простого порядка р из Аи1;(Г) и О = Р1х(д) Тогда V = 16и4—12и2+1, к — 4и2 для некоторого натурального числа и такого, что и2 сравнимо с 0 или 1 по модулю 5 и либо р — 2, ■каждая вершина из Г — О смежна с единственной вершиной из £1 и выполняется одно из утверждений

(1) П — сильно регулярный граф с А = 3, ц = 1 степени 4ги2 и и = 2ш2 — 1 делит а\(д)/4 + и?,

(2) П = а1 для некоторой вершины а б Г и 4и делит (д),

либо р = 3 и выполняется одно из утверждений

(3) О — одновершинный граф, 3 делит и и 4и делит а\ (д),

(4) П является подграфом из а1, причем £2(а) содержит х изолированных вершин и у клик порядка 4, 3 делит (и2 — 1, х + у — 1) и 2и делит их+ 2у — х,

(5) О. — граф Петерсена и и = 6,

(6) — граф Хоффмана-Синглтона и и = 9 или 21,

(7) — граф Ашбахера и и — 10601,

(8) Г2 - является сильно регулярным графом с Л = 3,/г = 1 степени 4и>2, число и2 — и? делится на 3 и и делит 4и;4 — Зш2,

либо р > 5 и выполняется одно из утверждений

(9) - пустой граф, р делит 1 + 4и2 + 16и2 (и2 — 1) и 4и делит сц(д) + 2и + 1,

(10) — одновершинный граф, р делит и2 и 4и делит а.\{д),

(11) является 5-кликой, р делит и2 — 1 и 4и делит а^д) — 4,

(12) Г2 является мельницей на 4х + 1 вершинах из о-1-, р делит (и2 — 1,2 — 1) и 4и делит 4х — а\(д),

(13) Г2 — сильно регулярный граф степени 4ы2 с А = 3, ц = 1, число р делит и2 — и? и и делит 4и>4 — Зад2 — ац(д)/4

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (3905,64,3,1), д - элемент простого порядка р из Аи^Г) и О, — Р1х(р) Тогда выполняется одно из следующих утверждений

(1) р > 3, П — либо пустой граф, р — 5,11 или 71 и 16 делит а1(я) + 9, либо является 5-кликой, р = 5 и а\(д) = 5(16в + 4), либо является мельницей на 4х 4-1 вершинах из а1 для некоторой вершины а, р — 5, х = 6 или 11, сх\(д) = 5(16(7 + 8) или 5(16г + 12) соответственно,

(2) р = 3 и Г2 является подграфом из а1, содержащим х изолированных вершин и у клик порядка 4, где (х, у) е {(0,4), (0,16), (2,5), (4, 6), (6,7), (8,8), (16,0)},

(3) р = 2 и = ах для некоторой вершины а

Следствие 3 Сильно регулярный граф с параметрами (3905,64,3, 1) не является вершинно транзитивным

Теорема 5 Пусть Г — сильно регулярный граф с параметрами (9701,100,3,1), д — элемент простого порядка р из А^(Г) и О = ^гх(д) Тогда выполняется одно из следующих утверждений

(1) р = 89 или 109, П либо пустой граф и 20 делит 0:1(9) + И-

(2) р = 5, П является одновершинным графом, и а\ (д) делится на 20,

(3) р = 3, Г2 — подграф из а-1, и С1(а) является объединением х изолированных вершин и у клик порядка 4, 3 делит х + у — 1 и 5 делит 2х 4- у,

(4) р = 2 и Г2 = ах для некоторой вершины а

Следствие 4 Порядок группы автоморфизмов сильно регулярного графа Г с параметрами (9701,100,3,1) делит 2г3 5289 109 и Г не является вершинно транзитивным графом

В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с массивом пересечений {8, 7,5,1,1,4}

Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г Хигмеп предложил оригинальный метод, использующий теорию характеров конечных групп Этот метод изложен в монографии П Камерона [12], причем он применялся только к изучению инволютивных автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1) Позднее, в работах [2]-[4] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений В данной работе этот метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа с массивом пересечений {8, 7,5,1,1,4} на 135 вершинах

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

Теорема 6 Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {8,7,5,1,1,4}, С? = Аи^Г), д — элемент из (7 простого порядка р и П = Р1х(р) Тогда верно одно из утверждений

(1) р = 3 или 5 и П — пустой граф,

(2) р = 7 и Г2 является двухвершинной кликой,

(3) р = 2, П состоит вершин, попарно находящихся на расстоянии 3 в Г, и |П| = 3,5,7,9 или 11

Следствие 5 Дистанционно регулярный граф, имеющий массив пересечений {8, 7,5,1,1,4}, не является вершинно транзитивным

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

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

[1] Махнев, А А Об одном классе реберно регулярных графов/ А А Махнев, И M Минакова// Известия Гомельского гос унта- 2000- ТЗ- С 145-154

[2] Махнев, А А Об автоморфизмах сильно регулярных графов с Л = 0, ц = 2/ А А Махнев, В В Носов// Мат сб - 2004 - Т185, №3 - С 47-68

[3] Махнев, А А Об автоморфизмах графов с Л = 1, ц = 2/ АА Махнев, ИМ Минакова// Дискрет матем - 2004- Т16, №1-С 95-104

[4] Махнев, А А Об автоморфизмах графа Ашбахера/ А А Махнев, Д В Падучих// Алгебра и логика - 2001 - Т 40, №2 - С 125134

[5] Махнев, А А Узкие частичные четырехугольники и их автоморфизмы / А А Махнев , M С Нирова // Труды 37-й молодежной конф Екатеринбург, 2006 - С 25-27

[6] Aschbacher, M The nonexistence of rank three permutation groups of degree 3250 and subdegree 57 / M Aschbacher //J Algebra -1971-V 19, №3-P 538-540

[7] Brouwer, A E Distance-regular graphs/ A E Biouwer, A M Cohen, A Neumaier// Berlin etc Springer-Verlag - 1989 - 495 с

[8] Brouwer, AE Block designs/ AE Brouwer, HA Willbrink// Handbook of incidence geometry buildings and foundations/ F Buekenhout - Elsever Science Amsterdam - 1995 - P 349-383

[9] Brouwer, A E The Gewirtz graph an exercize in the theory of graph spectra/A E Brouwer, W H Haemers// Europ J Comb- 1993-Vol 14 - P 397-407

[10] Buekenhout, F Foundations of incidence geometry / F Buekenhout// Handbook of incidence geometry buildings and foundations/ F Buekenhout - Elsever Science Amsterdam - 1995 -P63 107

[11] Buekenhout, F Finite diagram geometries extending buildings/ F Buekenhout, P Pasmi//Handbook of incidence geometry buildings and foundations/ F Buekenhout — Elsever Science Amsterdam -1995- P 1143-1255

[12] Cameron, P Permutation Groups/ P Cameron - London Math Soc Student Texts 45 Cambridge Umv Press, 1999

[13] Chang, L C The uniqueness and nonumqueness of triangular association schemes/ LC Chang// Sci Recoid- 1949- Vol3-P 604-613

[14] Chang, L C Association schemes of partially balanced block designs with parameters v = 28, nj = 12, no = 15 and = 4/ L C Chang// Sci Record - 1950 - Vol 4 - P 12-18

[15] Damercll, R M On Moore graphs/Damcrell R M - Math Pioc Cambr Phil Soc - 1973 - Vol 74 - P 227-236

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

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

[18] Higman, D G Intersection matricies for finite permutation groups/ D G Higman// J Algebra - 1967 - Vol 6 - P 22 42

[19] Higman, D G On finite affine planes of rank 3/ D G Higman// Math Z - 1968 - Vol 104 - P 147-149

[20] Higman, D G A survey of some questions and resalts about rank 3 permutation groups/ D G Higman// Actes, Cjngres Int Math Rome - 1970 - Vol 1 - P 361 -365

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

[22] Higman, D G Coherent configurations/ D G Higman// Rend Sem Mat Umv Padova - 1970 - Vol 44 - P1-26

[23] Hoffman, A J On the uniqueness of the triangular association scheme/ A J Hoffman// Ann Math Stat - 1960 - Vol 31 - P 492497

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

[25] Hoffman, A J On the lme-graphs of the complete bipartite graph/ A J Hoffman// Ann Math Stat - 1964 - Vol 35 - P 883-885

[26] Prager, C E Low rank representations and graphs for sporadic groups/ C E Prager, L H Soicher - Lecture series 8 - Cambridge University press - 1997

[27] Numata, M On a characterization of a class of regular graphs/ M Numata// Osaka J Math - 1974 - Vol 11 - P 389-400

[28] Seidel, J J Strongly regular graphs with (-1,1,0) adjaccncy matrix having eigenvalue 3/ J J Seidel// Linear Algebra and Appl - 1968 -Vol 1 - P 281-298

[29] Shrickhande, S S The uniqueness of the association scheme/ S S Shnckhande// Ann Math Stat - 1959 - Vol 30 - P 781-798

[30] Tits, J Buildings of Spherical Type and finite BN-pairs/ J Tits// Springer Lecture Notes in Mathematics - Vol 386

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

[31] Белоусов, И Н О почти хороших парах вершин в реберно регулярных графах / И Н Белоусов, Л А Махнев // Известия Уральскою госуниверситета - 2005- Т 36, №7 - С 35-48

[32] Белоусов, И Н О почти хороших парах в реберно регулярных графах/ И Н Белоусов, Е И Гурский, А С Дергач, А А Махнев // Труды 37-й молодежной конф Екатеринбург, 2004 - С 911

[33] Белоусов, И Н О реберно регулярных графах с к > 3&1 — 3 / И Н Белоусов, А А Махнев // Алгебра и анализ - 2006 Т 18, №4 С-10-38

[34] Белоусов, И Н О сильно регулярных графах с ц = 1 и их автоморфизмах / И Н Белоусов, А А Махнев // Доклады Академии Наук - 2006 - Т 410, №2 С -151-155

[35] Белоусов, И Н Об автоморфизмах дистанционно регулярного графа с массивом пересечений {8,7,5,1,1,4}/ И II Белоусов, А А Махнев // Труды 37-й молодежной конф Екатеринбург, 2006 - С 3-6

[36] Белоусов, И Н О сильно регулярных графах с ц — 1 и их автоморфизмах, II / И Н Белоусов // Труды 38-и молодежной конф Екатеринбург, 2007 - С 3-6

Подписано в печать 11 05 07 Формат 60 х 84 1/16 Бумага писчая

Плоская печать Тираж 100 Заказ №65

Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г Екатеринбург, ул Мира 19

Введение

1 Реберно регулярные графы с к > 3bi —

1.1 Предварительные результаты.

1.2 Доказательство теоремы 1.

1.3 Вполне регулярные графы с ц = к — 2Ь\ + 2 .2G

1.4 Редукция к графам диаметра 3.

1.5 Графы диаметра 3.

2 О сильно регулярных графах с fi = 1 и их автоморфизмах

2.1 Предварительные результаты.G

2.2 Автоморфизмы графов с параметрами (v,k,3,l).G

2.3 Автоморфизмы графа с параметрами (3905,04,3,1).G

2.4 Группа автоморфизмов графа с параметрами (3905,04,3,1)

2.5 Автоморфизмы графа с параметрами (9701,100,3,1).

2.0 Группа автоморфизмов графа с параметрами (9701,100,3,1).

3 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {8,7,5; 1,1,4}

3.1 Предварительные результаты.

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

3.3 Ипволютивные автоморфизмы графа с массивом пересечений {8,7,5;1,1,4}.

3.4 Граф с массивом пересечений {8,7,5; 1,1,4} ие является вершинно транзитивным.

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно па некоторой геометрии и все геометрии этого класса допускают классификацию ([15]-[19], [37], [36]). Например, класс билдингов Титса характеризует группы лиева типа [40]. Позднее в этом направлении возникли задачи, пе связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [15].

Пусть G — транзитивная группа подстановок на множестве Q. Если стабилизатор Gp точки р (Е Q, имеет г орбит на О,, то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Т(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого Q и две вершины p,q смежны в Г, если q £ Г(р) [20].

Д. Хигман ([26]—[32]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.

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

Первые результаты о комбинаторно симметричных графах были получо ны в пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами ((2), 2(п — 2),п — 2,4). В работах 1959-60 годов J1. Чанг [23] и А. Хоффмап ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены JI. Чапгом в 1949 году [22].

Реберный граф L(K„hn) полного многодельного графа Кт,п является ко-ребсрио регулярным графом с параметрами (mn,m + п — 2,2). Граф К1П)П называют m, х п решеткой. При m — п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Шрикханде в [39] показал, что грае]), имеющий параметры n х п решетки является либо решеткой, либо графом Шрикхаиде (п = 4).

Результаты JI. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейделем [38], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п X n-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через d(a, Ь) обозначается расстояние между а и Ь, а через Г;(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.

Подграф Ti(a) называется о?;рсстиостыо вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

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

Граф Г называется рсберно регулярным графом с параметрами (v, к, Л), если Г содержит v вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.

Граф Г называется вполне регулярным графом с параметрами (v, к, A,/i), если Г рсберно регулярен с соответствующими параметрами и подграф [а]П[6] содержит [1 вершин в случае d(a,b) = 2. Вполне регулярный грае}) диаметра 2 называется сильно 'регулярным графом.

Число вершин в [а] П [6] обозначим через Л (а, 6), если d(a,b) = 1, а соответствующий подграф назовем Х-подграфюм.

Если d(a,b) = 2, то число вершин в [а] П [Ь] обозначим через ц(а,Ь), а соответствующий подграф назовем /л-подграфом.

Если вершины u,w находятся на расстоянии г в Г, то через b[(u, w) (через Ci(u,w)) обозначим число вершин в пересечении Г,-+1(и) (r,-i(u)) с Г(гу). Заметим, что в рсберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин u,w и обозначается через &1.Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {&о, h,bd-1; ci,., Cd}, если значения w) и сг(м, w) не зависят от выбора вершин u,w на расстоянии г в Г для любого i = 0, .,d.

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

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

1) Изучить связные рсберно регулярные графы с параметрами (v, k, X) и к> 36i - 3.

2) Найти возможные автоморфизмы сильно регулярных графов с малыми параметрами А и /х.

3) Найти возможные автоморфизмы дистанционно регулярных графов диаметра 3 с малым числом вершин.

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

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

1. Исследованы связные реберно регулярные графы с параметрами (v, к, А) и к > 3&i — 3.

2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (v, к, 3,1) и изучены группы автоморфизмов графов с параметрами (3905,64,

3,1) и (9705,100,3,1).

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с массивом пересечений {8,7,5; 1,

1,4}.

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

Апробация работы. Основные результаты работы докладывались на:

Международной школе-конференции но теории групп, посвященной 75-летию со дня рождения А.И.Старостина (Нальчик, 200G г.) и па 37-й и 38-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 200G—2007 гг.);

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

Публикации. Основные результаты диссертации опубликованы в работах [42]-[47]. Работы [42]-[4G] выполнены в нераздельном соавторстве с А.А. Мах-невым.

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

Результаты диссертации.

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются связные реберно регулярные графы с параметрами (v, к,Х) и к > 3— 3.

При изучении реберно регулярных графов с к > f(b{) для некоторых функций / удается установить оценку v < д{к) (или получить описание графов, для которых не выполняется оценка v < д{к)). Так, в [15, лемма 1.4.2] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v,k,X), в котором к > 3&i, то диаметр Г равен 2 и v < 2к — 2. Фактически доказано, что v < к — 2 + 3&i + 3/(&i + 1), и уточнение границы для числа вершин потребует описания графов с малыми значениями hi и графов, насыщенных хорошими парами вершин. В следствии из [1] доказано, что если Г — связный реберно регулярный граф с параметрами (v, к, Л), в котором ЗА > 2& —5 (равносильно, к > 3&i —2), то либо Г — многоугольник или граф икосаэдра, либо к = 4 и каждое ребро графа Г лежит в единственном треугольнике, либо Г — граф диаметра 2 с не более чем 2к вершинами, пятиугольник, 3x3 решетка или треугольный граф Т{7). Через Т(к) обозначим класс регулярных графов степени к без треугольников, а через 8(к) — класс реберных графов для графов из Т(к). Пусть расстояние между вершинами u,w в реберно регулярном графе Г равно 2. Пару (и,ги) назовем хорошей, если fJ.(u,w) = к — 2&1-Н, назовем почти хорошей, если fi(u,w) = к — 2Ь\ + 2.

Граф .Р(га) с v = 5т2, к .= 4т — 2 и &i = 2т — 1 получается заменой вершин пятиугольника на попарно непересекающиеся т х га решетки. Следующие результаты является основными в главе I.

Теорема 1 Пусть Г — связный реберпо регулярный граф с параметрами (v,k, Л) и Ь\ = к — А — 1. Если и £ Г, - две несмсжныс вершины из Гг(и) и ц(и, w) = ц(щ z) = к—2&1+2, то для j = выполняются следующие утверэ/сдепия:

1) к < 6i(3 — (27 — 6)/(72 — З7 + 2)) + 7 — 6, причем в случае равенства z) = 26i — 2 + 7 и каждая вершина из ([u] — [w] U [z]) U ([w] П [z]) — [u])

CMCDiciia с одной или с двумя вершинами из [и] П [w] П [z\;

2) k < 2&i + 7 — 6 + 461/(7 + 1)> причем в случае равенства fi(w,z) = 26i — 2 + 7 и ка'ждая вершина из ([и] — [ш] U [z]) U ([гу] П [z]) — [и]) смеэюна с (у — 1)/2 вершинами из [и] П [w] П [z);

3) если 7 > 1, то k < 36i — 4, причем в случае к = 36i — 4 получим 7 = 2.

Хорошо известно, что если любая пара вершин связного реберпо регулярного графа, находящихся на расстоянии 2, является хорошей, то граф оказывается пятиугольником или графом икосаэдра. С помощью теоремы 1 получено описание связных реберпо регулярных графов, в которых любая пара вершин, находящихся на расстоянии 2, является почти хорошей.

Следствие 1 Пусть Г — вполне регулярный граф с параметрами (v, к, Л, /л) и ц = к — 2&i + 2. Тогда Г — либо граф Зейделя, либо тривалентный граф без треугольников диаметра, большего 2, с fi = 1.

Теорема 2 Пусть Г — связный реберпо регулярный граф с параметрами (и, к, Л) и к > 36i — 3. Тогда выполняется одно из следующих утверждений: (1) диаметр Г не больше 2 и либо число вершин v не превосходит 2к + 4, либо граф Г совпадает с графом Р(2) или локально шестиугольным графом на 17 или 19 вершинах;

11775729

2) диаметр Г не меньше 3 и Г является тривалентиым графом без треугольников, реберным графом четырехвалентного графа без треугольников или локально шестиугольным графом;

3) Г — граф диаметра 3 с |Гз(и)| < 1 для любой вершины и.

Следствие 2 Пусть Г — связный вполне регулярный граф) диаметра, большего 2, с параметрами (v, k,X,fi) и k > 3b\ — 3. Тогда выполняется одно из следующих утверэюдений:

1) Г е £{4) и ц = h - 2 = 1;

2) Г е Т(3) U£(3) un = bi- 1 = 1;

3) ц = bi и Г является п-угольником, п > 6, полным двудольным графом 4 с удаленным максимальным паросочетанием, графом икосаэдра, графом Джонсона J(6,3), локально Т(6)-графом Тэйлора на 32 вершинах или локально Шлафли-графюм Тэйлора на 56 вершинах.

Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А,^) = (3,1).

Автоморфизмы сильно регулярных графов с (j, = 1 рассматривались в [4, 13] для графов Мура и в [5] для графов с А = 2 (хорошо известно, что сильно регулярные графы с А = ц — 1 не существуют).

Известно (предложение 1.1.2 [15]), что сильный граф с ц > 2 регулярен. Поэтому непустые подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с тах{А,//} < 2 либо являются кликами, либо сильно регулярны с этими же параметрами.

Пусть Г — сильно регулярный граф с параметрами (v, к, 3,1), G = Aut(r). Тогда п2 = (А — /i)2 + 4(к — ц) = 4к, причем окрестность любой вершины является объединением изолированных 4-клик. Поэтому к = 4и2,п = 4и и Г имеет неглавные собственные значения п — m = 2и + 1 и — m = 1 — 2и. Далее, v = 1 + 4u2 + 1Qu2(u2 — 1), условие целочислеииости выполнено, и так как число 5-клик в Г равно vk/20, то и2 сравнимо с 0 или 1 по модулю 5.

Для д 6 G через ai(g) обозначим число пар вершин (и,ия) таких, что и, и9 смежны.

Через Fix(g) обозначим подграф индуцированный на множестве вершин графа Г, неподвижных относительно автоморфизма д.

Мельницей называется граф Г, совпадающий с а1 для некоторой вершины а, в котором [а] является объединением изолированных клик одинаковых порядков.

Графом Грюнберга-Кегеля (графом простых чисел) конечной группы G называется граф, вершинами которого являются простые делители |С?| и два делителя р, г смежны в этом графе, если G содержит элемент порядка рг.

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

Теорема 3 Пусть Г — сильно регулярный граф с параметрами (v, к, 3,1); д — элемент простого порядка р из Aut(r) и О, = Fix(g). Тогда v = 16u4 — 12w2 + 1, k = 4и2 для некоторого натурального числа и такого, что и2 сравнимо с 0 или 1 по модулю 5 и либо р = 2, каэ/сдая вершина изТ — Q, смежна с единственной вершиной из О, и выполняется одно из утверждений:

1) О, — сильно регулярный граф с л = 3, fi = 1 степени 4 w2 ии — 2 w2 — 1 делит a\(g)/4w2;

2) fi = а^- для некоторой вершины а Е Г и 4и делит ot\(g); либо р = 3 и выполняется одно из утверждений:

3) О, — одновершинный граф, 3 делит и и 4и делит &\{д);

4) q является подграфом из а1, причем Q,(a) содержит х изолированных вершин и у клик порядка 4, 3 делит (и2 — 1, х-\-у — 1) и 2и делит их + 2у — х;

5) О, — граф Петерсена и и = 6;

6) О, — граф Хоффмана-Синглтона и и = 9 или 21;

7) О, — граф Ашбахера и и = 10601;

8) О, — является сильно регулярным графом с Л = 3, д = 1 степени 4w2, число и2 — w2 делится на 3 и и делит 4w4 — 3w2; либо р>Ъ и выполняется одно из утверэ/сдений:

9) Q — пустой граф, р делит l+4u2+16u2(it2—1) и 4и делит ai(g)+2u+l;

10) Q — одновершинный граф, р делит и2 и 4и делит OL\{g);

11) Q является 5-кликой, р делит и2 — 1 и 4и делит ai(g) — 4;

12) Q является мельницей на 4ж+1 вершинах из а1, р делит (и2—1, х—1) и 4и делит 4х — а\ (д);

13) П — сильно регулярный граф степени 4w2 с А = 3, р — 1, число р делит и2 - w2 и и делит 4w4 — 3w2 — a\{g)/4.

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (3905,64,3, 1), g — элемент простого порядка р из Aut(T) и Q, = Fix(g). Тогда выполняется одно из следующих ymeepoicdenuu:

1) р > 3, Q — либо пустой граф, р = 5,11 или 71 и 16 делит а\(д) + 9, либо является 5-кликой, р — 5 и a\{g) = 5(16s + 4), либо является мельницей на 4х + 1 вершинах из а1 для некоторой вершины а, р = 5, х = 6 или 11, ai(g) = 5(16g + 8) или 5(16г + 12) соответственно;

2) р = 3 и fi является подграфом из а1, содерэ/сагцим х изолированных вершин и у клик порядка 4, где (х,у) Е {(0,4), (0,16), (2,5),

4,6), (6,7), (8,8), (16,0)};

3) р = 2 м О = ах для некоторой вершины а.

Следствие 3 Сильно регулярный граф с параметрами (3905,64,3,1) не является вершинно транзитивным.

Теорема 5 Пусть Г — сильно регулярный граф с параметрами (9701,100,3, 1)? 9 ~ элемент простого порядка р из Aut(r) и Q = Fix(#). Тогда выполняется одно из следующих утверждений:

1) р = 89 или 109, О, — либо пустой граф и 20 делит а:^) + 11;

2) р = 5, fi является одновершинным графом, и оц(д) делится па 20;

3) р = 3, О, — подграф из а1, и Q(a) является объединением х изолированных вершин и у клик порядка 4, 3 делит х + у — 1 и 5 делит 2х + у;

4) р = 2 и О, = а1 для некоторой вершины а.

Следствие 4 Порядок группы автоморфизмов сильно регулярного графа Г с параметрами (9701,100,3,1) делит 2^3 • 5289 -109 и Г не является вершинно транзитивным графом.

В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярных графов с массивом пересечений {8,7,5; 1,1,4}.

Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмеп предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона [20], причем он применялся только к изучению инволютивпых автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [2]-[4] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений. В данной работе этот метод применяется для изучения автоморфизмов гипотетического дистанционно регулярного графа с массивом пересечений {8,7,5; 1,1,4} па 135 вершинах.

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

Теорема 6 Пусть Г — дистанционно регулярный граф), имеющий массив пересечений {8,7,5; 1,1,4}; G = Aut(r), g — элемент из G простого порядка р и О, = Fix(g). Тогда верно одно из утверждений:

1) р = 3 или 5 и Q — пустой граф;

2) р = 7 и Q является двухвершинной кликой;

3) р = 2, Q состоит вершин, попарно находящихся на расстоянии 3 в Г, и = 3,5,7,9 или 11.

Следствие 5 Дистанционно регулярный граф, имеющий массив пересечений {8,7,5; 1,1,4}, не является вершиино транзитивным.

1. Махнев, А.А. Об одном классе реберно регулярных графов/ А.А. Махнев, И.М. Минакова// Известия Гомельского гос. ун-та- 2000.- Т.З.- С. 145-154.

2. Махнев, А.А. Об автоморфизмах сильно регулярных графов с Л = 0, ц = 2/ А.А. Махнев, В.В. Носов// Мат. сб.- 2004.- Т.185, №3.- C.47-G8.

3. Махнев, А.А. Об автоморфизмах графов с Л = 1, /л = 2/ А.А. Махнев, И.М. Минакова// Дискрет, матем.- 2004.- T.1G, М.- С.95-104.

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

5. Зарииов, С.Р. Реберно регулярные графы диаметра 2 с А > 2к/3 — 2/ С.Р. Зарииов, А.А. Махиев, И.П. Яблоико// Труды Украинского матем.конгресса. Киев, 2001, секция 1: Алгебра и теория чисел, Институт математики НАН Украины, Киев 2003.- C.4G-61.

6. Махнев, А.А. О сильной регулярности некоторых реберно регулярных графов/ А.А. Махнев// Известия РАН, сер. матем.- 2004.- T.G8.- С.159-172.

7. Кабанов, В.В. Об отделимых графах с некоторыми условиями регулярности/ В.В. Кабанов, Махнев А.А.// Матем. сборник.-1996.- Т.187, №9. С.495-503.

8. Кондратьев, А.С. Распознавание знакопеременных групп простой степени/ А.С. Кондратьев, В.Д. Мазуров // Сиб. матем. ж.- 2000.- Т.41, №2ю-С.359-369.

9. Aschbacher, М. The nonexistence of rank three permutation groups of degree 3250 and subdegrce 57 / M. Aschbacher // J. Algebra.- 1971.- V. 19, №3.-P.538-540.

10. Bombieri, E. Thompson's problem (a2 = 3)/ E. Bombieri// Invent. Math.-1980.- V. 58.- P.77-100.

11. Brouwer, A.E. The Gcwirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Haemers// Europ. J. Comb.- 1993.- Vol.14.- P.397-407.

12. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995.- P.G3-107.

13. Buekenhout, F. Finite diagram geometries extending buildings/ F. Buekenhout, P. Pasini// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout.— Elsever Science. Amsterdam.- 1995.- P.1143-1255.

14. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.

15. Cameron, P. J. Graphs, Codes and Desidns. / Cameron P. J., van Lint J.London Math. Soc., Student Texts №22, Cambridge: Cambridge Univ. Press, 1991.

16. Chang, L.C. The uniqueness and nonuniquencss of triangular association schemes/ L.C. Chang// Sci. Record.- 1949.- Vol.3.- P.G04-G13.

17. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, щ = 12, no = 15 and p2 = 4/ L.C. Chang// Sci. Record.-1950.- Vol.4.- P.12-18.

18. Darnerell, R.M. On Moore graphs/Damerell R.M.- Math. Proc. Cambr. Phil. Soc.- 1973.- Vol.74.- P.227-23G.

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

20. Higman, D.G. Intersection matricies for finite permutation groups/ D.G. Higman// J. Algebra.- 1967.- Vol.6.- P.22-42.

21. Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z.-1968.- Vol.104.- P. 147-149.

22. Higman, D.G. A survey of some questions and resalts about rank 3 permutation groups/ D.G. Higman// Actes, Cjngres Int. Math. Rome.-1970.-Vol.l.- P.361-365.

23. Higman, D.G. Characterization of families of rank 3 permutation groups by the subdegrces I, II/ D.G. Higman// Arth. Math.- 1970.- Vol.21.- P.151-156; 353-361.

24. Higman, D.G'. Coherent configurations/ D.G. Higman// Rend. Sein. Mat.Univ. Padova.- 1970.- Vol.44.- P.l-26.

25. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960.- Vol.31.- P.492-497.

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

27. Hoffman, A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman// Ann. Math. Stat.- 1964.- Vol.35.- P.883-885.

28. Nurnata, M. On a characterization of a class of regular graphs/ M. Numata// Osaka J. Math.- 1974.- Vol.11.- P.389-400.

29. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soiclier.- Lecture series 8.- Cambridge: University press.-1997.

30. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl.- 19G8.- Vol.1.- P.281-298.

31. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande// Ann. Math. Stat.- 1959.- Vol.30.- P.781-798.

32. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.38G.

33. Walter, J. The characterization of finite groups with abelian Sylow 2-subgroups/ J. Walter// Ann. Math.- 19G9.- V. 89.- P.405-514.Работы автора по теме диссертации

34. Белоусов, И.Н. О почти хороших нарах вершин в реберно регулярных графах / И.Н. Белоусов, А.А. Махнев // Известия Уральского госуниверситета.- 2005.- Т. 3G, №7. С.35-48.

35. Белоусов, И.Н. О почти Хороших парах в ребер но регулярных графах/ И.Н. Белоусов, Е.И. Гурский, А.С. Дергач, А.А. Махнев // Труды 37-й молодежной копф. Екатеринбург, 2004.- С.9--11.

36. Белоусов, И.Н. О реберно регулярных графах с к > 3bi — 3 / И.Н. Белоусов, А.А. Махнев // Алгебра и анализ.- 200G. Т. 18, Ш. С.-10-38.

37. Белоусов, И.Н. О сильна регулярных графах с ц = 1 и их автоморфизмах, II / И.Н. Белоусов // Труды 38-й молодежной конф. Екатеринбург, 2007.- C.3-G.