Границы для числа вершин в графах и автоморфизмы графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Исакова, Мариана Малиловна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2010
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ
804613753
На правах рукописи
М-^ЬП,'
ИСАКОВА Мариана Малиловна
ГРАНИЦЫ ДЛЯ ЧИСЛА ВЕРШИН В ГРАФАХ И АВТОМОРФИЗМЫ ГРАФОВ
01.01.06 — математическая логика, алгебра и теория чисел
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук
Екатеринбург - 2010 ^ ®
004613753
Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН.
Научный руководитель:
доктор физико-математических наук,
профессор, чл.-корр. РАН МАХНЕВ Александр Алексеевич
Официальные оппоненты:
доктор физико-математических наук, профессор
РОЖКОВ Александр Викторович
кандидат физико-математических наук БЕЛОУСОВА Вероника Игоревна
Ведущая организация: Уральский государственный университет
Защита состоится 23 ноября 2010 года в 12.00 часов на заседании специализированного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской, 16.
С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, 16).
Автореферат разослан 46 октября 2010 года
Ученый секретарь диссертационного совета, кандидат физ.-мат. наук
ИИ. Белоусов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.
Актуальность темы. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [8]. Например, класс билдингов Титса характеризует группы лиева типа [15]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [7].
Пусть б — транзитивная группа подстановок на множестве Г2. Если стабилизатор Ор точки р £ А, имеет г орбит на П. то говорят, что б имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе (7 удается построить сильно регулярный граф Г, множество вершин которого П и две вершины р, q смежны в Г, если £ Г(р) [10].
Д. Хигман ([10]—[14]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через с1(а, Ь) обозначается расстояние между а и Ь, а через Г, (а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г! (а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (и, к, А), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в А треугольниках.
Граф Г называется вполне регулярным графом с параметрами
(v,k,X,fi), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит ц вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Пусть J- — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локально А-графом.
Пусть Г — реберно регулярный граф с параметрами (и, к, Л) и f>i = к—Х—1. Пара вершин и, w называется (почти) хорошей, если d(u, tu) = 2 и fj.(u, w) равно к - 2bi + 1 (равно к — 2bi + 2). Тройка вершин (u, tu, z) называется (почти) хорошей, если w,z б Гг(и) и ц(и,и>) + ц(и, z) не больше 2к - 4bi + 3 (равно 2к — Abi + 4).
A.A. Махнев [1] получил следующее свойство хороших троек:
Пусть Г — реберно регулярный граф, содержащий хорошую тройку (u,w, z) и 5 = \\и] П [w] П {г]|. Тогда выполняются следующие утверждения:
(1) если /л{и,ю) = p(u,z) — к — + 1, то 5 — 0 в случае, когда вершины w, z не смежны и ä < 1 в случае, когда вершины w, z смежны;
(2) если fi(u, w) + ß(u, z) = 2к — Щ + 3, то S < 1.
С помощью этих результатов получается новое доказательство классификации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий. В [2] была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (v, к,Х), к = 3bi +7 и 7 > —2. Если (и, w, z) — почти хорошая тройка «Д=[и]П [ги] П [z] — непустой граф, то вершины tu, z смежны и выполняется одно из следующих утверждений:
(1) |А| < 2 ы 7 < -1;
(2) подграф А является 3-кликой, Ь\ = 6, к = 16 и v = 31;
(3) подграф А является Ъ-кликой, Ь\ — 3 и Г — граф Клебша;
(4) подграф А является А-кликой, Ь\ = 5 и Г — граф Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов с к > ЗЬг — 2.
Цель диссертации. Целью данной работы является решение следующих задач:
1. Найти новые верхние границы для числа вершин реберно регулярных графов с к > 36х-
2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (64,35,18,20).
3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (396,135,30,54) и уточнить результаты в случае, когда граф является точечным для частичной геометрии рО^Ь, 26).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие:
1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к > ЗЬх-
2. Определены возможные порядки элементов группы б автоморфизмов сильно регулярного графа с параметрами (64,35,18,20), в частности, установлено, что 7г(С) С {2,3,5,7}.
3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (396,135, 30,54). Результаты существенно уточнены в случае, когда Г — точечный граф частичной геометрии рйг(5,26).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались
на:
Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).
Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.
Публикации. Основные результаты диссертации опубликованы в работах [16]-[22]. Работы [16]-[21] выполнены в нераздельном соавторстве с A.A. Махневым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем работы — 70 стр.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются реберио регулярные графы с к > 3bj. Во второй главе выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (64,35,18,20). В третьей главе работы определяются возможные автоморфизмы сильно регулярного графа Г с параметрами (396,135.30,54). Результаты уточняются в случае, когда Г — точечный граф частичной геометрии pG2{5,26).
Результаты диссертации.
Пусть Г — связный реберно регулярный граф с параметрами (v, к, Л), к > 3fc>i- Тогда диаметр Г не больше 2. Основным результатом главы 1 является
Теорема 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (v,k, А), к = 3bi + 7, 7 > 0. Тогда выполняются следующие утверждения:
(1) если некоторая вершина и образует хорошие пары с двумя вершинами w,z, то вершины w,z не смежны и либо ß(w, z) > 3bj/2 и v - k - 1 < 5Ь\/2, либо ц{т, z) < 36J2 и v - k - 1 < 36j - (З7 + 19)/2;
(2) если имеется хорошая пара, но нет вершин, лежащих в двух хороших парах, то v — к — 1 < min{56i/2,З61 — 7 — 8};
(3) если в Г нет хороших пар, то либо
(г) в Г нет почти хороших пар uv — к — 1 < 3bj — 2-у — 9 + (272 + 157 + 27)/(&! +7 + 3), либо
(И) некоторая вершина образует почти хорошие пары с двумя смежными вершинами и Г — граф Клебша или граф Шлефли, или 7 = 0 uv~k~l<2b1~l + (2 - 4)/5, либо
(ш) в Г есть почти хорошая пара, но пет вершин, образующих почти хорошие пары с двумя смежными вершинами и v — к — 1 <
ЗЬг - 27 - 9 + (272 + 157 + 29)/(6i + 7 + 3).
Эта теорема уточняет границы для числа вершин, полученные A.A. Махневым и Д.В. Падучих [6].
Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Если а = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами: V = (s + 1)(1 + st/a), k = s(t + 1), А = (s - 1) + {а - 1 )t, ß = a(t+ 1). Любой сильно регулярный граф с такими параметрами для некоторых a, s, t называется псевдогеометрическим графом для pGa{s, t).
В теореме 2 из [3] найдены параметры сильно регулярных графов, в которых окрестности вершин являются псевдогеометрическими графами для pGx(2x,t), где х < 3. В случае х = 2 граф имеет параметры (210,95,40,45), и возможные автоморфизмы такого графа изучались в [4]. В случае х = 3 имеется много возможностей для параметров графа. Но если t = 2, то возможны лишь параметры (64,35,18,20) или (76,35,18,14). Во второй главе диссертации найдены возможные автоморфизмы сильно регулярного графа с параметрами (64,35,18,20) и определены подграфы их неподвижных точек. Для автоморфизма g через ai{g)
обозначим число пар вершин (и, и3) таких, что ¿(и, и9) = г.
Теорема 2 Пусть Г — сильно регулярный граф с параметрами (64,35,18,20), С — АиЦГ), д — элемент простого порядка р из (2 и П = РЬс(д). Тогда 7г(С) С {2,3,5,7} и верно одно из утверждений:
(1) О, — пустой граф, р = 2 и а\(д) делится на 16;
(2) является п-кликой, р = 7, п = 1, а\(д) =35 или р = 2 и п е {4,6,8};
(3) О. является 4-кокликой, р = 5 и а\{д) = 20;
(4) Г2 является объединением т (т > 2) изолированных клик порядков П\ > ... > пт, р — 2 и либо
(г) щ = 6, < 10 и гц = 2 для г > 1, либо
(И) щ = 4, |П| < 8 и щ — 2 для г > 1 или пг = 4, либо
(ш) щ = 2 и |Г2| < 10;
(5) О. содержит 2-лапу, р — 3 и либо
(г) П — четырехугольник или .Кг,5-подграф, либо (¿г) = 10 гх Г2 содержит такие две несмежные вершины с, ¿, что Г2(с) П [(¿] — объединение двух изолированных вершин и А'3 3-подграфа, либо
(ш) |0| = 13 и а\(д) € {15,39}, либо (¿и) |П| = 16 и а\(д) = 0;
(6) П содержит 2-лапу, р = 2 и либо |П| € {6,8,..., 28}, либо «1(5) = 0, |П| = 32 и Г — П — граф Тэйлора, в котором окрестности вершин изоморфны точечному графу обобщенного четырехугольника (7(3(2,2).
Для подмножества вершин Б графа Г через Г(5) обозначим подграф Паез({а} - 5).
Граф Г называется /-изорегулярным. если для любого г < 2 и любого ¿-вершинного подмножества 5 число |Г(5)| зависит только от изоморфного типа подграфа, индуцированного 5. Граф Г на г» вершинах называется абсолютно изорегулярным, если он является (и — 1)-изорегулярным, ¿-изорегулярный граф Г называется точно ¿-изорегулярным, если он не является (£ + 1)-изорегулярным. Камерон доказал, что каждый 5-изорегулярный граф Г является абсолютно изорегулярным и с точностью до перехода к дополнительному графу, Г является полным многодольным графом Ктхп, пятиугольником, или 3 х 3-решеткой. Каждый точно 4-изорегулярный граф является экстремальным графом Смит (с
точностью до перехода к дополнительному графу, Г является псевдогеометрическим графом для рСг(2г, 2г3 4- 3г2 - 1)). Обозначим такой граф через 1го(г). При г = 1 получим точечный граф единственного обобщенного четырехугольника порядка (2,4), а при г = 2 — граф Маклафлина. А.А. Махнев [5] доказал, что 1го(г) не существует в случае г — 3. Вторая окрестность вершины в графе 1го[г) при г — 3 является сильно регулярным графом с параметрами (640,243,66,108). Вопрос о существовании графа с такими параметрами открыт.
Пусть Г — сильно регулярный граф с параметрами (640,243,66,108), а — вершина графа Г. Тогда Г имеет собственные значения к = 243, г = 3,5 = —45 и достигается равенство во втором условии Крей-на: (в + 1 )(к + в + 2гй) < (к + г)(г + I)2. Поэтому [а] является сильно регулярным графом с параметрами (243,66,9,21) и Гг(а) — сильно регулярный граф с параметрами (396,135,30,54). Таким образом, для исследования автоморфизмов сильно регулярного графа с параметрами (640,243,66,108) необходимо изучить автоморфизмы сильно регулярных графов с параметрами (243,66,9,21) и (396,135,30,54).
В третьей главе диссертации найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (396,135,30,54).
Теорема 3 Пусть Г является сильно регулярным графом с параметрами (396,135,30,54), д — автоморфизм простого порядка р графа Г, Г2 — . Тогда выполняется одно из следующих утверждений:
(1) О — пустой граф, р € {2,3,11};
(2) П является п-кликой, и либо р = 5, п = 1 и аг(д) £ {15,165, 315}, либо р — 13, п = 6 и 0:1(5) = либо р = 2, п £ {4,6} и сц(д) — 3п — 12 делится на 60;
(3) П является 3^кокликой, р = 3, а\(д) = 94 4- 90г + 42, г € {0,1,...,3} и 4 < 14;
(4) П — объединение I > 2 изолированных клик порядков п,; 6 {2,4}, р = 2 и 3|Г2| — 01(5) + 12 делится на 60;
(5) р = 13, либо |П| =32 и ах(д) = 78, либо |П| =45 и а^д) = 117, либо |П| = 58 и а\(д) — 156, либо |Г2| = 71 и 0:1(3) = 195;
(6) р = 11, либо = 66 и а\(д) = 0, либо |П| = 77 и а^д) = 33, либо |П| = 88 и аг(д) = 66, либо |П| = 99 и сц(д) = 99;
(7) р = 7 и либо
(г) |Г2| = 116 и 01(3) = 0, либо
(И) |П| = 81, а.](д) = 105 и на Г — П имеются 45 семиугольных (д)-орбит, либо
(ш) |П| € {74,67,60,53,39,32} м^Щ 6 {84,63,42,21,189,168} соответственно, либо (гг>) |П| = 46 и сц(д) <Е {0,210};
(8) р = 5, |П| = 5г + 1, 4 < г < 19 и аг{д) + 15г + 15 делится на 150;
(9) р = 3, = 3£, а1(5)/18 - Ц + 3)/2 делится на 3 и 2 < г < 24 или i е {27,33};
(10) р = 2, |£2| = 2*, ^ > 3, (01(5) - 12 - 6^/30 четно и либо 4 < 78, либо t = 88.
Сильно регулярный граф с параметрами (396,135,30,54) является псевдогеометрическим для частичной геометрии рС2(5,26). В следующей теореме найдены возможные автоморфизмы частичной геометрии рСг(5,26), подграфы неподвижных точек которых содержат геодезический 2-путь.
Теорема 4 Пусть Г является точечным графом частичной геометрии рйг(5,26), <3 — группа автоморфизмов графа Г, д — элемент простого порядка р из <3. Если 12 = ¥1х(д) содержит геодезический 2-путь, то выполняется одно из следующих утверждений:
(1) р = 7,0, является частичной геометрией рС?г(5,5) и а\(д) = 105;
(2) р = 5, О является частичной геометрией рСг(5,6) и либо а\ {9) — 0) либо на Г — П имеются 60 пятиугольных (д)-орбит;
(3) р = 3 и — либо частичная геометрия р(?2(5,¿), £ 6 {2,5}, либо частичная геометрия р(?г(2,2);
(4) р = 2, является частичной геометрией рС2(5,£), /, £ {2,6} или частичным пространством прямых порядка (4,^, £ - четно.
Автор выражает глубокую благодарность своему научному руководителю профессору АА.Махневу за постановку задачи, внимание и поддержку, а также всем участникам семинара отдела алгебры и топологии ИММ УрО РАН за критические замечания и плодотворное обсуждение результатов диссертации.
Список литературы
[1] Махнев А.А. О хороших парах в реберно регулярных графах/ А.А. Махнев, А.А. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет. матем.-2003,- Т.15.- С.77-97.
[2] Махнев А.А. О почти хороших тройках вершин в реберно регулярных графах / В.И. Казарина, А.А. Махнев // X Белорусская матем. конф. Тез. докл. Минск.- 2008.- С. 46.
[3] Махнев А.А. О сильно регулярных графах с к = 2ц и их расширениях / А.А. Махнев // Сиб. матем. журнал.- 2002.- Т. 43, е 3 - С. 609-619.
[4] Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45) / А.А. Махнев, Н.В. Чуксина // VII Международная школа-конференция по теории групп,- Тез. докл.-Челябинск.- 2008,- С. 78-79.
[5] Махнев А.А. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) / А.А. Махнев // Украинский матем. журнал.- 2002,- Т. 54, е 7.- С. 941-949.
[6] Падучих Д.В. Новая оценка для числа вершин реберно регулярных графов / А.А. Махнев, Д.В. Падучих // Сибирский матем. журнал.-2007.- Т. 48, е 4,- С. 817-832.
[7] Brouwer А.Е. Distance-regular graphs/ А.Е. Brouwer, А.М. Cohen, А. Neumaier// Berlin etc: Springer-Verlag.- 1989.- 495 с.
[8] Buekenhout F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. - Elsever Science. Amsterdam.- 1995.- P.63-107.
[9] Gardiner A. Homogeneous graphs / A.Gardiner // J. Comb. Theory.-1976.- V. 20.- P. 94-102.
[10] Higman D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z.- 1964,- Vol.86.- P. 145-156.
[11] Higman D.G. Primitive rank 3 groups with a prime subdegree/ D.G. Higman// Math. Z.- 1966.- Vol.91.- P.70-86.
[12] Higman D.G. Intersection matricies for finite permutation groups/ D.G. Higman// J. Algebra.- 1967.- Vol.6.- P.22-42.
[13] Higman D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z.- 1968.- Vol.104.- P. 147-149.
[14] 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.
[15] Tits J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.
Работы автора по теме диссертации
[16] Исакова М.М. О числе вершин в реберно регулярных графах с к > 3Ь\ / М.М. Исакова, А.А. Махнев // Труды 40-й Всеросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург.- 2009.- С. 16-18.
[17] Исакова М.М. О числе вершин в реберно регулярных графах с к > 36i / М.М. Исакова, А.А. Махнев // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина. КБГУ: Нальчик.- 2009. - С. 57-61.
[18] Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (64,35,18,20) / М.М. Исакова, А.А. Махнев // Тезисы 41-й Всеросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург- 2010.-С. 19-22.
[19] Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) / М.М. Исакова, А.А. Махнев // Теория групп и ее приложения. Труды межд. конф., посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик - 2010.- С. 110113.
[20] Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (64,35,18,20) / М.М. Исакова, А.А. Махнев // Труды ИММ УрО РАН,- 2010.- Т. 16, е 3.- С. 603-619.
[21] Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) / М.М. Исакова, A.A. Махнев // Владикавказский матем. журнал.- 2010.- Т. 12, е 3.- С. 32-42.
[22] Исакова М.М. Об автоморфизмах частичной геометрии рС2(5,26) / М.М. Исакова // Сибирские электронные матем. известия.- 2010.- Т. 7,- С. 150-154.
ИСАКОВА Мариана Малнловна
ГРАНИЦЫ ДЛЯ ЧИСЛА ВЕРШИН В ГРАФАХ И АВТОМОРФИЗМЫ ГРАФОВ
Автореферат диссертации на соискание ученой степени кандидата физика-математических наук
На празах рукописи
Формат 60*84/16. Печать о<рс. Бумага офс. Гарнитура «Тайме». Усл. печ. л. 1,0. Тираж 100 экз. Заказ 217. Отпечатано в Издательстве И.П. «Полиграфия».
Лицензия № 3070706100020. КНР, г.Нальчик, ул.Чсрнышсвского, 131.
Введение
1 Реберно регулярные графы с к > ЗЬ
1.1 Предварительные результаты.
1.2 Графы с хорошими парами.
1.3 Графы без хороших пар.
2 Автоморфизмы графа с параметрами (64,35,18,20)
2.1 Предварительные результаты.
2.2 Автоморфизмы графа с параметрами (64,35,18,20).
3 Автоморфизмы графа с параметрами (396,135,30,54)
3.1 Предварительные результаты.
3.2 Автоморфизмы графа с параметрами (396,135,30,54)
3.3 Автоморфизмы малых порядков.
3.4 Автоморфизмы частичной геометрии рС'2(5,26).
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([20]-[24], [37], [21]). Например, класс билдингов Титса характеризует группы лиева типа [38]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].
Пусть С — транзитивная группа подстановок па. множестве 17. Если стабилизатор Ср точки р 6 имеет г орбит на то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе С удается построить сильно регулярный граф Г, множество вершин которого О и две вершины р, д смежны в Г, если д 6 Г(р) [29].
Д. Хигман ([29]—[35]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через с1(а, Ъ) обозначается расстояние между а и Ь, а через Г\(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г^а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным, графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (и,к,Х), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (?;. к. А, /л), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[6] содержит ¡1 вершин в случае с?(а, Ь) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [Ь] обозначим через А(а, 6), если с1(а,Ь) = 1, а соответствующий подграф назовем \~подграфом.
Если 6) = 2, то число вершин в [а] П [6] обозначим через /¿(а, 6), а соответствующий подграф назовем ц-подграфом.
Если вершины и, т находятся на расстоянии г в Г, то через Ъ^и. ъи) (через С{(и, га)) обозначим число вершин в пересечении Гг+^и)
Г^1(гг)) с Г(ги). Заметим, что в реберно регулярном графе число Ь\(и, ш) не зависит от выбора смежных вершин и,ь) и равно 61 = к — Л — 1.Граф Г диаметра с? называется дистанционно регулярным с массивом, пересечений {¿о, ¿1, • - •. Ь(1-1; сх,., с^}, если значения ги) и сг-(/и, ш) не зависят от выбора вершин и, и> на расстоянии г в Г для любого г = 0,., й.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу А, то граф Г назовем локально А-графом.
Пусть Г — реберно регулярный граф с параметрами (v, к, А) и Ъ\ = к—Л—1. Пара вершин u,w называется (почти) хорошей, если d(u,w) = 2 и fi(u,w) равно к — 2bi + 1 (равно к — 2&i + 2). Тройка вершин (u,w,z) называется (почти) хорошей, если w, z е Г2(и) и ¡i{u, w) + fi(u, z) не больше 2к — 4Ь\ + 3 (равно 2к — 46i + 4).
Основанием для развития метода хороших пар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (v,k, Л) и 61 = к — Л — 1. Если вершины и, w находятся на расстоянии 2 в Г, то выполняются следующие утверждения:
1) степень любой вершины в //-подграфе из Г не меньше к — 2i>i;
2) вершина d имеет степень а в графе [w] П [ги], тогда и только тогда, когда [d] содержит точно а — (к — 2Ь\) вершин вне и1- U w1;
3) если ß{u,w) = к — 26i + 1, то подграф [w] П [гу] является кликой и [d] Сихи w1- для любой вершины d £ [и] П [ги];
4) если Г — (г¿J- U w1) содержит единственную вершину z, то fi(u, z) =
A.A. Махнев [1] получил следующее свойство хороших троек:
Пусть Г — реберно регулярный граф, содержащий хорошую тройку (и, ги, z) и 5 = \[и] П [w] П [z]|. Тогда выполняются следующие утверждения:
1) если /j,(u,w) = fi(u, z) = к — 2bi + 1, то 5 — 0 в случае, когда вершины w, z не смежны и 6 < 1 в случае, когда вершины w< z смежны;
2) если /.¿(w, w) + fi(u, ги) = 2к — 4Ь\ + 3, то 8 < 1.
С помощью этих результатов получается новое доказательство класснфикации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] - [5|). В [6]) была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (у, к, А), к = З61 + 7 и 7 > —2. Если — почти хорошая тройка и
Д = [п] П [и>] П [г] непустой граф, то вершины и>, г смежны и выполняется одно из следующих утвероюдепий:
1) |А| < 2 м 7 < — 1/
2) подграф) А является, 3-кликой, Ьу = 6, к = 16 и V = 31;
3) подграф) Д является 3-кликой, Ь\ = 3 и Г — граф Клебша;
4) подграф) Д является А-кликой, Ьу — 5 и Г — граф Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов с к > ЗЬ\ — 2.
Цель диссертации. Целью данной работы является решение следующих задач:
1. Найти новые верхние границы для числа вершин реберно регулярных графов с к > ЪЬ\.
2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (64,35,18,20).
3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (396,135,30,54) и уточнить результаты в случае, когда граф является точечным для частичной геометрии ^2(5, 26).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.
1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к > 3&i.
2. Определены возможные порядки элементов группы G автоморфизмов сильно регулярного графа с параметрами (64,35,18,20), в частности, установлено, что 7t(G) С {2,3, 5, 7}.
3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (396,135,30,54). Результаты существенно уточнены в случае, когда Г — точечный граф частичной геометрии pGo(5,26).
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжют изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного типа.
Апробация работы. Основные результаты работы докладывались на:
Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).
Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.
Публикации. Основные результаты диссертации опубликованы в работах [39]—[45]. Работы [39]—[44] выполнены в нераздельном соавторстве с A.A. Мах-невым.
Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем работы — 70 стр.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются реберно регулярные графы с к > 3Ъ\. Во второй главе выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (64,35,18,20). В третьей главе работы определяются возможные автоморфизмов сильно регулярного графа Г с параметрами (396,135,30,54). Результаты уточняются в случае, когда Г — точечный граф частичной геометрии ^^2(5, 26).
Содержание диссертации.
Пусть Г — связный реберно регулярный граф с параметрами (г>, к, А), к > Збх. Тогда диаметр Г не больше 2. Основным результатом главы 1 является
Теорема 1 Пусть Г — связный неполный реберно регулярный граф с 'параметрами (у,к*Х), к = 3&1 + 7, 7 > 0. Тогда выполняются следующие утверждения:
1) если некоторая вершина и образует хорошие пары с двумя вершинами и>, г, то вершины ги, г не смеэюпы и либо (¿(ш, г) > 3&г/2 и V — к — 1 < 5Ь[/2, либо ¡1{ги, г) < ЗЪг/2 и V - к - 1 < ЗЬг - (З7 + 19)/2;
2) если имеется хорошая пара, но нет вершин, леэюащих в двух хороших парах, то V — к — 1 < тт{5б1/2, 3&1 — 7 — 8};
3) если в Г нет хороших пар, то либо г) в Г нет почти хороших пар ии — к — 1 < 3&1 — 27 — 9 + (272 + 167 + 27)/(¿»1 +7 + 3), либо гг) некоторая вершина образует, почти хорошие пары с двумя с.меэ/сными вершинами и Г — граф Клебша или граф Шлефли или 7 = 0 uv — k — 1 < 2bi - 1 + (2&i - 4)/5, либо
Иг) в Г есть почти хорошая пара, но нет вершин, образующих почти хорошие пары с двумя смежными вершинами uv — k— 1 < 3b\ — 2/у — 9 + (272 + 157 + 29)/(6i+7 + 3).
Эта теорема уточняет границы для числа вершин, полученные A.A. Мах-невым и Д.В. Падучих [18].
Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на ¿ + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s, /.). Если а — ¿, то геометрия называется сетью. Точечным, графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко попять, что точечный граф частичной геометрии pGa(s: t) сильно регулярен с параметрами: v — (s + 1)(1 + st/а)} k — s(t + 1), А = (s — 1) + (а — 1 )£, ¡1 — a(t + 1). Любой сильно регулярный граф с такими параметрами для некоторых а, s,t называется псевдогеометрическим, графом для pGn(s, t.).
В теореме 2 из [7] найдены параметры сильно регулярных графов, в которых окрестности вершин являются псевдогеометрическими графами для pGx(2x,t), где х < 3. В случае х = 2 граф имеет параметры (210,95,40,45), и возможные автоморфизмы такого графа изучались в [8]. В случае х — 3 имеется много возможностей для параметров графа. Но если t = 2, то возможны лишь параметры (64,35,18,20) или (76,35,18,14). Во второй главе диссертации найдены возможные автоморфизмы сильно регулярного графа с параметрами (64,35,18,20) и определены подграфы их неподвижных точек. Для автоморфизма д через а^д) обозначим число пар вершин (и, ид) таких, что с1(и, и9) = %.
Теорема 2 Пусть Г — сильно регулярный граф с параметрами (64,35.18,20), С? = Аи^Г), д — элемент простого порядка р из С и О = ¥[х(д). Тогда ■^(С) ^ {2,3, 5, 7} и верно одно из утверждений:
1) Г2 — пустой граф, р = 2 и а\(д) делит,ся на 16;
2) Г2 является п-кликой, р = 7, п = 1, су\(д) = 35 или р = 2 и п € {4, 6,8};
3) является 4-кокликой, р = Ъ и (У.\(д) — 20;
4) О, является объединением т (га > 2) изолированных клик порядков п\ > . > пт, р = 2 и либо г) пх = 6; |Г2| < 10 и щ = 2 ¿ля. г > 1, либо и) п1 = 4, < 8 и щ = 2 для г > 1 или П2 — 4, либо ш) П1 = 2 и |П| < 10;
5) содержит, 2-лапу, р = 3 и либо г) О — четырехугольник или К2$~подграф), либо п) |П| = 10 и О, содержит такие две несмеоюпые вершины с,с1, что Щс) П Щ — объединение двух изолированных вершин и К^-подграфа, либо (Ш) = 13 и а\(д) & {15, 39}; либо (ъу) |П| = 16 « = 0;
6) Г2 содержит 2-лапу, р = 2,и либо е {6, 8,., 28}, либо а\(д) ~ 0; |Г2| = 32 и Г —Г2 — граф Тэйлора, в котором окрестности вершин изоморфны точечному графу обобщенного четырехугольника СС2(2,2).
Для подмножества вершин S графа Г через Г(5) обозначим na6s([a] — S). Граф Г называется t-изорегулярным, если для любого i < I и любого г-вершинпого подмножества S число |Г(5")| зависит только от изоморфного типа подграфа, индуцированного S. Граф Г на v вершинах называется абсолютно изорегулярным, если если он является (г> — 1)-изорегулярным. Камерон [26, теорема 8.21] доказал, что каждый 5-изорегулярный граф Г является абсолютно изорегулярным, и с точностью до перехода к дополнительному графу, Г является полным многодольным графом Ктхп: пятиугольником, или 3 х З-решеткой. А каждый точно 4-изорегулярный граф является экстремальным графом Смит (с точностью до перехода к дополнительному графу, Г является псевдогеометрическим графом для pGr(2r,2r3 + Зг2 — 1)). Обозначим такой граф через Izo(r). При г — 1 получим точечный граф единственного обобщенного четырехугольника порядка (2,4), а при г — 2 — граф Маклафлина. A.A. Махнев [15] доказал, что Izo(r) не существует в случае г = 3. Вторая окрестность вершины в графе Izo{3) является сильно регулярным графом с параметрами (640,243,66,108). Вопрос ©существовании графа с такими параметрами открыт.
Пусть Г — сильно регулярный граф с параметрами (640,243,66,108), а — вершина графа Г. Тогда Г имеет собственные значения к = 243, г — 3,s = —45 и достигается равенство во втором условии Крейна: (s + 1)(к + s + 2rs) < (к + s)(r + I)2. Поэтому [а] является сильно регулярным графом с параметрами (243,66,9,21) и Г2(а) — сильно регулярный граф с параметрами (396,135,30,54). Таким образом, для исследования автоморфизмов сильно регулярного графа с параметрами (640,243,66,108) необходимо изучить автоморфизмы сильно регулярных графов с параметрами (243,66,9,21) и (396,135,30,54).
В третьей главе диссертации найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (396,135,30,54).
Теорема 3 Пусть Г является сильно регулярным графом с параметрами (396,135, 30, 54), д — автоморфизм простого порядка р графа Г, = Р1х(д). Тогда выполняется одно из следующих утверждений:
1) — пустой граф, р £ {2,3,11};
2) О, является п-кликой, и л,ибо р = 5, п = 1 и <у.\{д) £ {15,165, 315}, либо р = 13, п = 6 и а\(д) = 0, либо р = 2, п £ 4, 6 и а\{д) — 3п — 12 делит,ся на 60;
3) является Ы-кокликой, р = 3, а\(д) = Ш + 90г + 42, г £ {0,1,., 3} и £ < 14;
4) О — объединение I > 2 изолированных клик порядков щ £ {2, 4}, = 2 и 3|Г2| — а\{д) -+-12 делится на 60;
5) р = 13, либо |Г2| = 32 и ос\(д) = 78, л,ибо = 45 и а\(д) — 117, либо |П| = 58 и а\(д) = 156, либо |П| -71 и аг(д) = 195;
6) р = 11, либо = 66 и а\(д) = 0, либо = 77 и ос\(д) = 33, либо = 88 и ах(д) = 66, либо |Г2| = 99 и аг(д) = 99;
7) р = 7 и либо г) |Г2| = 116 и «1 (д) = 0, либо
И) = 81, а\(д) — 105 и на Г — имеются 45 семиугольных (д)-орбит, либо ш) |П| б {74,67,60,53,39,32} и а±{д) £ {84,63,42,21,189,168} соответственно, либо |П| = 46 и аг(д) £ {0, 210};
8) р = 5, = 5г + 1, 4 < г < 19 и а\(д) + 15г + 15 делится на 150;
9) р = 3, \П\ = 3£, а\{д)/18 - (I + 3)/2 делится на 3 г/ 2 < £ < 24 шт I е {27,33};
10) р = 2, |П| = 2£ > 3, (п.^) - 12 - 6*)/30 четно и либо £ < 78; либо ¿-88.
Чачтичное пространство прямых 5 порядка (в, ¿) — это система инцидентности с множеством точек Р и множеством блоков в которой любые две прямые инцидентны не более одной точке, любая точка инцидентна ровно ^ + 1 прямым, и любая прямая инцидентна ровно в + 1 точкам. При этом каждую прямую можно отождествить с множеством инцидентных ей точек и инцидентность становится обычным включением. Две точки из Р называются коллинеарными, если они лежат на прямой. Точечный граф геометрии 5 — это граф на множестве точек Р, в котором две точки смежны, если они различны и коллинеарны. Аналогично определяется граф прямых.
Сильно регулярный граф с параметрами (396,135,30,54) является псевдогеометрическим для частичной геометрии £>(^2(5,26). В следующей теореме найдены возможные автоморфизмы частичной геометрии 26), подграфы неподвижных точек которых содержат геодезический 2-путь.
Теорема 4 Пусть Г — точечный граф частичной геометрии рС^б. 26), С - группа автоморфизмов графа Г, д элемент простого порядка р из С. Если О, = Р\х(д) содержит геодезический 2-путь, то выполняется одно из следующих утверждений:
1) р — 7, является частичной геометрией рСг(5, 5) и а\(д) = 105;
2) р = 5, является частичной геометрией 5,6) и либо <У1(д) = 0, либо на Г — О, имеются 60 пятиугольных (д)-орбит;
3) р = 3 и П - либо частичная геометрия рС2(6, I Е {2, 5}; либо частичная геометрия 2);
4) р — 2, О, является частичной геометрией рС?2(5, Ь €Е {2,6} шш частичным пространством прямых порядка (4, £), £ четно.
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмеп предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона [25], причем он применялся только к изучению инволютивных автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [9]-[12] изучались автоморфизмы сильно регулярных графов с малыми числами пересечений. В данной работе этот метод применяется для изучения автоморфизмов сильно регулярных графов с параметрами (64, 35,18, 20) и (396,135, 30, 54).
1. Махнев, А.А.О хороших парах в реберно регулярных графах/ A.A. Мах-пев, A.A. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет. матем.-2003.-Т.15.- С.77-97.
2. Махнев A.A. О реберно регулярных графах, не содержащих хороших пар / A.A. Махнев, A.C. Омельченко // Известия Гомельского госун-та.-2008,- Т. 47. С. 117-127.
3. Махнев, A.A. О реберно регулярных графах, в которых каждая вершина, лежит не более чем в одной хорошей паре / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал.- 2008.- Т. 10, № 1.- С. 53-67.
4. Махнев A.A. О почти хороших тройках вершин в реберно регулярных графах / В.И. Казарина, A.A. Махнев // X Белорусская матем. конф. Тез. докл. Минск.- 2008,- С. 46.
5. Махнев, A.A. О сильно регулярных графах с к = 2/л и их пасширениях / A.A. Махнев // Сиб. матем. журнал,- 2002.- Т. 43, № 3.- С. 609-619.
6. Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45) / A.A. Махнев, Н.В. Чуксина // VII Международная школа-конференция по теории групп.- Тез. докл.- Челябинск.- 2008.- С. 78-79.
7. Махнев, A.A. Об автоморфизмах графа Ашбахера/ A.A. Махнев, Д.В. Падучих // Алгебра и логика.- 2001.- Т.40, № 2,- С. 125-134.
8. Махнев, A.A. Об автоморфизмах сильно регулярных графов с Л — 0, ¡1 = 2/ A.A. Махнев, В.В. Носов// Мат. сб.- 2004,- Т.185, № 3,- С. 47-68.
9. Махнев, A.A. Об автоморфизмах графов сЛ = 1,/х = 2/ A.A. Махнев, И.М. Минакова // Дискрет, матем,- 2004,- Т.16, № 1,- С. 95-104.
10. Белоусов H.H. О сильно регулярных графах с /л = 1 и их автоморфизмах / H.H. Белоусов, A.A. Махнев // Доклады Академии Наук.- 2006.- Т. 410, № 2.- С. 151-155.
11. Махнев, A.A. О расширениях частичных геометрий, содержащих малые //-подграфы /A.A. Махнев // Дискр. анализ и исслед. операций.- 1996.-Т.З.- С.71-83.
12. Махнев, A.A. О сильной регулярности некоторых реберно регулярных графов / A.A. Махнев // Известия РАН, сер. матем.- 2004,- Т.68.- С .159172.
13. Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) / A.A. Махнев // Украинский матем. журнал.- 2002,Т. 54, № 7.- С. 941-949.
14. Журтов А.Х. Об автоморфизмах 4-изорегулярных графов / А.Х. Жур-тов, А. А. Махнев, М.С. Нирова //8 Международная школа-конференция но теории групп. Нальчик 2010. Тез. докл.- С. 94-102.
15. Кондратьев, А.С. Распознавание знакопеременных групп простой степени / А.С. Кондратьев, В.Д. Мазуров // Сиб. ма,тем. ж,- 2000,- Т. 41, № 2,- С.359-369.
16. Падучих Д.В. Новая оценка для число вершин реберно регулярных графов / А.А. Махнев, Д.В. Падучих // Сибирский матем. журнал.- 2007.Т. 48, Ш 4,- С. 817-832.
17. Aschbacher, М. The nonexistence of rank three permutation groups of degree 3250 and subdegree 57 / M. Aschbacher //J. Algebra.- 1971.- V. 19, №3,-P.538-540.
18. Brouwer, A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag.- 1989.- 495 c.
19. Brouwer, A.E. Block designs/ A.E. Brouwer, H.A. Willbrink// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995.- P.349-383.
20. Brouwer, A.E. The Gewirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Hacmers// Europ. J. Comb.- 1993.- Vol.14.- P.397-407.
21. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995.- P.63-107.
22. 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. 11431255.
23. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.
24. Cameron, P. J. Graphs, Codes and Dcsidns. / Cameron P. J., van Lint J.London Math. Soc., Student Texts №22, Cambridge: Cambridge Univ. Press, 1991.
25. Damerell, R.M. On Moore graphs/Damerell R.M.- Math. Proc. Cambr. Phil. Soc.- 1973.- Vol.74.- P.227-236.
26. Gardiner A. Homogeneous graphs / A.Gardiner // J. Comb. Theory.- 1976.-V. 20,- P. 94-102.
27. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z.- 1964,- Vol.86.- P.145-156.
28. Higman, D.G. Primitive rank 3 groups with a prime subdegree/ D.G. Higman// Math. Z.- 1966,- Vol.91.- P.70-86.
29. Higman, D.G. Intersection matricies for finite permutation groups/ D.G. Higman// J. Algebra.- 1967,- Vol.6.- P.22-42.
30. Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z-1968,- Vol.104.- P. 147-149.
31. 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.
32. 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.
33. Higman, D.G. Coherent configurations/ D.G. Higman// Rend. Sem. Mat.Univ. Padova.- 1970.- Vol.44.- P. 1-26.
34. Macay M. Search for properties of the missing Moore graph / M. Macay, J. Siran // Linear Algebra and its Appl.- 2009.- V. 432,- P. 2381-2398.
35. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher.- Lecture series 8.- Cambridge: University press.-1997.
36. Tits, J. Buildings of Spherical Type and finite BN-pairs/ Л. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации
37. Исакова М.М. О числе вершин в реберно регулярных графах с к > 3Z?i / М.М. Исакова, A.A. Махпев // Труды 40-й Всеросс. молод, копф. Изд-во ИММ УрО РАН: Екатеринбург,- 2009,- С. 16-18.
38. Исакова М.М. О числе вершин в реберно регулярных графах с к > 3&i / М.М. Исакова, A.A. Махнев // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина. КБГУ: Нальчик.- 2009. С. 57-61.
39. Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (64,35,18,20), / М.М. Исакова, A.A. Махнев // Тезисы 41-й Всеросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург,- 2010.- С. 19-22.
40. Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) / М.М. Исакова, A.A. Махнев // Теория групп и ее приложения. Труды межд. конф., посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик.- 2009.- С. 57-61.
41. Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (64,35,18,20) / М.М. Исакова, A.A. Махнев // Труды ИММ УрО РАН.- 2010.- Т. 16, № 3.- С. 102-110.
42. Исакова М.М. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) / М.М. Исакова, A.A. Махнев // Владикавказский матем. журнал,- 2010,- Т. 12, № 3,- С. 32-42.
43. Исакова М.М. Об автоморфизмах частичной геометрии pG2(5, 26) / М.М. Исакова // Сибирские электронные матем. известия,- 2010,- Т. 7 С. 150154/
