Хорошие пары вершин в реберно регулярных графах и автоморфизмы графов

Чуксина, Наталия Владимировна

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

Чуксина, Наталия Владимировна АВТОР

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

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

2009 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

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

Автореферат диссертации на тему "Хорошие пары вершин в реберно регулярных графах и автоморфизмы графов"

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

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

ЧУКСИНА Наталия Владимировна

□□3474419

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 5 ИЮН

ЕКАТЕРИНБУРГ - 2009

003474419

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

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

чл.-корр. РАН МАХНЕВ A.A.

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

профессор БАРАНСКИЙ В.А.

кандидат физ.-мат. наук, доцент ЗЮЛЯРКИНА Н.Д.

Ведущая организация: Институт математики и механики СО РАН.

Защита состоится 30 июня 2009г. в 11.00 на заседании специализированного совета Д.004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г.Екатеринбург, ул. С.Ковалевской, 16.

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

Автореферат разослан Л9 мая 2009 г.

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

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

КАБАНОВ В.В.

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

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

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

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

Граф Г диаметра d называется дистанционно транзитивным, если для любого г е {О, и для любых его вершин u,v,x,y таких, что d(u,v) — d(x,y) = г, существует автоморфизм g графа Г такой, что (u,v)g = (х, у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 (см. [23]). В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем я более общие условия комбинаторной симметричности.

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах прошлого века. Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах, или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами - 2),тг — 2,4). В работах 1959-60 годов Л. Чанг [11] и А. Хоффман ([19], [20]) независимо показали, что треугольный граф Г(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что, кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [10].

Через обозначим полный п-дольный граф с долями порядков т\, ...,т„. Если

Шх = ... = т„ = т, то соответствующий граф обозначается через Кпут. Если ш > 2, то граф К\1Ш называется тп-лапой. Реберный граф Ь[Кт,„) полного многодольного графа Кт>п является кореберно регулярным графом с параметрами (тп, т + п — 2,2). Реберный граф для Кш,п называют тхп- решеткой. Известно, что пхп- решетка является сильно регулярным графом с параметрами (п2,2п - 2, п — 2,2). С. Шрикханде в [25] показал, что сильно регулярный граф, имеющий параметры пхп- решетки является либо п х п-решеткой, либо графом Шрикханде при п = 4.

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

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

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

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

Граф Г называется реберно регулярным графом с параметрами (у,к,Х), если Г содер-

жит V вершин, является регулярным степени к и каждое ребро из Г лежит в А треугольниках.

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

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

Если вершины и, га находятся на расстоянии г в Г, то через 6<(и,ш) (соотв. с^и,«)) обозначим число вершин в пересечении ^+1(11) (соотв. с Г(-ш). Заметим, что в

реберно регулярном графе число £>1(^,111) не зависит от выбора смежных вершин и,ю и обозначается через 61.

Частичной геометрией рСа(в, 4) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит 5 + 1 точку, каждая точка лежит на 4 + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой Ь, найдется точно а прямых, проходящих через а и пересекающих Ь. Если а = 1, то геометрия рС^^) называется обобщенным четырехугольником и обозначается ССд(з^).

Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Точечный граф частичной геометрии р(?а(з, 4) сильно регулярен с параметрами V = (в+1)(1 + 54/а), к = в(4 +1), А = (з — 1) + (а-1)4, д = а(4 +1). Любой сильно регулярный граф с такими параметрами для некоторых а, в, 4 называется псевдогеометрическим графом для 4).

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

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

2) найти возможные автоморфизмы сильно регулярного графа, являющегося псевдогеометрическим для рй2(4,9);

3) найти возможные автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии pGzi4,9).

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

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

1. Исследованы связные реберно регулярные графы с параметрами (и, к,\)ък> ЗЬх—1.

2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (210,95,40,45) и (95,40,12,20).

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии pGa(4,9).

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

Апробация работы. Основные результаты работы докладывались на международном российско-китайском семинаре ( Иркутск, 2007), VII Международной школе конференции по теории групп (Челябинск, 2008) и на 39-й и 40-й Всероссийских молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2009 гг.).

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

Публикации. Основные результаты диссертации опубликованы в работах [27]—[33]. Работы [27]—[32] выполнены в нераздельном соавторстве с A.A. Махневым.

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

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

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

В главе 2 рассматриваются связные реберно регулярные графы с параметрами (г>, к, Л) и к > зг>1 - 1.

Пусть Г — реберно регулярный граф с параметрами (у, к, А) и 61 — к — Х - 1. Пара вершин и,ш называется хорошей (почти хорошей), если <1{и, хи) = 2и равно к —

2&1 +1 (равно к — 2Ьх + 2). Тройка вершин (и,и),г) называется хорошей (почти хорошей), если и,2б Гг(и) и [х(и, ш) + и, г) не больше 2к — 461+3 (равно 2к — 46] + 4).

В [1, предложение и лемма 1.9] доказано, что если Г — связный реберно регулярный граф диаметра 2 с параметрами (у, к, А), где к = ЗЬх + 7 и 7 > —2, то выполняются следующие утверждения:

(1) если Г содержит такую 3-коклику Д, что любые ее две вершины образуют хорошие пары, то 7 < —1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;

(2) если некоторая вершина и графа Г лежит в хорошей паре, то либо 7 < Ьх - 6, либо = 1 и Г — многоугольник, либо 61 = 2 и Г — граф икосаэдра или граф с к = 4 диаметра,

большего 2;

(3) если 7 > 0 и для некоторой вершины и подграф Гг(гх) содержит две вершины, образующие хорошие пары с и, то 7 < 61/2 — 2.

Уточнение утверждения (2) получено в [3]. В параграфе 2.1 доказано предложение 1 о почти хороших тройках, с помощью которого в теореме 1 получено усиление утверждения

(3).

Предложение 1 Пусть Г — связный реберно регулярный граф с параметрами (у, к, А), к = 3&1+7 «7 > 0. Если {и, ы, г) — почти хорошая тройка вершин в Г и Д = [и]П[ш]П[г], то верно одно из следующих утверждений:

(1) вершины ги, г не смежны и |Д| = 0;

(2) вершины ги, г смежны и либо

(г) подграф [«] П [ад] П [z] является 2-кликой, -у = О, ß{u,w) = ß{u,z) = bi + 2, Г2(и) П (И U [г]) = {го, z} U (И П [z]) ubi> 8, либо

(ii) подграф [и] П [ш] П [z] является 3-кликой, 7=1, fi(u, w) = р(и, z) = -f 3, 61 = 3 и Г — граф Клебша, либо

(ш) подграф [и] П [го] П [г] является 4-кликой, 7 = 1, р(и, w) = ß(u, z) = bi + 3, i>i = 5 и Г — граф Шлефли.

Теорема 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (г>, к, А) и к = 3i>i + 7, 7 > 0. Если 7 > 5bi/12 — 5, то каждая вершина графа Г лежит не более нем в одной хорошей паре.

В работе А. Браувера [4] доказано, что если Г связный неполный реберно регулярный граф с параметрами (v,k,X), в котором к > ЗЬь то диаметр равен 2 и выполняется неравенство hbi > (v - к — 1){к - 2bi + 1). В статье A.A. Махнева и Д.В. Падучих [1] эти результаты были уточнены и получена верхняя оценка для числа вершин связного реберно регулярного графа диаметра 2 с параметрами (v, к, А) и к = 36j -I- 7, 7 > —2. В параграфах 2.5-2.6 с помощью результатов о почти хороших тройках эта оценка уточняется для графов с к = З61 — 1. Доказана следующая теорема.

Теорема 2 Пусть Г — реберно регулярный граф с к — ЗЬг—1, ¡i(u, w)+p,(u, z) = 2Ьг+2 для различных w, z из Г2(и), Д = [и] П [го] П [г]. Тогда верно одно из следующих утверждений:

(1) вершины w,z не смежны и |Д| = 0;

(2) Д = {а}, ß(u,w) = /Ды,г) =bi + l, [м]П [го] — а1 содержит единственную вершину с, [и] П [г] — а1- содержит, единственную вершину е и [w] U [z] - [и] С {w, z} U([t»]n [z]);

(3) Д является 2-кокликой, [го] — ([u] U z1) содержит единственную вершину z* и [г] — ([u] Ü го-1) содержит единственную вершину vi*;

(4) Д является 2-кликой.

Следствие 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (v, k,X) uk = З&1 — 1. Тогда либо граф Г является многоугольником или графом икосаэдра, либо верно одно из утверждений:

(1) для некоторой вершины и в Г найдутся две вершины w, z, образующие хорошие пары с и, и либо вершины w,z смежны и v < 5Ьь либо вершины w,z не смежны и

V <6bi — 8;

(2) в Г нет вершин, лежащих в двух хороших парах, Г содержит хорошую пару и v<6h- 6;

(3) в Г нет хороших пар и либо

(г) Г не содержит почти хороших пар и v < 661 — 6, либо (ii) Г содержит почти хорошую тройку (u,w,z), вершины w,z смежны и и < 5í>i + (bi - 3)/2, либо

(Иг) Г не содержит почти хороших троек (и, w, z) со смежными вершинами w, z и V <6Ьх - 9 + 16/(bi +2).

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

Теорема 3 Пусть Г — связный реберно регулярный граф с параметрами к = 17 ubi — 6. Тогда v = 30, и в Г нет хороших и почти хороших пар вершин.

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

В работе A.A. Махнева [2] доказано, что связный вполне регулярный граф, окрестности вершин которого являются псевдогеометрическими графами для pGi(A,t) либо является графом Тэйлора, либо сильно регулярен с параметрами (210,95,40,45). В главе 3 с помощью метода Г. Хигмана, приведенного в [9] исследуются возможные порядки элемента в группе автоморфизмов сильно регулярного графа, а также выяснено строение подграфов неподвижных точек автоморфизмов простых порядков сильно регулярных графов с параметрами (210,95,40,45) и (95,40,12,20). Как следствие, доказано, что точечный граф частичной геометрии pG^ii, 9) не является вершинно симметричным. Кроме того, выяснено строение подграфа неподвижных точек сильно регулярного графа, окрестности вершин которого являются точечными графами частичной геометрии pGíi4,9).

Пусть Г — сильно регулярный граф, G = Aut(r), g — элемент простого порядка р из G и Í2 = Fix(j). Для автоморфизма g через a¡(g) обозначим число пар вершин (и, и9) таких, что d(u,us) = i.

Основными результатами 3 главы являются теоремы 4-6.

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (210,95,40,45), д — элемент простого порядка р из Aut(r) и П = Fix(p). Тогда верно одно из утверждений:

(1) П - пустой граф, и либор = 2, ац(д) = 210, либо р е {3,5} и 15 делит ai(g), либо р = 7 иаг{д) е {0,105,210};

(2) €1 является п-кликой и либо р = 19, п = 1 и cti(g) = 95, либо р = 2 и п 6 {2,4,6,8,10}, либо р = 3, п G {3,6,9} и Qi(p) делится на 15;

(3) П является т-кокликой, р = 5,шб{5,10,15,20} и cti(g) — 5т делится на 15;

(4) Í2 является объединением 1 (I > 2) изолированных клик порядков щ,...,n¡, р = 3 и n¡ делится на 3 для любого i G {1,..., I};

(5) Ü содержит 2-лапу и р < 13.

Из теоремы следует, что w(G) С {2,3,5,7,11,13,19}.

Теорема 5 Пусть Г — сильно регулярный граф с параметрами (95,40,12,20), g — элемент простого порядка р из Aut(F) и П = Fix{g). Тогда верно одно из утверждений:

(1) П — пустой граф и либо р = 5, ai(g) = 50 и Г имеет кликовую {д)-орбиту, либо р = 19 и а%{д) — 38;

(2) П является п-кликой, р = 3 и либо п = 2 и а^д) сравнимо с 6 по модулю 12, либо п = 5 и а\(д) делится на 12;

(3) О является т-кокликой и либо

(г) р = 5, ттг = 15, o¡i(g) = c*i(g2) = 20 или т = 10, a^g) е {10,70}, либо (ii) р = 2, т нечетно, т <17 и c*i (д) — 2т — 2 делится на 12;

(4) П содержит 2-лапу и либо

(г) р = 3, ttj(s) = 0 и |П| € {11,17,23,29}, либо

(гг) р — 2, П не является кокликой, |Г — П| = 2í, где 27 < í < 43 или t = 24, и каждая вершина из Q смежна с вершиной из Г — ÍÍ.

С помощью этой теоремы получаем

Следствие 2 Точечный граф частичной геометрии pG*2(4,9) не является вершинно симметричным.

Приведенная ниже теорема позволяет уточнить строение подграфа неподвижных точек сильно регулярного графа с параметрами (210,95,40,45), у которого окрестности вершин являются точечными графами частичной геометрии pGi(i,9).

Теорема 6 Пусть Г — сильно регулярный граф с параметрами (210,95,40,45), у которого окрестности вершин являются точечными графами частичной геометрии pGz{4,9), д — элемент простого порядка р из G = Aut(r) и П = Fix(g). Тогда tt(G) С {2,3,5,7,19} и верно одно из утверждений:

(1) П — пустой граф и либо р = 2, Qi(ff) = 210, либо р е {3,5} и 15 делит сч(д), либо р — 7 и ai(g) 6 {0,105,210};

(2) П является п-кликой и либо р — 19, п = 1 и ai(g) = 95, либо р = 3, п € {3,6} и öi(s) делится на 15;

(3) Q является т-кокликой, р = 5,тб{5,10} и а\ (д) — 5 т делится на 15;

(4) П является объединением 1 (I > 2) изолированных клик порядков n\,...,ni, р = 3, щ 6 {3,6} для любого i е {1,...,/} и |П| < 30, если П содержит б-клику, и |П| < 24, если П не содержит 6-клик;

(5) П содержит 2-лапу, и либо

(i) р — 5, П является 5-кокликовым расширением п-угольника, где п £ {4,..., 8}, или объединением двух изолированных Ki^w-подграфов, либо

(ii) р = 2, Q — половинный граф 6-куба или граф без треугольников, причем в последнем случае либо П — регулярный граф степени 17 на 54 вершинах, либо 6 < |П| < 50.

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

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

[1] Махнев, A.A. Новая оценка для числа вершин реберно регулярных графов /A.A. Мах-нев, Д.В. Падучих // Сиб. мат. журн,-2007.-Т. 48 — С. 46-61.

[2] Махнев А. А. О графах, окрестности вершин которых сильно регулярны с к = 2ц // Матем. сборник.—2000.—Т. 191, №7.- С.89-104.

[3] Махнев, А.А. О реберно регулярных графах, не содержащих хороших пар /А.А. Махнев , А.С.Омельченко // Известия Гомельского госуниверситета.- 2007 - Т. 10, №23-С.103-118.

[4] Brouwer, А.Е. Distance-regular graphs/ А.Е. Brouwer, A.M. Cohen, A. Neumaier // Berlin etc: Springer-Verlag- 1989.— 495 s.

[5] Brouwer, A.E. Block designs/ A.E. Brouwer, H.A. Willbrink // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. - Elsevier Science. Amsterdam-1995,- P.349-383.

[6] 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.

[7] Buekenhout, F. Foundations of incidence geometry / F. Buekenhout // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. - Elsevier Science. Amsterdam.- 1995 - P.63-107.

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

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

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

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

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

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

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

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

[16] 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.

[17] 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.

[18] Higman, D.G. Coherent configurations/ D.G. Higman // Rend. Sem. Mat.Univ. Padova-1970.- Vol.44.- P. 1-26.

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

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

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

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

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

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

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

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

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

[27] Махнев, A.A. О реберно регулярных графах, в которых кажда вершина лежит не более чем в одной хорошей паре /А.А.Махнев, Н.В. Чуксина // Алгебра и логика: Материалы международного российско-китайского семинара. Иркутск, 2007 - С.77-78.

[28] Махнев, A.A. О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре/А.А. Махнев, Н.В. Чуксина // Владикавказ, матем. ж.- 2008. - Т. 10, Выпуск 1,- С. 53-67.

[29] Махнев, A.A. О хороших парах вершин в реберно регулярных графах с к = 36i — 1 /А.А.Махнев, Н.В.Чуксииа // Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. Екатеринбург, УрО РАН.- 2008. С. 35-37.

[30] Махнев, A.A. О хороших парах вершин в реберно регулярных графах с к = 3&i — 1/А.А. Махнев, Н.В. Чуксина // Труды Института математики и механики УрО РАН.- 2008 - Том 14, №4,- С. 119-134.

[31] Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45)/А.А. Махнев, Н.В. Чуксина // Тезисы сообщений VII Международной школы конференции по теории групп. Челябинск, ЮУрГУ.-2008- С. 78-80.

[32] Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (95,40,12,20)/А.А. Махнев, Н.В. Чуксина // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. Екатеринбург, УрО РАН.- 2009.- С. 52-53 .

[33] Чуксина, Н.В. Автоморфизмы графа с окрестностями вершин из рСг(4,9) // Сибирские электронные математические известия,- 2009 - Т. 6 - С. 110-119.

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

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Чуксина, Наталия Владимировна

Введение

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

1.1 О хороших парах вершин в реберно регулярных графах.

1.2 Некоторые свойства сильно регулярных графов.

2 О хороших парах вершин в реберно регулярных графах

2.1 Почти хорошие тройки в графах с к > 3&i.

2.2 Хорошие пары в графах с к > 3&i.

2.3 Доказательство теоремы 2.

2.4 Реберно регулярный граф с к — 17, Ъ\ — 6.

2.5 Хорошие пары в графах с к = 3&i — 1.

2.6 Графы без хороших пар.

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

3.1 Автоморфизмы графа с параметрами (210,95,40,45).

3.2 Автоморфизмы графа с параметрами (95,40,12,20).

3.3 Автоморфизмы точечного графа частичной геометрии ^(?2(4, 9)

3.4 Автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии рС?2(4, 9).

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

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

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

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

Граф Г диаметра d называется дистанционно транзитивным, если для любого г €Е {0,., с?} и для любых его вершин u,v,x,y таких, что d(u,v) = d(x,y) = i, существует автоморфизм g графа Г такой, что (u,v)g — (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 (см. [30]). В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности.

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

Через jPCmit.}mn обозначим полный n-дольный граф с долями порядков mi,.,mn. Если mi = ••• = Шп — т, то соответствующий граф обозначается через Кпхт. Если т > 2, то граф KijTn называется т-лапой. Реберный граф L(Km^n) полного многодольного графа Кт<п является кореберно регулярным графом с параметрами (тп, т + п — 2, 2). Реберный граф для Кт,п называют т х п- решеткой. Известно, что п х п- решетка является сильно регулярным графом с параметрами (п2, 2п — 2, п — 2, 2). С. Шрикханде в [32] показал, что сильно регулярный граф, имеющий параметры п х п— решетки является либо п х п- решеткой, либо графом Шрикханде при п = 4.

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

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

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

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

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

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

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

Если вершины и, w находятся на расстоянии г в Г, то через w) (соотв. Ci(u,w)) обозначим число вершин в пересечении Ti+i(u) (соотв. Г;1(г4)) с Г(и>). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин u,w и обозначается через Ъ\.

Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s 4-1 точку, каждая точка лежит на i +1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия pGa(s, t) называется обобщенным четырехугольником и обозначается GQ(s,t).

Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Точечный граф частичной геометрии pGa(s, t) сильно регулярен с параметрами v = (s -j- 1)(1 + st/a), к = s(t + 1), Л = (s — 1) + (а — 1 )i, fx — a(t + 1). Любой сильно регулярный граф с такими параметрами для некоторых а, s, t называется псевдогеометрическим графом для pGa(s,t).

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

1) изучить связные реберно регулярные графы с параметрами (v, к, Л) и k>3bi- 1;

2) найти возможные автоморфизмы сильно регулярного графа, являющегося псевдогеометрическим для 9);

3) найти возможные автоморфизмы сильно регулярного графа, в котором окрестности вершин являются точечными графами частичной геометрии р<?2(4,9).

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

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

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

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

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

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

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

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

Пусть Г — реберно регулярный граф с параметрами (г>, к, А) и Ъ\ = к—А—1. Пара вершин u,w называется хорошей (почти хорошей), если d(u,w) = 2 и fi(u, w) равно к—26i+1 (равно к—2&1+2). Тройка вершин (и, w, z) называется хорошей (почти хорошей), если w,z € Г2 (it) и n(u,w) + z) не больше

2к - 4&i + 3 (равно 2к - 4bi + 4).

В [2, предложение и лемма 1.9], доказано, что если Г — связный реберно регулярный граф диаметра 2 с параметрами (v, к, Л), где к = З&1+7 и 7 > —2, то выполняются следующие утверждения:

1) если Г содержит такую 3-коклику Д, что любые ее две вершины образуют хорошие пары, то 7 < —1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;

2) если некоторая вершина и графа Г лежит в хорошей паре, то либо 7 < Ъ\ — 6, либо &i = 1 и Г — многоугольник, либо bi — 2 и Г — граф икосаэдра или граф с к — 4 диаметра, большего 2;

3) если 7 > 0 и для некоторой вершины и подграф ^(w) содержит две вершины, образующие хорошие пары cii, то 7 < &i/2 — 2.

Уточнение утверждения (2) получено в [6]. В параграфе 2.1 доказано предложение 1 о почти хороших тройках, с помощью которого в теореме 1 получено усиление утверждения (3).

Предложение 1 Пусть Г — связный реберно регулярный граф с параметрами (v, к, А), к = 3&i + 7 и 7 > 0. Если (и, w, z) — почти хорошая тройка вершин в Г и А = [и] П [ги] П [z], то верно одно из следующих утверждений:

1) вершины w,z не смеэюны и |Д| =0;

2) вершины w, z смежны и либо г) подграф [и] П [w] П [z] является 2-кликой, 7 = 0, /i(u, w) — fi(u, z) = 61 + 2, Г2(u) П (H U \z\) = {w, z} U (И П [z]) ub 1 > 8, либо ii) подграф [и] П [w] П [z] является 3-кликой, 7 = 1, fi(u, w) = //(n, z) = b\ + 3, 61 = 3 и T — граф Клебша, либо iii) подграф [п] П [ги] П [z] является А-кликой, 7 = 1, и, w) = z) = bi + 3, bi = 5 и Г — град5 Шлефли.

Теорема 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (v,k, А) и k — 3bi + 7, 7 > 0. Если 7 > 56i/12 — 5, mo каждая вершина графа Г лежит не более чем в одной хорошей паре.

В работе А. Браувера [10] доказано, что если Г связный неполный ребер-но регулярный граф с параметрами (г?, к, А), в котором к > 3bi, то диаметр равен 2 и выполняется неравенство кЪ\ > (v — к — 1) (к — 2b\ + 1). В статье А.А. Махнева и Д.В. Падучих [2] эти результаты были уточнены и получена верхняя оценка для числа вершин связного реберно регулярного графа диаметра 2 с параметрами (v, к, А) и к = 3&i + 7, 7 > —2. В параграфах 2.5-2.6 с помощью результатов о почти хороших тройках эта оценка уточняется для графов с к = 3&i — 1. Доказана следующая теорема.

Теорема 2 Пусть Г — реберно регулярный граф с к — 3&i — 1; fi(u, w) + (i(u, z) = 2bi 4- 2 для различных w, z из Г2{и), Д = [it] П [it?] П [z]. Тогда верно одно из следующих утверждений:

1) вершины w,z не смежны и |Д| = 0;

2) Д = {а}; fi(u, w) = [i(u, z) — b\ + 1, [it] П [u>] — а1- содержит единственную вершину с, [и] П [z] — а1- содержит единственную вершину е и И U И - М С {w, z} U (М П [г]);

3) Д является 2-кокликой, [it?] — ([it] Uz1) содержит единственную вершину z* и [z] — ([it] U w1-) содержит единственную вершину w*;

4) Д является 2-кликой.

Следствие 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (i?, к, Л) и к — 36i — 1. Тогда либо граф Г является многоугольником или графом икосаэдра, либо верно одно из утверждений:

1) для некоторой вершины и в Г найдутся две вершины w, z, образуюш}ие хорошие пары с и, и либо вершины w,z смежны и v < 5&ь либо вершины w, z не смежны uv< 661 — 8/

2) в Г нет вершин, лежащих в двух хороших парах, Г содержит хорошую пару и v < 6&i — 6;

3) в Г нет хороших пар и либо г) Г не содержит почти хороших пар и v < 6&1 — б, либо (ii) Г содержит почти хорошую тройку (и, w, z), вершины u>, 0 смежны и v < 5bi + (61 — 3)/2, либо ш) Г не содероюит почти хороших троек (и, ги, z) со смежными вершинами w, z и v < 6&i — 9 + 16/(&i + 2).

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

Теорема 3 Пусть Г — связный реберно регулярный граф с параметрами к — 17 и Ъ\ = 6. Тогда v = 30, ив Г нет хороших и почти хороших пар вершин.

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

В работе А.А. Махнева [4] доказано, что связный вполне регулярный граф, окрестности вершин которого являются псевдогеометрическими графами для pG2(4,t) либо является графом Тэйлора, либо сильно регулярен с параметрами (210, 95,40,45). В главе 3 с помощью метода Г. Хигмана, приведенного в [15], исследуются возможные порядки элемента в группе автоморфизмов сильно регулярного графа, а также выяснено строение подграфов неподвижных точек автоморфизмов простых порядков сильно регулярных графов с параметрами (210,95,40,45) и (95,40,12,20). Как следствие, доказано, что точечный граф частичной геометрии р(?2(4, 9) не является вершинно симметричным. Кроме того, выяснено строение подграфа неподвижных точек сильно регулярного графа, окрестности вершин которого являются точечными графами частичной геометрии р(?2(4, 9).

Пусть Г — сильно регулярный граф, G = Aut(r), g — элемент простого порядка р из G и Q, = Fix(p). Для автоморфизма g через оц{д) обозначим число пар вершин (и, и9) таких, что d(u, и9) = г.

Основными результатами 3 главы являются теоремы 4-6.

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (210,95,40,45), д — элемент простого порядка р из Aut(r) и Q, = Fix(g). Тогда верно одно из утверждений:

1) D. — пустой граф, и либо р = 2, ai(g) — 210, либо р Е {3,5} и 15 делит ai(g), либо р = 7 и а\(д) Е {0,105,210};

2) Q является п-кликой и либо р = 19, п — 1 и а±(д) = 95, либо р = 2 и п Е {2,4,6,8,10}, либо р = 3, п Е {3,6,9} и ос\{д) делится на 15;

3) П является т-кокликой, р — 5, т Е {5,10,15,20} и ai(g) — 5т делится на 15;

4) Г2 является объединением I (Z > 2) изолированных клик порядков П1,., щ, р = 3 и щ делится на 3 для любого i Е {1,., /};

5) Г2 содержит 2-лапу up < 13.

Из теоремы следует, что ir(G) С {2,3, 5, 7,11,13,19}.

Теорема 5 Пусть Г — сильно регулярный граф с параметрами (95,40,12,20), g — элемент простого порядка р из Aut(T) и Q = Fix(g). Тогда верно одно из утверждений:

1) £1 — пустой граф и либо р = 5, cti(g) = 50 и Г имеет кликовую (у)-орбиту, либо р = 19 и о.\{д) = 38;

2) Г2 является п-кликой, р = 3 и либо п = 2 и a.i{g) сравнимо с 6 по модулю 12, либо п = 5 и а\(д) делится на 12;

3) Г2 является т-кокликой и либо г) р = 5, т = 15, аг(д) = аг(д2) = 20 или т = 10, оц(д) Е {10,70}, либо ii) р = 2, т нечетно, т <17 и ai(g) — 2т — 2 делится на 12;

4) Q содержит 2-лапу и либо г) р = 3, cvi(g) = 0 и М Е {11,17,23,29}, либо ii) р = 2, П не является кокликой, |Г — Г2| = 2t, где 27 < t < 43 или t = 24, и каждая вершина из Q смежна с вершиной из Г — £1.

С помощью этой теоремы получаем

Следствие 2 Точечный граф частичной геометрии р(?2(4, 9) не является вершинно симметричным.

Теорема 6 Пусть Г — сильно регулярный граф с параметрами (210, 95,40,45), у которого окрестности вершин являются точечными графами частичной геометрии р6?2(4,9), д — элемент простого порядка р из G = Aut(r) и Г1 = Fix(g). Тогда tt(G) С {2,3, 5, 7,19} и верно одно из утверждений:

1) Q — пустой граф и либор = 2, ot\{g) = 210, либор € {3,5} и 15 делит oil(g), либо р = 7 и OL\(g) £ {0,105,210};

2) Г2 является п-кликой и либо р = 19, п = 1 и оц{д) = 95, либо р — 3, п Е {3, 6} и а\ (д) делится на 15;

3) fi является т-кокликой, р = 5, т G {5,10} и o>i(д) — Ът делится на

15;

4) П является объединением I (I > 2) изолированных клик порядков П\,., 72/, р = 3, щ G {3,6} для любого г S {1,.,/} и < 30, если Q содержит 6-клику, и |0| < 24, если О. не содержит 6-клик;

5) Q, содержит 2-лапу, и либо г) р = 5, Q является Ъ-кокликовым расширением п-угольника, где п €Е {4, .,8}, или объединением двух изолированных Кю^о-подграфов, либо ii) р — 2, Q — половинный граф 6-куба или граф без треугольников, причем в последнем случае либо Q — регулярный граф степени 17 на 54 вершинах, либо б < |П| < 50.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Чуксина, Наталия Владимировна, Екатеринбург

1. Казарина, В.И. О реберно регулярных графах с bi = 5 /В.И. Казари-на, А.А. Махнев // Межд. конф. "Алгебра, логика и кибернетика". Тез. докл.-Иркутск, 2004.-С. 159-161.

2. Махнев, А.А. Новая оценка для числа вершин реберно регулярных графов /А.А. Махнев, Д.В. Падучих // Сиб. мат. журн.—2007—Т. 48.— С. 46-61.

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

4. Махнев А.А. О графах, окрестности вершин которых сильно регулярны с к = 2д // Матем. сборник.-2000.-Т. 191, №7.- С.89-104.

5. Махнев, А.А. О расширениях частичных геометрий, содержащих малые ^-подграфы // Дискр. анализ и исслед. операций. -1996.- Т. 3, №3.- С.71-83.

6. Махнев, А.А. О реберно регулярных графах, не содержащих хороших пар /А.А. Махнев , А.С.Омельченко // Известия Гомельского госуниверситета.- 2007.- Т. 10, №23.- С.103-118.

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

8. Махнев, А.А. О хороших парах в реберно регулярных графах /А.А. Махнев, А.А. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет, матем,- 2003.-Т.15, С.77-97.

9. Нирова М.С. О вполне регулярных графах с < 5 // Сибирские электронные математические известия. -2007.- Т. 5 С. 125-134.

10. Brouwer, A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier // Berlin etc: Springer-Verlag.- 1989.— 495 s.

11. Brouwer, A.E. Block designs/ A.E. Brouwer, H.A. Willbrink // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsevier Science. Amsterdam.- 1995 - P.349-383.

12. 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.

13. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsevier Science. Amsterdam.- 1995.- P.63-107.

14. Buekenhout, F. Finite diagram geometries extending buildings/ F. Buekenhout, P. Pasini // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout.— Elsevier Science. Amsterdam.-1995.- P. 11431255.

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

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

17. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang // Sci. Record.- 1949,- Vol.3.- P.604-613.

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

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

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

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

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

23. 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.

24. 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. 151156; 353-361.

25. Higman, D.G. Coherent configurations/ D.G. Higman // Rend. Sem. Mat.Univ. Padova.- 1970.- Vol.44.- P. 1-26.

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

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

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

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

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

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

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

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

34. Shao C. Characterization of simple ^-groups /С. Shao, W. Shi, Q. Jiang // Front. Math. China.- 2008.- V. 3.-P. 355-370.Работы автора по теме диссертации

35. Махнев, А.А. О реберно регулярных графах, в которых кажда вершина лежит не более чем в одной хорошей паре /А.А.Махнев, Н.В. Чуксина / / Алгебра и логика: Материалы международного российско-китайского семинара. Иркутск, 2007 С.77-78.

36. Махнев, А.А. О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре/А.А. Махнев, Н.В. Чуксина // Владикавказ, матем. ж.- 2008. Т. 10, Выпуск 1.- С. 53-67.

37. Махнев, А.А. О хороших парах вершин в реберно регулярных графах с к = 3bi — 1 /А.А.Махнев, Н.В.Чуксина // Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. Екатеринбург, УрО РАН.- 2008. С. 35-37.

38. Махнев, А.А. О хороших парах вершин в реберно регулярных графах с к = 3bi — 1/А.А. Махнев, Н.В. Чуксина // Труды Института математики и механики УрО РАН.- 2008.- Том 14, №4.- С. 119-134.

39. Махнев, А.А. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45)/А.А. Махнев, Н.В. Чуксина // Тезисы сообщенийVII Международной школы конференции по теории групп. Челябинск, ЮУрГУ.-2008,- С. 78-80.

40. Махнев, А.А. Об автоморфизмах сильно регулярного графа с параметрами (95,40,12,20)/А.А. Махнев, Н.В. Чуксина // Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. Екатеринбург, УрО РАН.- 2009.- С. 52-53 .

41. Чуксина,Н.В. Автоморфизмы графа с окрестностями вершин изр^'2(4,9) // Сибирские электронные математические известия 2009.- Т. 6.- С. 110-119.