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

НОСОВ Виталий Валерьевич

На праф&х рукописи /

А

1

У /

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

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

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

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

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

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

доктор физ.-мат. наук, профессор, чл.-корр. РАН МАХНЕВ А.А.

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

доктор физ.-мат. наук, профессор БАРАНСКИЙ В.А. кандидат физ.-мат. наук, доцент ЗЮЛЯРКИНА Н.Д.

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

Челябинский государственный университет.

Защита состоится 28 июня 2005г в 14.00 на заседании диссертационного совета Д 004.006 03 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики УрО РАН по адресут.Екатеринбург, ул. С.Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО

РАН.

Автореферат разослан мая 2005 г

Ученый секретарь

диссертационного совета

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

КАБАНОВ В.В.

2РРМ

то 7

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

Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [3—6, 7,16,17]. Например, класс билдингов Титса характеризует группы Лиевского типа [18]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [3].

Пусть <3 — транзитивная группа подстановок на множестве П. Если подгруппа Ор группы О, состоящая из всех подстановок, фиксирующих точку р бй, имеет г орбит, то говорят, что С? является группой ранга г. Пусть г = 3 и соответствующие 3 орбиты — это {р}, Д(р),Г(р). Тогда по группе <3 удается построить сильно регулярный граф Г, множество вершин которого

— Пи две вершины р, q смежны в Г, если р £ Д (д) [9].

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

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь —- вершины графа Г, то через ¿(а, 6) обозначим расстояние между а и Ь, а через Г, (а) - подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Гх(а) будем называть окрестностью вершины а и обозначать через [в]. Через а1 обозначим подграф, индуцированный {а} и [о].

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Граф Г назовем реберно регулярным с параметрами (р,к, А), если он содержит V вершин, регулярен степени к, и каждое его ребро аЪ лежит в А треугольниках. Граф Г - вполне регулярный граф с параметрами

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

Граф Г диаметра ё. называется дистанционно транзитивным, если для любого г € {0,.. , й} и для любых вершин и, V, х, у, таких что ¿(и, и) = й(х, у) = г, существует автоморфизм д графа Г (и, у)9 = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [16].

Если вершины и, т находятся на расстоянии г в Г, то через Ь,(и, и;) (через с,(и, ги)) обозначим число вершин в пересечении Г,+1(и) (в пересечении Г,_1(«)) с [и/]. Дистанционно регулярным графом называется граф, в котором параметры Ъг{и,т) и с,(и, и>) не зависят от вершин и, ш, а зависят только от расстояния на котором эти вершины находятся в графе Г.

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

В первой главе монографии [3] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (и, к, А), в котором к > ЗЬ] . то Г имеет диаметр 2 и V < 2к — 2.

Цель работы. В диссертации исследуются строение реберно регулярных храфов с к > 3£>1 — 1 и возможные автоморфизмы некоторых сильно регулярных графов.

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

Научная новизна. Все основные результаты диссертации являются новыми Изучено вложение "хороших пар "в реберно регулярные графы с к > 3&1 — 1. Впервые некоторые сильно регулярные графы охарактеризованы тремя параметрами (ъ,к, А). Для трех сильно регулярных графов получена информация о возможных автоморфизмах.

Теоретическая и практическая ценность. Результаты имеют теоретическую ценность.

Апробация работы. Результаты работы докладывались на Международной алгебраиче-

ской конференции, посвященной 70-летию А.И Старостина и 80-летию Н.Ф.Сесекина, на Международной алгебраической конференции, посвященной 250-летию Московского госуниверситета, на 34-й и Зб-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.

Публикации. Основные результаты опубликованы в работах [19—24J. Работы [19-20] получены в нераздельном соавторстве с Веденевым A.A., Кузнецовым А.Н., Махневым A.A. Работы [19—23] были получены в нераздельном соавторстве с Махневым A.A.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы (42 наименования). Ссылка на утверждение i.j к означает, что оно находится под номером к в параграфе j главы i.

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

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v, к, А). Тогда (см. лемму 11.1) степень вершины в любом ß-подграфе из Г не больше к—2Ь\. Поэтому для /4, = fc —2^ + 1 и любых верпгин и, ю, находящихся на расстоянии 2, выполняется неравенство ß(u,w) > ц,. Пару вершин (и, w), находящихся на расстоянии 2, назовем хорошей, если ß(u,w) = ß,.

В лемме 1.4.2 из [1] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (v, к, Л) в котором А > 2к/3 — 1, (эквивалентно к > ЗЬх), то Г имеет диаметр 2, v < 2к - 2 и выполняется неравенство kbi > (v — к — 1 )(к -I-1 — 2&i) (*).

В работе [17] доказано, что если к > 36j — 1, то либо для любой вершины и не более двух вершин из Гг(и) образуют хорошие пары с и, либо к = 3&i — 1 и Г является графом икосаэдра. Для числа вершин реберно регулярного графа диаметра 2 с к > 3&i — 1 существенно уточняется неравенство (*). Установлено, что реберно регулярный граф с параметрами треугольного графа Т{п), п — 5,6, графа Клебша или графа Шлефли совпадает с соответствующим графом.

В работе [17] изучено расположение хороших пар в реберно регулярных графах при к > 3i>! -1.

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

Теорема 1.1 Пусть Г - связный реберно регулярный граф с параметрами (ь, к,Х) и и £ Г. Тогда выполняются следующие утверждения:

(1) если к > 4&1 — 1, то Г не содержит хороших пар;

(2) если к > 361—1, то либо к — 3&1 -1, Г является многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары,, либо /г(и, т,) = /1, для не более чем двух вершин из Гг(м).

Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А, ц) = (0,2). Сильно регулярный граф с А = 0 и /г — 2 имеет параметры ((и4 + Зи2 4 4)/2, и2 + 1,0,2), где и — натуральное число, не кратное 4.

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

В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Хигмэна работы с автоморфизмами сильно регулярных графов [6] Во втором параграфе теореаико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (352,26,0,2) Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются. Автоморфизмы этого графа изучались в [19]. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (704,37,0,2). Автоморфизмы этого графа изучались в [22].

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

Теорема 2.3. Пусть Г является сильно регулярным графом с параметрами (352,26,0,2), в = Аи^Г), д — элемент простого порядка р из С? и Д = 7хх.(д). Тогда выполняется одно из следующих утверждений:

(1) р = 2 и либо А — пустой граф, 14-коклика или связный граф степени 6 на 32 вершинах, либо А имеет четыре связные компоненты, являющиеся четырехугольниками;

(2) р = 5 и А — двухвершинная клика;

(3) р = 11 и Д — пустой граф;

(4) р = 13 и Д является одновершинным графом.

Из теоремы 2.3 следует, что порядок группы автоморфизмов С графа Г с параметрами (352,26,0,2) делит 2' • 52 • 11 • 13. В частности, (3 — разрешимая группа.

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

Теорема 2.4. Пусть Г - сильно регулярный граф с параметрами (704,37,0,2), О = АШ,(Г), д — элемент простого порядка р из в и = РЬс(д). Тогда выполняется одно из следующих утверждений:

(1) р = 2 и £1 — либо пустой граф, либо объединение 10 изолированных ребер, либо вполне регулярный граф степени 5 на 32 вершинах, либо вполне регулярный граф степени 7 на 44 вершинах;

(2) р = 5 или 7 и £1 является четырехугольником;

(3) р = 11 и П — пустой граф;

(4) р = 37 и Г2 — одновершинный граф.

И.-! теоремы следует что порядок группы автоморфизмов С графа Г с параметрами (704,37,0,2 делит 2' ■ 5 • 7 • 11 • 37. В частности, С — разрешимая группа.

В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Крейна с параметрами (1600,205,0,30). Автоморфизмы этого графа изучались в [21].

Пусть сильно регулярный граф Г с параметрами (и, к, А, имеет собственные значения к, г, з. Вели графы Г и Г связны, то выполняются неравенства, называемые условиями Крейна:

(1) (г + 1)(* + г + 2гв) < (к + г)(в + I)2 и

(2) (« + 1)(А + з + 2га) < (к + в) (г + I)2.

Граф Г назовем графом Крейна, если для него достигается равенство в одном из условий Крейна (1) или (2). Сильно регулярный граф Крейна без треугольников Кге{г) имеет

параметры ((гг + 3г)2, г3 + Зг" 4- г, 0, г2 + г). Известно, что Кге(1) — граф Клебпта, Кге(2) — граф Хигмсна-Симса. Несуществование Кге(3) доказано в [4] Вопрос о существовании графов Кге(4),Кге(5) пока остается открытым.

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

Теорема 3.1. Пусть Г — граф Крейна Кте(Ь), G = Aut(r). Если д — элемент нечетного простого порядка р из G, Q = Fix(<?), то верно одно из утверждений:

(1) И — пустой граф u р = 5;

(2) либо П — одновершинный граф ир = 41, либо О является 2-кликой ир = 17;

(3) П является графом с удаленным максимальным паросонетением up — 3.

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

ЛИТЕРАТУРА

1. Зрипов С.Р., Махнев А.А., Яблонко И.П. О сильно регулярных графах без треугольников // Алгебра и линейная оптимизация. Труды межд. семинара, Екатеринбург, УрО РАН 2002, 117-121.

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

3. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag - 1989.

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

5. Brouwer A.E., Haemers W.H. The Gewirtz graph' an exercize in the theory of graph spectra // Europ. J. Comb. 1993, v. 14, 397-407.

6. Buekenhout F. Foundations of incidence geometry //Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 63 — 107.

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

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

9. Higman D. G. Finite permutation groups of rank 3. — Math. Z., 1964, v. 86, p. 145 — 156

10. Higman D. G. Primitive rank 3 groups with a prime subdegree. — Math. Z., 1966, v. 91, p. 70 — 86. 11. Higman D. G. Intersection matricies for finite permutation groups.— J. Algebra, 1967, v. 6, p. 22 - 42.

12. Higman D G On finite affine planes of rank 3. - Math. Z., 1968, v. 104, p. 147 - 149.

13. Iligman D G A survey of some questions and resalts about rank 3 permutation groups.— Actes, Cjngres Int. Math. Rome, 1970, v. 1, p. 361 — 365.

14. Higman D. G. Characterization of families of rank 3 permutation groups by the subdegrees I, II. - Arth. Math., 1970, v. 21, p. 151 - 156; 353 - 361.

15. Higman D. G. Coherent configurations. — Rend. Sem. Mat. Univ. Padova, 1970, v. 44, p. 1 -26.

16. Prager С. E , Soicher L H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.

17. Numata M. On a characterization of a class of regular graphs // Osaka J. Math. 1974, v 11, 389-400.

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

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

20. Махнев А.А., Веденев А.А.. Кузнецов А.Н., Носов В.В. О хороших парах в реберно регулярных графах // Тез. докладов международного семинара по теории групп по-свящепного 70-летию А.И. Старостина и 80-летию Н.Ф. Сесекина, Екатеринбург, 2001. С. 139-140.

21. Махнев A.A., Носов B.B. Об автоморфизмах графов с А = 0,/л = 2.//Мате- матический сборник. Том 195, №3, 2004, С. 47-68.

22. Махнев A.A., Носов В.В. Об автоморфизмах графов с А = 0, р = 2.// Проблемы теоретической и прикладной математики: труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 41-44.

23. Махнев A.A., Носов В.В. Об автоморфизмах графов Крейна без треугольников. // Международная алгебраическая конференция, посвященная 250-летию Московского университета. Тезисы докладов. М.:Изд.-во механико-математической литературы. МГУ, 2004г.С.89-91.

24. Носов В.В. Об автоморфизмах графа с параметрами (704,37,0,2) //Проблемы теоретической и прикладной математики: Труды 36-й Регион, молод, конф. Екатеринбург: УрО РАН, 2005. С 55-60

Подписано в печать 23.05.05 Формат 60x84 1/16 Бумага писчая

Плоская печать Тираж 100 экз. Заказ Вб

Ризография научно-исследовательской части ГОУ ВПО УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира 19

1

í

I

h f

Í.

/

I

»11040

РНБ Русский фонд

2006-4 14207

! л

Введение

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

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

А = 0 и /л =

2.1 Об автоморфизмах графа с параметрами (352,26,0,2).

2.2 Об автоморфизмах графа с параметрами (704,37,0,2).

3 Об автоморфизмах графа с параметрами

1600,205,0,30)

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ъ — вершины графа Г, то через с?(а, 6) обозначим расстояние между а и Ь, а через Г^(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Гх(а) будем называть окрестностью вершины а и обозначать через [а]. Через а1 обозначим подграф, индуцированный {a} U [а].

Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Число вершин в [а] П [Ь] обозначим через А(а, Ь) (д(а,Ь)), если d(a,b) = 1 (с?(а, Ь) = 2), а соответствующий подграф назовем (fi-) А-подграфом. Граф Г назовем реберно регулярным с параметрами (и, к, А), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (v, к, А, /л), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит /I вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.

Через Кти. ,5ТПп обозначим полный n-дольный граф, с долями порядков mi, ., тп. Если т\ = . = mn = т, то соответствующий граф обозначается через Кпхт. Треугольным графом Т{т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \Х\ = т и пары {а, 6}, {с, d} смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X х Y называется m х п решеткой, если \Х\ = т, |У| = п и вершины (xi,yi), (2:2, У2) смежны тогда и только тогда, когда Xi = Х2 или у\ = у2. Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (чрез Ci(u,w)) обозначим число вершин в пересечении Гi+i(u) (в пересечении rji(tt)) с [w]. Заметим, что в реберно регулярном графе с параметрами г>, к, А) значение bi (и, и;) не зависит от выбора ребра {и, w} и равно Лг — Л — 1.

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 31, 32]. Например, класс билдингов Титса характеризует группы Лиевского типа [36]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [1,15].

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

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

Граф Г диаметра d называется дистанционно транзитивным, если для любого г Е {0,., d} и для любых вершин и, v, х, у, таких что d(u, v) = d(x, у) = г, существует автоморфизм д графа Г : (u,v)9 = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [31].

Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через c;(u, w)) обозначим число вершин в пересечении Гг+1(и) (в пересечении Гг-1(^)) с [w]. Дистанционно регулярным графом называется граф, в котором параметры w) и c;(u, w) не зависят от вершин u, w, а зависят только от расстояния на котором эти вершины находятся в графе Г.

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

В диссертации исследуются строение реберно регулярных графов с к > 3&i — 1 и возможные автоморфизмы некоторых сильно регулярных графов.

Результаты работы докладывались на Международной алгебраической конференции, посвященной 70-летию А.И.Старостина и 80-летию Н.Ф.Сесекина, на Международной алгебраической конференции, посвященной 250-летию Московского госуниверситета, на 34-й и 36-й Региональных молодежных конференциях ИММ УрО РАН, на алгебраических семинарах Института математики и механики УрО РАН.

Диссертация состоит из введения, трех глав и списка литературы (43 наименования).

1. Баннаи Э., Ито. Т. Алгебраическая комбинаторика. Схемы отношений: Пер. с англ.-М.: Мир, 1987.-375 е., ил.

2. Браувер А.Е. Ван Линт Дж. Сильно регулярные графы.//Кибернетический сборник: Вып. 23. Сборник статей: Пер. с англ. -М.: Мир, 1987. С. 160-186.

3. Донских Е.Н., Махнев А.А. О реберно регулярных графах с bi = 4 // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2002, 18-19.

4. Зрипов С.Р., Махнев А.А., Яблонко И.П. О сильно регулярных графах без треугольников // Алгебра и линейная оптимизация. Труды межд. семинара, Екатеринбург, УрО РАН 2002, 117-121.

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

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

7. Махнев А. А. Реберно регулярные графы, в которых каждое ребро лежит в большом числе треугольников // Дискр. анализ и исслед. операций 1995, т. 2, №4, 42-53.

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

9. Махнев А.А., Дрожевский А.В., Ищенко П.В., Паметов П.Ю. О почти хороших парах вершин в реберно регулярных графах // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2003, 25-26.

10. Махнев А.А., Минакова И.М. Об одном классе реберно регулярных графов // Известия Гомельского госуниверситета, Вопросы алгебры 2000, т. 3 (16), 145-154.

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

12. Хестенс М.Д., Хигмэн Д.Г. Группы ранга 3 и сильно регулярные графы.// Кибернетический сборник: Новая серия, вып. 23. Сборник статей: Пер с англ.-М.: Мир, 1986. С.131-152.

13. Холл. М. Комбинаторика. М:-Изд-во"Мир", 1970, 424 с.

14. Юбо К.Сильно регулярные графы.//Кибернетический сборник: Вып. 24. Сборник статей: М.: Мир, 1987. С. 160-186.

15. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag 1989.

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

17. Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra // Europ. J. Comb. 1993, v. 14, 397-407.

18. Buekenhout F. Foundations of incidence geometry.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 63 107.

19. Buekenhout F, Cameron P. Projective and affine geometry over division rings.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout. Elsever Science, Amsterdam, 1995, P. 27 — 63.

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

21. Cameron P. Permutation Groups, London Math. Soc. Student Texts 45, Cambridge Univ. Press. 1999.

22. Cameron P., Van Lint J. Designs, Graphs, Codes and their Links. London Math. Soc. Student Texts 22, 1981. Cambr. Univ. Press. 240 pp.

23. Cohen A.M. Point line spaces related to buildings.//Handbook of incidencegeometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995,P. 647-739.

24. Higman D. G. Finite permutation groups of rank 3. — Math. Z., 1964, v. 86, p. 145 156.

25. Higman D. G. Primitive rank 3 groups with a prime subdegree. — Math. Z., 1966, v. 91, p. 70 86.

26. Higman D. G. Intersection matricies for finite permutation groups.— J. Algebra, 1967, v. 6, p. 22 42.

27. Higman D. G. On finite affine planes of rank 3. — Math. Z., 1968, v. 104, p. 147 149.

28. Higman D. G. A survey of some questions and resalts about rank 3 permutation groups.— Actes, Cjngres Int. Math. Rome, 1970, v. 1, p. 361 — 365.

29. Higman D. G. Characterization of families of rank 3 permutation groups by the subdegrees I, II,- Arth. Math., 1970, v. 21, p. 151 156; 353 - 361.

30. Higman D. G. Coherent configurations. — Rend. Sem. Mat. Univ. Padova, 1970, v. 44, p. 1 26.

31. Prager С. E., Soicher L. H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.

32. Numata M. On a characterization of a class of regular graphs // Osaka J. Math. 1974, v. 11, 389-400.

33. Nakagawa N. On strongly regular graphs with parameters (к, 0, 2) and their antipodal double cover // Hokkaido Math. Soc. 2001, v. 30, 431-450.

34. Thas J. A. Generalized polygons.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 383— 433.

35. Thas J. A. Projective geometry over a finite field.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995, P. 295-349.

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

37. Willbrink H. A., Brouwer A. E. A (57, 14, 1) strongly regular graph does not exist// Proc. Kon. Nederl. Akad. Ser. A, 1983. Vol. 45, N 1. P. 117-121.РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

39. Махнев А.А., Веденев А.А. Кузнецов А.Н., Носов В.В. О хороших парах в реберно регулярных графах // Тез. докладов международного семинара по теории групп по-священного 70-летию А.И. Старостина и 80-летию Н.Ф. Сесекина, Екатеринбург, 2001. С. 139-140.

40. Махнев А.А., Носов В.В. Об автоморфизмах графов с Л = 0, д = 2.//Математический сборник. Том 195, №3, 2004, С. 47-68.

41. Махнев А.А., Носов В.В. Об автоморфизмах графов с А = 0,д = 2.// Проблемы теоретической и прикладной математики: труды 34-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2003. С. 41-44.

42. Махнев А.А., Носов В.В. Об автоморфизмах графов Крейна без треугольников. // Международная алгебраическая конференция, посвященная 250-летию Московского университета. Тезисы докладов. М.:Изд.-во механико-математической литературы. МГУ, 2004г.С.89-91.

43. Носов В.В. Об автоморфизмах графа с параметрами (704, 37,0,2) //Проблемы теоретической и прикладной математики: Труды 36-й Регион, молод, конф. Екатеринбург: УрО РАН, 2005. С 55-60.