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

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

ТКАЧЕВА Ирина Михайловна

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

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

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

Уральский государственный педагогический университет.

Защита состоится 28 сентября 2004 г. в 15 ч. 00 м. на заседании диссертационного совета Д. 00400603 по защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики УрО РАН по адресу: г. Екатеринбург, ул. С.Ковалевской, 16.

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

Автореферат разослан 20 августа 2004 г.

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

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

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

КАБАНОВ В.В.

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

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

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

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [9—12, 14, 23, 24]. Например, класс билдингов Титса характеризует группы Лиевского типа [25]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [8].

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

3 гос. национальная

библиотека

регулярный граф Г, множество вершин которого — Пи две вершины р, д смежны в Г, если р € Д(д) [7].

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

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

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

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

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

Цель работы. В диссертации исследуются строение реберно регулярных графов с к > ЗЬх — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Аи/х.

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

вания).

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (и, А, А). Тогда (см. лемму 1.1.1) степень вершины в любом ^-подграфе из Г не больше к — 2Ьх-Поэтому для ц* — к — 26;+1 и любых вершин и, го, находящихся на расстоянии 2, выполняется неравенство ц(и, и») > Пару несмежных вершин («, но) назовем хорошей, если /¿(и,ги) = ц,.

В следствии из статьи А. А. Махнева [2] доказано, что если Г - связный реберно регулярный граф с параметрами (у, к, А), в котором ЗА > 2к — 5, то либо Г -многоугольник или граф икосаэдра, либо к = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2к + 4 вершинами.

В параграфе 1.1. данной работы уточняется строение графа, удовлетворяющего условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно регулярных графах.

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

Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра 2 с параметрами (у, к,Х), в котором ЗА > 2к—5 и2&+1 < V. Тогда Г - пятиугольник, 3x3 решетка или треугольный граф Т(7).

Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами (ь, к, А), в котором ЗА > 2к — 5. Тогда либо (к, А) = (4,1) о диаметр Г больше 2, либо Г - многоугольник, граф икосаэдра, 3x3 решетка или треугольный граф Т(7), либо Г - граф диаметра 2 с не более чем 2к вершинами.

Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (и, к, А) и <1 € Г. Если к > 3¿1 — 2, то либо к = — 1, Г является многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары, либо для любой вершины й из Г пары {¿, ги,) являются

хорошими для не более чем трех вершин и;,- из Гг(с().

Случай к > 3&1 — 1 рассмотрен в работе [3].

Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А, р) = (1,2). Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров А и ц имеют-жестко заданное строение. Так подграф неподвижных I .. автоморфизма графа Мура сам является графом Му-

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

В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Д.Хигмана работы с автоморфизмами сильно регулярных графов [13]. Во втором параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (99,14,1,2). Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются, В конце параграфа 2.2 работы найдено возможное строение группы С автоморфизмов графа с параметрами (99,14,1,2) при условии, что эта группа содержит инволюцию. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (243,22,1,2).

В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (115,18,1,3), если группа автоморфизмов этого графа содержит элемент порядка 3.

Пусть Г является сильно регулярным графом с параметрами (и, £,Л,[а) и <7 = АиЬ(Г) — группа его автоморфизмов. Для Хсб через РЬс(Х) обозначим инду-

цированный подграф на множестве вершин графа Г неподвижных относительно

Отметим далее некоторые утверждения, верные для графов с параметрами (ь, к, 1,2). Так как Г — сильно регулярный граф, то А: > 4. При к — 4 Г имеет параметры (9,4,1,2). Этим параметрам соответствует единственный граф, а именно, 3 х 3-решетка.[1]. В случае А; > 4, используя равенство (А —/*)2+4(к —/л) = п2, получим п = 2и + 1, к = и2 + и + 2, п - т = и а —тп = — и — 1. По условию целочисленности для сильно регулярных графов [8] имеем цп = 2(2и + 1) делит (т—1)к(к+т) = и(и2+и+2)(и2+2и+3). Поэтому 2и+1 делит 63, и и = 1,3,4,10 или 31. При и = 1 снова возникает 3 х 3-решетка. При и — 3 получается граф с параметрами (99,14,1,2), автоморфизмы которого изучались в работе [4]. При и = 4 получается граф с параметрами (243,22,1,2), автоморфизмы которого изу-

В третьей главе работы рассматривается сильно регулярный граф с парамет-

Доказательство теорем второй и третьей главы опирается на метод Дональда Хигмена работы с автоморфизмами сильно регулярного графа, изложенный в третьей главе монографии Камерона [13]. При этом сильно регулярный граф Г на V вершинах с собственными значениями к, г, в рассматривается как симметричная схема отношений (X, {До, Л2}), где X — множество вершин графа Г, где До — отношение равенства на вершинах графа Г, Д1 — отношение смежности в Г и йг — отношение смежности в дополнительном графе Г.

Если Р и С? — первая и вторая матрицы собственных значений схемы, то

Р =

1

А; г 5

V — к— 1 -г — 1 —я — 1

и РС} = (¿Р = VI. При этом кратности 1, /, д собственных значений к, г, 5 графа Г образуют первый столбец матрицы (¿.

Подстановочное представление группы б = АЫ(Т) на вершинах графа Г обыч-

ным образом дает матричное представление ф группы <3 в Ст£(г, С). Пространство С" является ортогональной прямой суммой собственных ^(С7)-инвариантных подпространств И^ матрицы смежности графа Г. Пусть Xi ~~характер

представления Тогда для любого д € С получим

2

х,(д) = V1 £ <2ьч(д), ]=0

где а,(з) — число точек х из X таких, что (х,х3) € Щ. Заметим, что значения характеров являются целыми алгебраическими числами, а правая часть данной формулы — число рациональное, поэтому х«(з) является целым числом.

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

Теорема 2.1. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), (7 = Аи(;(Г). Если д — элемент простого порядка из С?, Д = Р1х(д), то выполняется одно из утверждений:

(1) Д — одновершинный граф и\д\ = 2 или 7;

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

(£) Д — треугольник и |<?| = 3.

В частности, порядок группы автоморфизмов сильно регулярного графа с параметрами (99,14,1,2) делит 2 • З3 • 7 • 11.

Следствие 2.1. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), в = АиЦГ). Если й содержит инволюцию то выполняется одно из утверждений:

(1) |С| делится на 7 и делит 42, причем [0(6?)',*] = 1 ив случае = 42 подгруппа О (С) неабелева.

(2) |(7| делит 6.

Теорема 2.2. Пусть Г является сильно регулярным графом с параметрами (243,22,1,2), в = Аи^Г). Еслир — элемент простого порядка из С, А — Р1х(р), то выполняется одно из утверждений:

(1) |р| = 2, |Д| = 9 и каждая связная компонента графа Д является одновершинным графом, треугольником или 3x3 решеткой;

(2) \р\ = 3, Д является пустым графом или 3x3 решеткой;

(3) |р| = 5, Д является треугольником;

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

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

Теорема 3.1. Если Г является сильно регулярным графом с параметрами (115,18,1,3), то порядок группы автоморфизмов графа Г делит число 2а3^5 • 23.

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

ЛИТЕРАТУРА

1. Махнев A.A. Об одном классе графов без 3-лап // Матем. заметки 1998, т. 63, №3, 407-413.

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

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

4. Махнев A.A., Минакова И.М. Об автоморфизмах графов с А = 1 — 2.//Проблемы теоретической и прикладной математики: Труды 34-й Регион, молод. конф. Екатеринбург: УрО РАН, 2003. С 38-41.

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

6. Ткачева (Минакова) И. М. Об автоморфизмах графов с параметрами (243,22,1,2) //Проблемы теоретической и прикладной математики: Труды 35-й Регион, молод, конф. Екатеринбург: УрО РАН, 2004. С 51-59.

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

8. Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: Springer-Verlag - 1989.

9. Brouwer A. E., Willbrink H. A. Block designs. //Handbook of incidence geometry: buildings and foundations/F. Buekenhout. Elsever Science, Amsterdam, 1995, P. 34&383.

10. Buekenhout F. Foundations of incidence geometry.//

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

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

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

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

14. Cohen A.M. Point line spaces related to buildings.//Handbook of incidence geometry: buildings and foundations/F. Buekenhout.— Elsever Science, Amsterdam, 1995,R 647-739.

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

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

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

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

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

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

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

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

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

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

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

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

1. Кабанов В.В., Ткачева (Минакова) И. М. Об автоморфизмах графов с параметрами

(115,18,1,3) //Проблемы теоретической и прикладной математики: Труды 35-й Регион, молод, конф. Екатеринбург: УрО РАН, 2004. С 30-32.

2. Махнев А.А., Минакова И.М. Об автоморфизмах графов с

Л = 1Д = 2.//Дискретная математика: М., 2004, т.16, вып.1, С 95-104.

3. Махнев А.А., Минакова И.М. Об автоморфизмах графов с параметрами

1 5 571

(99,14,1,2).// Межд. сем. по теории групп: Тезисы докл.: Екатеринбург, 2001, С 141-142.

4. Махнев А.А., Минакова И.М. Об автоморфизмах графов с А = 1,/.4 = 2.//Проблемы теоретической и прикладной математики: Труды 34-й Регион, молод, конф. Екатеринбург: УрО РАН, 2003. С 38-41.

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

6. Махнев А.А., Минакова И.М. Об одном классе реберно регулярных графов // Тез. докл. Межд. алгебр, сем., посвященного 70-лнтию семинараЮ основанного О.Ю. Шмидтом- М.,2000, с. 31-32.

7. Махнев А.А., Минакова И.М. О хороших парах вершин в реберно регулярных графах с к > 3Ь — 2) //Алгебра, и линейная оптимизация: Труды межд. семинара, поев. 90-летию со дня рожд. С.Н. Черникова, 3—5 июня 2002 г.: Екатеринбург, 2002. С 172-175.

8. Ткачева (Минакова) И. М. Об автоморфизмах графов с параметрами (243,22,1,2) //Проблемы теоретической и прикладной математики: Труды 35-й Регион, молод, конф. Екатеринбург: УрО РАН, 2004. С 51-59.

Подписано в печать 28.06.04 Формат 60x84 1/16 Бумага писчая Плоская печать Тираж 75 Заказ 86

Ризография НИЧ ГОУ ВПО УГТУ-УПИ

620002 г. Екатеринбург, ул. Мира 19

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

1.1 О реберно регулярных графах с А; > Sbi —

1.2 О хороших парах в графах с А: > 3bi —

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

2.2 Об автоморфизмах графа с параметрами (99,14,1,2)

2.3 Об автоморфизмах графа с параметрами (243,22,1,2)

3 Об автоморфизмах графа с параметрами (115,18,1,3)

Мы рассматриваем неориентированные графы без петель и кратных ребер.Если а,Ь — вершины графа Г, то через d{a, b) обозначим расстояние между а и 6, а через Гг(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф ^i{a) будем называть окрестностью вершины а и обозначать через [а]. Через а^ обозначим подграф, индуцированный {а} U [а].Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Граф Г назовем реберно регулярным с параметрами (г;,/г, Л), если он содержит V вершин, регулярен степени к, и каждое его ребро аЬ лежит в Л треугольниках. Граф Г — вполне регулярный граф с параметрами {v, к, Л, /л), если он реберно регулярен с соответствующими параметрами и [а]П[6] содержит fi вершин для любых двух вершин а, 6, находяш,ихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 30, 31J. Например, класс билдингов Титса характеризует группы Лиевского типа [32]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [14].Пусть G — транзитивная группа подстановок на множестве Q. Если подгруппа Gp группы G, состоящая из всех подстановок, ([фиксирующих точку р Е Q, имеет г орбит, то говорят, что G является группой ранга г. Пусть г = 3 и соответствуюш,ие 3 орбиты — это {р}, А(р), Г{р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого — ^ и две вершины p,q смежны в Г, если р G А(5) [13].Д.Хигмэн [21 — 27] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин, так и на множестве ребер. Такие графы являются дистанционно транзитивными графами диаметра 2.Граф Г диаметра d называется дистанционно транзитивным, если для любого i G {О, .,.,с?} и для любых вершин u,v,x,y, таких что d{u,v) = d{x,y) = i, существует автоморфизм д графа Г : {u^vy — {х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [28].Если вершины u,w находятся на расстоянии г в Г, то через bi{u,w) (через Ci{u,w)) обозначим число вершин в пересечении Ti+i^u) (ri_i(w)) с [w].Дистанционно регулярным графом называется граф, в котором параметры bi{u,w) и Ci{u,w)) не зависят от вершин u,v, а зависят только от расстояния на котором эти вершины находятся в графе Г. Поскольку каждый дистанционно регулярный граф является вполне ре-' гулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.В первой главе монографии [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (г;, А;, Л), в котором к > Sbi, то Г имеет диаметр 2 и г; < 2А; — 2.Цель работы. В диссертации исследуются строение реберно регулярных графов с А; > 36i — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Л и /х. ^ Диссертация состоит из введения, трех глав и списка литературы (33 наименования).В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v, А;, Л). Тогда (см. лемму 1.1.1) степень вершины в любом /i-подграфе из Г не больше к — 26i. Поэтому для /u* = к — 2Ь\ + 1 и любых вершин и, ги, находящихся на расстоянии 2, выполняется неравенство ii{u^w) > /i*. Пару несмежных вершин {u,w) назовем хорошей, если ^(w, ги) =//*.В следствии из статьи А. А. Махнева [4] доказано, что если Г - связный реберно регулярный граф с параметрами {v, /г, Л), в котором ЗЛ > 2А; — 5, то либо Г - многоугольник или граф икосаэдра, либо А; = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с пе более чем 2fc + 4 вершинами.В параграфе 1.1. данной работы уточняется строение графа, удовлетворяюш,его условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно регулярных графах.Следующие результаты являются основными в главе 1.Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра 2 с параметрами {v,k,X), в котором 3\ > 2к — 5 и 2к -\- 1 < v. Тогда Г • пятиугольник, 3 x 3 решетка или т^реугольный граф Т(7).Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами {v, /г, Л), в котором ЗЛ > 2к — 5. Тогда либо {к, Л) = (4,1) и диамет,р Г больше 2, либо Г - многоугольник, граф икосаэдра, 3 x 3 решетка или треугольный граф Т{7), либо Г - граф диаметра 2 с не более чем 2к вершинами.Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (v^k, X) и d Е. Г. Если к > 36i — 2, то либо к = 36i — 1, Г является многоугольником или графом икосаэдра и любые две вершины, находяш/аеся на расстоянии 2, образуют хорошие пары, либо для любой вершины d из Г пары {d,Wi) являются хорошими{для1не более чем трех\вершин wi из T2{d).Случай к > 3bi — 1 рассмотрен в работе [6].Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л,д) = (1>2).Подграфы неподви:жных точек автоморфизмов сильно регулярного графа с малыми значениями параметров X и fj, имеют жестко заданное строение. Так подграф неподвижного множества автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [10]). Хорошо известно (предложение 1.1.2 [14]), что сильный граф с /л > 2 сильно регулярен. Поэтому подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с тах{Л, fi} < 2 сильно регулярны с этими же параметрами или являются кликами.В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Д.Хигмана работы с автоморфизмами сильно регулярных графов [19]. Во втором параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (99,14,1,2). Затем с помои1,ью теории характеров конечных групп полученные результаты существенно уточняются. В конце параграфа 2.2 работы найдено возможное строение группы G автоморфизмов графа с параметрами (99,14,1,2) при условии, что эта группа содержит инволюцию. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (243,22,1,2).В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (115,18,1,3), если группа автоморфизмов этого графа содержит элемент порядка 3.Пусть Г является сильно регулярным графом с параметрами (f,A;,A,nx) и G = Aut(r) — группа его автоморфизмов. Для X G G через Fix(X) обозначим индуцированный подграф на множестве вершин графа Г неподвижных относительно любого автоморфизма из X.В третьей главе работы рассматривается сильно регулярный граф с параметрами (г;, А;, 1,3).Доказательство теорем второй и третьей главы опирается на метод Дональда Хигмена работы с автоморфизмами сильно регулярного графа, изложенный в третьей главе монографии Камерона [19]. При этом сильно регулярный граф Г на v вершинах с собственными значениями к, г, s рассматривается как симметричная схема отношений {X, {RQ, R\, -Дг}), где X — множество вершин графа Г, RQ — отношение равенства на вершинах графа Г, Ri — отношение смежности в Г и i?2 — отношение смежности в дополнительном графе Г. Подстановочное представление группы G = Aut{r) на вершинах графа Г обычным образом дает матричное представление 'ф группы G в GL(v, С).Пространство С" является ортогональной прямой суммой собственных Jp{G)инвариантных подпространств WQ Ф Wi 0 W2 матрицы смежности графа Г. Пусть Xi характер представления ^Wi- Тогда для любого д £ G получим j=0 где oti{g) — число точек х из X таких, что (а:, х^) G Ri- Заметим, что значения характеров являются целыми алгебраическими числами, а правая часть данной формулы — число рациональное, поэтому Хг(р) является целым числом.В частности, порядок группы автоморфизмов сильно регулярного графа с параметрами (99,14,1, 2) делит 2 • 3^ • 7 • 11.Основным результатом главы 3 является следующая теорема: Теорема 3.1. Если Г является сильно регулярным графом с параметрами (115,18,1,3), то порядок группы авт,оморфизмов графа Г делит число 2"3^5 • 23.Автор выражает глубокую признательность своим научным руководителям профессору А.А. Махневу и д.ф.-м.н В.В. Каба1юву за постановку задачи и постоянное внимание.1 Хоро1Пие пары в реберно регулярных графах Мы рассматриваем неориентированные графы без петель и кратных ребер.Если а,Ь- вершины графа Г, то через d{a, b) обозначается расстояние между а и 6, а через Гг(а) - подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии i от вершины а. Подграф Ti{a) называется окрестностью вершины а и обозначается через [а]. Через а-"- обозначается подграф, являющийся шаром радиуса 1 с центром а.Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами {v,k,X), если Г содержит v вершин, является регулярным степени fc, и каждое ребро в Г лежит в А треугольниках. Граф Г называется вполне регулярным графом с параметрами {v,k,X,/j,), если Г реберно регулярен и подграф [а] П [6] содержит /х вершин в случае d{a, b) = 2.Вполне регулярный граф диаметра 2 называется сильно регулярным графом.Число вершин в [а]П[6] обозначим через Л(а, 6) (через ^л(а,6)), если d{a, 6) = 1 (если d{a,b) = 2), а соответствующий подграф назовем (/х-) Л-подграфом.Если вершины и, w находятся па расстоянии г в Г, то через bi{u, w) {с{{и, w)) обозначим число вершин в пересечении Гг+1(и) (rt_i(it)) с [w]. Заметим, что в реберно регулярном гра(|)е с параметрами {v,k,X) значение bi{u,w) не зависит от выбора ребра uw и равно к — X — 1.В следствии из [2] доказано, что если Г - связный реберно регулярный граф с параметрами {v, к,Х), в котором ЗХ>2к — 5, то либо Г - многоугольник или граф икосаэдра, либо fc = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2А; + 4 вершинами.В лемме 1.4.2 из [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами {v,k,X), в котором Л > 2к/3 — 1, (эквивалентно к > 36i), то Г имеет диаметр 2, г; < 2А; —2 и выполняется неравенство (*) kbi> {v-k- 1){к -М - 2bi).Пусть Г — реберно регулярный граф с параметрами {v,k,X). Тогда (см. лемму 1.1.1) степень вершины в любом /i-подграфе из Г не больше к — 2bi.Поэтому для )U* = А;—26i-|-l и любых вершин и, w, находяш,ихся на расстоянии 2, выполняется неравенство /х(и,гу) > //*. Пару несмежных вершин {u,w) назовем хорошей, если ц{и,ги) = fj,^.В параграфе 1.1. данной работы уточняется строение графа, удовлетворяюш,его условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно рсгуляр1н>1х графах.Во втором параграфе этой главы используется следуюш,ее обозначите. Если ж, у - различные вершины графа Г, то через Лх,у обозначается подграф Г - (x-^Uy-^).

1. Донских E.H., Махнев A.A. О реберно регулярных графах с Ь\ = 4 // Проблемы теор. и приклад, матем. Труды регион, молод, конф. Екатеринбург 2002, 18-19.

2. Махнев A.A. Об одном классе графов без 3-лап // Матем. заметки 1998, т. 63, №3, 407-413.

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

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

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

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

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

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

9. Махнев A.A., Минакова И.М. Об автоморфизмах графов с А = 1,// = 2.//Дискретная математика: М., 2004, т.16, вып.1, С 95-104.

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

11. Ткачева И. М. Об автоморфизмах графов с параметрами (243,22,1,2) //Проблемы теоретической и прикладной математики: Труды 35-й Регион.молод, конф. Екатеринбург: УрО РАН, 2004. С 51-59.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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