Комбинаторно симметричные графы и их автоморфизмы

Казарина, Вероника Игоревна

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

Казарина, Вероника Игоревна АВТОР

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

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

2006 ГОД ЗАЩИТЫ

01.01.06 КОД ВАК РФ

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

Автореферат диссертации на тему "Комбинаторно симметричные графы и их автоморфизмы"

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

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

ё/Ь^ос

КАЗАРИНА Вероника Игоревна

КОМБИНАТОРНО СИММЕТРИЧНЫЕ ГРАФЫ И ИХ АВТОМОРФИЗМЫ

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

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

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

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

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

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

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

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

доктор физико-математических наук, профессор БАРАНСКИЙ Виталий Анатольевич

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

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

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

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

Автореферат разослан 4 мая 2006 года

Ученый секретарь диссертационного совета, доктор физ.-мат. наук

'Г002

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

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

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

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

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

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах. Пусть L(K„) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (("),2(п — 2),п — 2,4^. В работах 1959-60 годов JI. Чанг [14] и А. Хоффман ([23], [24]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 19-19 году [13].

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

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

РОС. НАЦИОНАЛЬНАЯ 3 БИБЛИОТЕКА

С-*Ве»ербур» ОЭ

графов Т{п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх-2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

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

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

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

Граф Г называется реберно регулярным графом с параметрами (ь, к, А), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в А треугольниках. Положим &1 = к — А — 1.

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

Сильно регулярный граф с параметрами (4/х + 1,2/1, ц — называется графом в половинном случае.

Графом Пэли называется граф, вершинами которого являются элементы конечного поля где д сравнимо с 1 по модулю 4, и две вершины смежны, если разность соответствующих элементов поля является ненулевым квадратом.

Граф Г называется сильным с параметрами (А, р), если каждое ребро из Г лежит точно в А треугольниках и подграф [а] П [6] содержит р. вершин в случае <*(а,6) = 2.

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

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

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

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

Частичным четырехугольником PQ(s, t, р) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит 8 + 1 точку, каждая точка лежит на I + 1 прямой (две прямые пересекаются не более, чем по одной точке), для любых двух несмежных вершин точечного графа пересечение их окрестностей содержит точно р. вершин и для любой точки о, не лежащей на прямой Ь, найдется не более одной прямой, проходящей через а

и пересекающей Ь.

Множество вертпин графа М2(п), отвечающего аффинной плоскости -к = (X, С) порядка п, совпадает с объединением множества точек X и множества прямых С, причем подграф X является кокликой, две прямые смежны, если они параллельны, и точка смежна с прямой, только если она принадлежит этой прямой. Граф MZ(n) имеет п(2п +1) вершин, является кореберно регулярным с ц = 1, Х(а, Ь) = 0, если одна из вершин а,Ь — точка, а другая — содержащая эту точку прямая, Л (а, Ъ) — п — 2, если а и Ь — параллельные прямые.

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

1) Исследовать вполне регулярные локально С(}{8, £) графы с сильно регулярными /¿-подграфами.

2) Изучить связные реберно регулярные графы с параметрами (у,к,Х) и &1 = 5.

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

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

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

1. Исследованы вполне регулярные локально С(2(в, () графы, в которых каждый ¿¿-подграф изоморфен известному сильно регулярному графу Д.

2. Классифицированы связные реберно регулярные графов с 61 = 5 с одним из дополнительных условий: граф сильно регулярен или к > 14.

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

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

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

Международной конференции, посвященной 75-летию со дня рождения проф. А.И. Кокорина (Иркутск, 2004 г.);

VI Международной конференции, посвященной 100-летию Н.Г. Чудакова (Саратов, 2004 г.);

Международной алгебраической конференции, посвященной 100-летию со дня рождения П.Г. Канторовича и 70-летию Л.Н. Шеврина (Екатеринбург, 2005 г.);

36-й и 37-й Региональных молодежных конференциях ИММ УрО РАН (Екаг теринбург, 2005-2006 гг.);

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

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

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

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

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются связные локально GQ(s, i) графы, в которых р-подграфы являются известными сильно регулярными графами.

Если регулярный граф степени к диаметра d имеет v вершин, то выполняется неравенство: v < 1 + к + к(к — 1) + ... 4- к(к — 1)й-1. Графы, для которых это нестрогое неравенство превращается в равенство, называются графами Мура. Простейший пример графа Мура представляет (2d 4- 1)-угольник. Р. Даме-релл [15] доказал, что граф Мура степени к > 3 имеет диаметр 2. В этом случае V = къ + 1, граф сильно регулярен с А = 0 и /х — 1, а степень к равна 3 (граф Петерсена), 7 (граф Хоффмана-Синглтона) или 57. Существование графа Мура степени к = 57 неизвестно.

Граф Клебша определен на множестве векторов 4-мерного линейного пространства V над полем из двух элементов, причем два вектора смежны, если расстояние Хемминга между ними равно 1 или 4. Это единственный сильно регулярный граф с параметрами (16,5,0,2). Графы Гевиртца, Хигмана-Симса и Маклафлина - это графы ранга 3 групп L3(4), Хигмана-Симса и Маклафлина на 56, 100 и 275 вершинах соответственно.

Пусть Л — класс графов, элементами которого являются Kn¡n, графы Мура, графы с параметрами (100,22,0,6), (77,16,0,4), (16,5,0,2), (56,10,0,2). Известные в настоящее время сильно регулярные графы с Л = 0 принадлежат Л.

Заметим, что вполне регулярные локально GQ{4,2) графы классифицированы в [б]. В работе [1| описаны связные локально GQ(3,t) графы.

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

Теорема 1 Пусть Г - вполне регулярный локально GQ(s, t) граф, в котором каждый ¡i-подграф изоморфен известному сильно регулярному графу Д € Л . Тогда выполняется одно из следующих утверждений:

(1) Д = Kt+M+1 и t + 1 делит s^s2 - 1);

(2) Д — граф Петерсена и Г — единственный локально GQ(2,2) граф с параметрами (28,15,6,10);

(3) Д - граф Хофмана-Синглтона, t = 6 и я = 9,14,15,24,29 или 30;

(4) Д - граф Клебша, t = 4 и s = 2,4,6,8,11,12 или 16;

(5) Д - граф Гевиртца, t = 9 и в = 3,7,27,31 или 63;

(6) Д - граф с параметрами (77,16,0,4), t = 15 и s = 21,41,55, 153 или 195;

(7) Д - граф Хигмана-Симса, i = 21 ti s = 19,24,34,35,39,45,49, 69,84,89,99,105,115,119,144,159,175,189,199,210,214,259,294,309, 339,364,375,399,419 или 420.

Следствие 1 Пусть Г — сильно регулярный локально GQ(s, t) граф, в котором каждый ц-подграф изоморфен известному сильно регулярному графу Д. Тогда выполняется одно из следующих утверждений:

(1) Д = Kt+i,t+i и либо s = 1 и Г = K3x(t+i), либо s — 4,t = 1 м Г — частное графа Джонсона J(10,5), либо з = t = 1,2,3,8 или 13;

(2) Д — граф Петерсена и Г является единственным локально GQ(2,2) графом с параметрами (28,15,6,10);

(3) Д — граф Гевиртца «Г — граф Маклафлина.

Известно существование и единственность сильно регулярных локально GQ{t, t) графов с ^.-подграфами, изоморфными Äj+i.t+i для t = 1 (Т — частное графа Джонсона .7(10,5)), t = 2 (Г единственный локально GQ(2,2) граф с параметрами (28,15,6,10)) и t = 3 (Г - граф ранга 3 для группы 2) с параметрами (176,40,12,8)).

Во второй главе работы рассматривается реберно регулярный граф с паг раметрами (v, к, А). В монографии А. Броувера, А. Коэна и А- Ноймайера [7j доказано, что связный реберно регулярный граф с &i = 1 является многоугольником или полным многодольным с долями порядка 2. A.A. Махневым в [3] получено описание реберно регулярных графов с 6i < 3, а также bi = 4, к > 10. В данной главе классифицированы связные реберно регулярные графы с bj = 5 с одним из дополнительных условий: граф сильно регулярен или к > 14.

Через Ф обозначим граф, множество вершин которого разбивается тремя /¿-замкнутыми К4Х2 подграфами Фь #2 и Ф3, у которого смежные вершины c,d из Фз смежны с вершинами ai,..., 04 из Ф1 и с вершинами bi,..., 64 из Ф2, а смежные вершины е, / из Ф3 — {с, d, с*, d*} смежны с вершинами ai, 02, а\, aj и с вершинами &i,¿>2,63,64, где для х е Ф, вершина х* является антиподом х в Ф,, можно считать, что <Zi смежна с bitb3, 64, а2 смежна с b?, 64, Ь\, Ь|, аз смежна с Щ, 64, <24 смежна с 6*, 62, &з. К-

Если Г) - граф диаметра, большего 2, то fi2 — граф на множестве вершин графа О, в котором две вершины смежны тогда и только тогда, когда они наг ходятся на расстоянии 2 в П.

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

Теорема 2 Пусть Г — связный реберно регулярный граф с параметрами (v, к, А) и bi = 5. Тогда выполняются следующие утверждения:

(1) если Г сильно регулярен, то он является одним из следующих графов: полный многодельный граф Кгхъ(г > 2), 6 х 6 решетка, граф Шлефли, треугольный граф Т(8) или один из трех графов Чанга;

(2) если к > 14, то либо Г сильно регулярен, либо верно одно из утверждений:

(») граф Г изоморфен графу Ф; »

(и) Г является графом Пг, где П — граф Клейна (единственный дистанционно регулярный локально семиугольный граф диаметра 3 на 24 вершинах, являющийся Ъ-накрытием 8-клики).

В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (А, /х) = (2,3). Если Г — граф в половинном случае, то он имеет параметры (13,6,2,3) и Г является графом Пэли. Используя равенство (А — ц)2 + 4(к — д) = п2 при А = 2, получим п2 = 4к + ¿х2 -8(1 + 4. Если ц четно, то ц = 2< и п2 = 4(к + £2 - 4« + 1). Если же ц нечетно, то /¿2 и п2 сравнимы с 1 по модулю 8, поэтому к нечетно. В случае ц = 3 имеем, что п2 = Ак—11, поэтому п = 2и+1, к = и2+«+3 и неглавные собственные значения графа Г равны и и — («+1). Кратность собственного значения и равна / = ик{к + и + 1 )/(пц) = и(и2 +и + 3)(а2 + 2и + 4)/(6и + 3), следовательно, 2« +1 делит 11 • 13 и и = 5,6 или 71. Соответственно, к — 33,45 или 5187. Случай к = 33 рассмотрен в третьей главе, к = 45 - в четвертой. Хорошо известно (предложение 1.1.2 из (7)), что сильный граф с ц > 2 регулярен. Поэтому связные компоненты непустых подграфов неподвижных точек автоморфизмов нечетного порядка сильно регулярного графа с тах{А, ¡м} < 2 либо являются кликами, либо сильно регулярны с этими же параметрами. Автоморфизмы графов Мура, т.е. сильно регулярных графов с параметрами 1), изучались в [5]. Автоморфизмы сильно регулярных графов с ^ = 2 и А 6 {0,1} рассматривались в |2], [4]. В первом параграфе третьей главы приведены вспомогательные леммы, во втором — изложен метод Г. Хигмана работы с автоморфизмами сильно регулярных графов [10].

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

В третьем параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (364,33,2,3). Затем, с помощью теории характеров конечных групп полученные результаты существенно уточняются. Автоморфизмы этого графа изучались в [36].

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

Теорема 3 Пусть Г — сильно регулярный граф с параметрами (364,33,2,3), д — элемент простого порядка р из АШ;(Г) и £2 = Е1х(<?). Тогда выполняется одно ив следующих утверждений:

(1) р = 7 или 13 и А — пустой граф;

(2) р = 11 иП является 1-кликой или р — 5 и Г2 является 4-кликой;

(3) р = 3 и либо П является графом Пэли с параметрами (13,6,2,3), либо П является объединением изолированных вершин и ■ф < 3 изолированных 4-клик, число (р + ф сравнимо с 1 по модулю 3 и не превосходит 22;

(4) р = 2 и либо |П(а)пП(Ь)| — 3 для некоторых несмежных вершин а, 6 £ П, либо П является одним из графов:

(t) 2-клика,

(ii) граф Петерсена,

(iii) Ü С а1 для некоторой вершины, а, П(а) является объединением ß изолированных вершин и 7 треугольников, где ß + 7 четно.

Из теоремы 3 следует, что для группы G автоморфизмов графа Г множество n{G) всех простых делителей G содержится в {2,3,5,7,11,13}.

Следствие 2 Пусть Г — точечный граф частичного четырехугольника PQ{3,10,3), g — элемент простого порядка р из Aut(r) и П = Fix(i?). Тогда выполняется одно из следующих утверждений:

(1) р = 7 или 13 и Q — пустой граф;

(2) р = 11 и П является 1-кликой или р = 5 и i2 является 4-кликой;

(3) р = 3 и Q является объединением ip изолированных вершин и rjj изолированных А-клик, причем (ip, ф) - (1,3), (2,2), (0,1), (3,1), (6,1), (10,0) или (7,0);

(4) р = 2 и либо |П(о) П П(6)| = 3 для некоторых несмежных вершин a,b е П, либо £1 С ах, для некоторой вершины а, П(а) является объединением ß изолированных вершин и 7 треугольников, где (/9,7) = (0,11), (3,6), (0,3) или (11,0).

В четвертой главе с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (676,45,2,3). Автоморфизмы этого графа изучались в [37].

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

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (676,45,2,3), g — элемент простого порядка р из Aut(F) и Д = Fix(y). Тогда выполняется одно из следующих утверждений:

(1) Д - пустой граф, р — 2 или 13, в случае р = 2 граф Г', вершинами которого являются g-допустимые А-клики из Г, причем вершины X, Y смежны в Г', если некоторая вершина из X смежна с вершиной из Y, является сильно регулярным с параметрами (169,42,5,12);

(2) Д является либо 1-кликой ир = 5, либо 4-кликой ир = 7;

(3) р — 13 и Д — граф Пэли с параметрами (13,6,2,3);

(4) р — 3, Д является объединением а изолированных вершин, ß изолированных А-клик и 7 графов Пэли с параметрами (13,6,2,3), число |Д| сравнимо с I по модулю 3 и верно одно из утверждений:

(») 7 = а = 2, р = 0,

(и) 7 - 1, а + Aß делится на 3 и не превосходит 18,

(да) 7 = 0, а + Aß делится на 3 и не превосходит 21;

(5) р = 2 и |Д(а) Г) Д(6)| = 3 для некоторых несмежных вершин a,b е Д, либо Д является одним из графов:

(i) граф Петерсена,

(■И) ДСа1 для некоторой вершины а, А(а) содержит <р изолированных вершин и ф треугольников,

(in) А является графом MZ(4).

Из теоремы 4 следует, что для группы G автоморфизмов графа Г множество n(G) содержится в {2,3,5,7,13}.

Следствие 3 Пусть Г — точечный граф частичного четырехугольника PQ(3,14,3), g — элемент простого порядка р из Aut(r) uí1 — Fix(g). Тогда выполняется одно из следующих утверждений:

(1) р = 2 и либо

(г) Д — пустой граф, либо

(И) |Д(а) П Д(Ь)| = 3 для некоторых несмежных вершин a, be Д, либо (ш) ДСа1 для некоторой вершины а, Д(а) является объединением у изолированных вершин и ф треугольников, (ip, ф) — (4,3) «ли (13,0);

(2) р — 3, Д является объединением а изолированных вершин и ß изолированных A-клик, где а + Aß < 19 и в случае равенства имеем ß - 0;

(3) р = 5 и А является 1-кликой;

(4) р — 7 и Д является 4-кликой;

(5) р — 13 и Д — пустой граф.

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

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

[1] Махнев, A.A. Локально 0<3(3,5)-графы и геометрии с короткими прямыми/ A.A. Махнев// Дискретная матем,- 1998.- Т.10, JV«2.- С.72-86.

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

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

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

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

[6] Махнев, A.A. Расширения О<3(4,2), вполне регулярный случай/ A.A. Махнев, Д.В. Падучих// Дискретная матем.- 2001,- Т. 13, №3.- С.91-109.

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

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

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

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

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

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

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

[141 Chang, L.C. Association schemes of partially balanced block designs with parameters v — 28, nx — 12, n0 = 15 and p\ = 4/ L.C. Chang// Sci. Record-1950.- Vol.4.- P. 12-18.

|15] Damerell, R.M. On Moore graphs/Damerell R.M.- Math. Proc. Cambr. Phil. Soc.- 1973.- Vol.74.- P.227-236.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[31] Казарина, В.И. О реберно регулярных графах с Ьг = 5/ В.И. Казари-на, А А. Махнев// Тезисы "Алгебра, Логика и Кибернетика". Материалы межд. конф., посвященной 75-летию со дня рожд. проф. А.И. Кокори-на. Иркутск, 2004.- С.159-161.

|32] Казарина, В.И. О локально GQ(s,t) графах с сильно регулярными /г-подграфами/ В.И. Казарина, А.А. Махнев// Алгебра и теория чисел. Современные проблемы и приложения. Тез. докладов VI межд. конф , посвященной 100-летию Н.Г. Чудакова. Саратов, 2004.- С.61-62.

[33] Казарина, В.И. О локально GQ(s,t) графах с сильно регулярными подграфами/ В.И. Казарина, А.А. Махнев// Алгебра и анализ, 2005.- Т.17,-С.93-106.

[34] Казарина, В.И. Об автоморфизмах сильно регулярных графов с А = 2, ц, = 3/ В.И. Казарина, А.А.Махнев// Труды 36-й молодежной конф. Екатеринбург, 2005.- С.З& 36.

[35] Казарина, В.И. Об автоморфизмах частичного четырехугольника PQ(3,10,3)/ В.И. Казарина, A.A. Махнев// Международная алгебраическая конференция, поев. 100-летию со дня рожд. П.Г. Канторовича и 70-летию JI.H. Шеврина. Екатеринбург, 2005.- С.180-181.

[36] Казарина, В.И. Об автоморфизмах сильно регулярных графов с Л =

2,ц = 3/ В.И. Казарина, A.A. Махнев// ЕкатеринбурпВестник УГТУ-УПИ, 2005.- №17(69).- С.174-194.

[37] Казарина, В.И. Об автоморфизмах сильно регулярных графов с А = 2, fi =

3, II/ В.И. Казарина// Сибирские электронные математические известия,-2005.- Т.З.- С.1-14.

[38] Казарина, В.И. Об автоморфизмах частичного четырехугольника Р<Э(3,14,3)/ В.И. Казарина// Труды 37-й молодежной конф. Екатеринбург.- 2006,- С.36-42.

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

Офсетная печать Тираж 100 Заказ №. 69

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

/го (У

И f 5 О О 7

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

Введение

1 О локально GQ(s,t) графах с сильно регулярными //-подграфами

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

1.2 Случай графов Мура

1.3 Случай графов Клебша и Гевиртца

1.4 А - граф с ц > 2.

2 О реберно регулярных графах с bi =

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

2.2 Реберно регулярные графы больших степеней с bi =

2.3 Графы с bi = 5 степени

3 Об автоморфизмах графа с (364,33,2,3)

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

3.2 Характеры групп и автоморфизмы графов.

3.3 Ииволютивные автоморфизмы графа с параметрами (364,33,2,3)

3.4 Автоморфизмы частичного четырехугольника PQ(3,10,3)

4 Об автоморфизмах графа с (676,45,2,3)

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

4.2 Характеры групп и автоморфизмы графов. 4.3 Ииволютивные автоморфизмы графа с параметрами (676,45,2,3)

4.4 Автоморфизмы частичного четырехугольника PQ(3,14,3)

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

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

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

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

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

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

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

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

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

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

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

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

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

Сильно регулярный граф с параметрами (4/л + 1,2//,/х — 1,//) называется графом в половинном случае.

Графом Поли называется граф, вершинами которого являются элементы конечного поля Fq, где q сравнимо с 1 по модулю 4, и две вершины смежны, если разность соответствующих элементов поля Fq является ненулевым квадратом.

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

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

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

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

Частичным чепшрехуголъпиком PQ(s, t, ц) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке), для любых двух несмежных вершин точечного графа пересечение их окрестностей содержит точно ц вершин и для любой точки а, не лежащей на прямой L, найдется не более одной прямой, проходящей через а и пересекающей L.

Множество вершин графа MZ(n), отвечающего аффинной плоскости 7Г = (X, С) порядка п, совпадает с объединением множества точек X и множества прямых С, причем подграф X является кокликой, две прямые смежны, если они параллельны, и точка смежна с прямой, только если она принадлежит этой прямой. Граф MZ(n) имеет п(2п + 1) вершин, является кореберно регулярным с ц = 1, А(а, 6) = 0, если одна из вершин а,Ь — точка, а другая — содержащая эту точку прямая, A(a,b) = п — 2, если а и b — параллельные прямые.

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

1) Исследовать вполне регулярные локально GQ(s,t) графы с сильно регулярными ц- подграфам и.

2) Изучить связные реберно регулярные графы с параметрами (v, к, А) и h = 5.

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

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

1. Исследованы вполне регулярные локально GQ(s,t) графы, в которых каждый /1-подграф изоморфен известному сильно регулярному графу Д.

2. Классифицированы связные реберно регулярные графов с Ь\ = 5 с одним из дополнительных условий: граф сильно регулярен или к > 14.

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

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

Международной конференции, посвященной 75-летию со дня рождения проф. А.И. Кокорина (Иркутск, 2004 г.);

VI Международной конференции, посвященной 100-летию Н.Г. Чудакова (Саратов, 2004 г.);

Международной алгебраической конференции, посвященной 100-летию со дня рождения П.Г. Канторовича и 70-летию J1.H. Шеврина (Екатеринбург, 2005 г.);

36-й и 37-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2005-2006 гг.);

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

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

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

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются связные локально GQ(s, t) графы, в которых /2-подграфы являются известными сильно регулярными графами.

Если регулярный грае}) степени к диаметра d имеет v вершин, то выполняется неравенство: v < 1+к+к(к—1)+. .+k(k—l)d~1. Графы, для которых это нестрогое неравенство превращается в равенство, называются графами Мура. Простейший пример графа Мура представляет (2d + 1)-угольник. Р. Даме-релл [20] доказал, что граф Мура степени к > 3 имеет диаметр 2. В этом случае v = к2 + 1, граф сильно регулярен с А = 0 и /2 = 1, а степень к равна 3 (граф Петерсеиа), 7 (граф Хоффмана-Сипглтопа) или 57. Существование графа Мура степени к — 57 неизвестно.

Граф Клебша определен на множестве векторов 4-мерного линейного пространства V над полем из двух элементов, причем два вектора смежны, если расстояние Хеммипга между ними равно 1 или 4. Это единственный сильно регулярный граф с параметрами (16,5,0,2). Графы Гевиртца, Хигмаиа-Симса и Маклафлина — это графы ранга 3 групп £з(4), Хигмана-Симса и Маклафлииа на 56, 100 и 275 вершинах соответственно.

Пусть А — класс графов, элементами которого являются Кщп, графы Мура, графы с параметрами (100,22,0,6), (77,16,0,4), (16,5,0,2), (56,10,0,2). Известные в настоящее время сильно регулярные графы с А = 0 принадлежат А.

Заметим, что вполне регулярные локально GQ(4,2) графы классифицированы в [8|. В работе [1] описаны связные локально GQ(3,t) графы.

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

Теорема 1 Пусть Г — вполне регулярный локально GQ(s,t) граф, в котором као/сдый ц-подграф изоморфен известному сильно регулярному графу Д £ Л. Тогда выполняется одно из следующих утверэ/сдений:

1) Д = Kt+ij+\ ut + 1 делит s2(s2 — 1);

2) Д — граф Петерсена и Г — единственный локально GQ{2, 2) граф) с параметрами (28,15,6,10);

3) Д — граф Хофмана-Синглтона, t = 6 и s = 9,14,15, 24,29 или 30;

4) Д — граф Клебша, t = 4 и s = 2,4,6,8,11,12 или 16;

5) Д — граф Гевиртца, t = 9 и s = 3,7,27,31 или 63;

6) Д — граф с параметрами (77,16,0,4), t = 15 и s = 21,41,55, 153 или 195;

7) Д — граф Хигмана-Симса, t — 21 и s = 19,24,34,35,39,45,49, 69,84,89,99,105,115,119,144,159,175,189,199,210,214,259,294,309, 339,364,375,399,419 или 420.

Следствие 1 Пусть Г — сильно регулярный локально GQ(s, t) граф), в котором као1сдый ц-подграф изоморфен известному сильно регулярному графу Д. Тогда выполняется одно из следующих ymeepoicdeiiuu:

1) Д = Kt+i,t+i и либо s = 1 и Г = либо s = 4,t = 1 и V — частное графа До/сонсона J( 10,5), либо s = t = 1,2,3,8 или 13;

2) Д — граф Петерсена и Г является единственным локально GQ{2,2) графом с параметрами (28,15, 6,10);

3) Д — граф) Гевиртца и Г — граф Маклафлина.

Известно существование и единственность сильно регулярных локально GQ(t,t) графов с fi-подграфами, изоморфными Kt+i,t+i для t = 1 (Г — частное графа Джонсона J(10,5)j, t = 2 (Г — единственный локально GQ(2,2) граф с параметрами (28,15,6,10)) и t = 3 (Г- — граф) ранга 3 для группы 1/4(2) с параметрами (176,40,12,8)).

Во второй главе работы рассматривается реберно регулярный граф с параметрами (v,k,X). В монографии А. Броувера, А. Коэна и А. Ноймайера [11] доказано, что связный реберно регулярный граф с b\ = 1 является многоугольником или полным многодольпым с долями порядка 2. А.А. Махне-^ вым в [G] получено описание реберно регулярных графов с &i < 3, а также

Ь\ = 4, к > 10. В данной главе классифицированы связные реберно регулярные графы с &i = 5 с одним из дополнительных условий: граф сильно регулярен или к > 14.

Через Ф обозначим граф, множество вершин которого разбивается тремя //-замкнутыми /^4Х2 подграфами Фх, Фг и Фз, у которого смежные вершины с, d из Фз смежны с вершинами <2i,., а\ из Ф\ и с вершинами 6i,64 из Ф2, а смежные вершины е, / из Ф3 — {с, d, с*, d*} смежны с вершинами а,2, а3, а\ ф и с вершинами 61,62,63, 64, где для х £ Фг- вершина х* является антиподом х в Фг, можно считать, что а\ смежна с 61,63,62,64, а2 смежна с 62,64,61,63, <23 смежна с 61,63,64, а4 смежна с 6|, 62,63,64.

Если О — граф диаметра, большего 2, то 0,2 ~ граф на множестве вершин графа О, в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии 2 в О.

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

Теорема 2 Пусть Г — связный реберно регулярный граф с параметрами ф (г;, к, A) u Ь\ = 5. Тогда выполняются следующие утверо/сдения:

1) если Г сильно регулярен, то он является одним из следующих графов: полный многодольный граф Кгхв(г > 2), 6 X б решетка, граф Шлефыи, треугольный граф Т(8) или один из трех графов Чанга;

2) если к > 14, то либо Г сильно регулярен, либо верно одно из утверждений: г) граф) Г изоморфен граф)у Ф; гг) Г является графюм 0,2, ?<дс О — граф) Клейна (единственный дистаициоиио регулярный локально семиугольный граф диаметра 3 па 24 вершинах, являющийся 3-накрытием 8-клики).

В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (A,/i) = (2,3). Если Г — граф в половинном случае, то он имеет параметры (13,6,2,3) и Г является графом Пэли. Используя равенство (А — /л)2 + А(к — //) = п2 при А = 2, получим п2 = Ак + ц2 — 8/х + 4. Если /i четно, то /х = 2t и п2 = 4(к + t2 — At + 1). Если же // нечетно, то fi2 и п2 сравнимы с 1 по модулю 8, поэтому к нечетно. В случае fi = 3 имеем, что п2 = Ак — 11, поэтому п = 2и + 1, к = и2 и + 3 и неглавные собственные значения графа Г равны и и — (и + 1). Кратность собственного значения и равна / = ик(к + и-{-1 )/(пц) = и(и2 + w + 3)(w2 + 2w + 4)/(6u + 3), следовательно, 2и + 1 делит 11 • 13 и и = 5,6 или 71. Соответственно, & = 33,45 или 5187. Случай к = 33 рассмотрен в третьей главе, к = 45 — в четвертой. Хорошо известно (предложение 1.1.2 из [11]), что сильный граф с /х > 2 регулярен. Поэтому связные компоненты непустых подграфов неподвижных точек автоморфизмов нечетного порядка сильно регулярного графа с шах{А,//} < 2 либо являются кликами, либо сильно регулярны с этими же параметрами. Автоморфизмы графов Мура, т.е. сильно регулярных графов с параметрами (i>, fc, 0,1), изучались в [9]. Автоморфизмы сильно регулярных графов с ц = 2 и A G {0,1} рассматривались в [7], [5]. В первом параграфе третьей главы приведены вспомогательные леммы,, во втором — изложен метод Г.Хигмана работы с автоморфизмами сильно регулярных графов [14].

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

В третьем параграфе теоретико-графовымй методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (364,33,2,3). Затем, с иомош,ыо теории характеров коночных групп полученные результаты существенно уточняются. Автоморфизмы этого графа изучались в [43].

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

Теорема 3 Пусть Г — сильно регулярный граф с параметрами

364,33,2,3), д — элемент простого порядкар из Aut(r) uQ = Fix((/). Тогда выполняется одно из следующих утверэ/сдений:

1) р = 7 или 13'м Q — пустой граф);

2) р = 11 и Q является 1 -кликой или р = 5 и Q является 4-кликой;

3) р = 3 и либо Q является графом Поли с параметрами (13,6,2,3), либо Q является объединением изолированных вершин и ф < 3 изолированных А-клик, число ip + ф сравнимо с 1 по модулю 3 и не превосходит 22;

4) р = 2 и либо |Г2(а) П 0(6)| = 3 для некоторых несмеэ/спых вершин a, b £ О, либо Q является одним из графов: г) 2-клика, гг) граф) Петерсепа, ггг) Q С а1 для некоторой вершины a, Q(а) является объединением /3 изолированных вершин и 7 треугольников, где (3 + 7 четно.

Из теоремы 3 следует, что для группы G автоморфизмов графа Г множество 7r(G) всех простых делителей G содержится в {2,3,5,7,11,13}.

Следствие 2 Пусть Г — точечный граф частпичного четырехугольника PQ{3,10,3), g — элемент простого порядка р из Aut(r) и Г2 = Fix^). Тогда выполняется одно из следующих утверэ/сдепий:

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

2) р = 11 и Q является I-кликой или р = 5 и Q является А-кликой;

3) р = 3 и Q является объединением ср изолированных вершин и ф изолированных А-клик, причем (<£>, ф) = (1,3), (2,2), (0,1), (3,1), (6,1), (10,0) или

7,0);

4) р = 2 и либо |Г2(а)П^(6)| = 3 для некоторых несмежных вершин а,Ь € Q, либо С а1-, для некоторой вершины a, Q(a) является объединением (3 изолированны,х вершин и 7 треугольников, где (/?, 7) = (0,11), (3,6), (0,3) или (11,0).

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

Теорема 4 Пусть Г — сильно регулярный граф с параметрами (676,45,2,3), g — элемент простого порядка р из Aut(r) и А = Fix(#). Тогда выполняется одно из следующих утверо/сдений:

1) Д — пустой граф, р = 2 или 13, в случае р = 2 граф Г", вершинами которого являются д-допустимые 4-клики из Г, причем вершины X, Y смеэюпы в Г', сели некоторая вершина из X смежна с вершиной из Y, является сильно регулярным с параметрами (169,42,5,12);

2) А является либо 1-кликой и р = 5, либо 4-кликой и р = 7;

3) р = 13 и А — граф Поли с параметрами (13,6,2,3);

4) р = 3, А является объединением а изолированных вершин, /3 изолированных 4-клик и 7 графов Пэли с параметрами (13,6,2,3), число |Д| сравнимо с 1 по модулю 3 и верно одно из утверэюдеиий:

0 7 = « = 2, /3 = 0, и) 7 = 1, а + 4/3 делится па 3 и не превосходит 18,

Иг) 7 = 0, а + 4/3 делится на 3 и не превосходит 21;

5) р = 2 и |Д(а) П А(Ь)\ = 3 для некоторых несмеэюиых вершин а,Ъ £ А, либо А является одним из графов: г) граф Петерсена,

И) А С а1 для некоторой вершины a, A (a) codepoicum (р изолированных вершин и ф треугольников,

Иг) А является графом MZ(4).

Из теоремы 4 следует, что для группы G автоморфизмов графа Г множество 7r(G) содержится в {2,3,5, 7,13}.

Следствие 3 Пусть Г — точечный граф частичного четырехугольника PQ(3,14,3), g — элемент простого порядка р из Aut(r) и £2 = Fix(g). Тогда выполняется одно из следующих утверэюдеиий:

1) р = 2 и либо г) А — пустой граф, либо

И) |А(а) П А(6)| = 3 для некоторых несмеэюпых вершин a, b £ А, либо (Hi) А С а1 для некоторой вершины а, А (а) является объединением <р изолированных вершин и ф треугольников, ((р,ф) = (4,3) или (13,0);

2) р = 3, А является объединением а изолированных вершин и fi изолированных 4-клик, где а + 4/? < 19 и в случае равенства имеем /3 = 0;

3) р — 5 и А является 1 -кликой;

4) р = 7 и А является А-кликой;

5) р = 13 и А — пустой граф.

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

1. Махнсн, А.А. Локально GQ(3,5)-rpa(l)bi и геометрии с короткими прямыми/ А.А. Махнев// Дискретная матем.- 1998.- Т.10, №2.- С.72-86.

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

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

4. Махнев, А.А. Об автоморфизмах сильно регулярных графов с А = О, ц = 2/ А.А. Махнев, В.В. Носов// Мат. сб.- 2004.- Т.185, ЖЗ.- С.47-68.

5. Махнев, А.А. Расширения GQ(4,2), вполне регулярный случай/ А.А. Махнев, Д.В. Падучих// Дискретная матем.- 2001.- Т.13, №3.- С.91-109.

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

7. Blokhuis, A. On locally 4-by-4 grid graphs/ A. Blokhuis, A.E. Brouwer// J. Graph Theory.- 1989.- V.13, №.- P.229-244.

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

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

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

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

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

13. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.17| Cameron, P. Extended generalized quadrangles/ P. Cameron, D.R. Hughes, A. Pasini// Gcom. Dcdic.- 1990.- V.35.- P.193-228.

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

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

16. Damerell, R.M. On Moore graphs/Damerell R.M.- Math. Proc. Cambr. Phil. Soc.- 1973.- Vol.74.- P.227-236.

17. Fisher, P.A. Triangular extended generalized quadrangles/ P.A. Fisher, S.A. Hobart// Gcoin. Dedic 1991.- V.37.- P.339-344.

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

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

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

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

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

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

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

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

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

27. Makhnev, A.A. On strongly regular locally GQ(4,t) graphs/ A.A. Makhnev// Intern. Conf. Combinatorica 2002. Maratea (Potenza). Abstracts. P.69-70.

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

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

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

31. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации

32. Казарина, В.И. О реберно регулярных графах с Ъ\ = 5/ В.И. Казарииа, А.А. Махнев// Тезисы "Алгебра, Логика и Кибернетика". Материалы межд. конф., посвященной 75-летию со дня рожд. проф. А.И. Кокори-на. Иркутск, 2004.- С.159-161.

33. Казарипа, В.И. О локально GQ(s,t) графах с сильно регулярными /г-иодграфами/ В.И. Казарина, А.А. Махнев// Алгебра и анализ, 2005.-Т.17.- С.93-106.

34. Казарина, В.И. Об автоморфизмах сильно регулярных графов с А = 2, /г = 3/ В.И. Казарина, А.А.Махнев// Труды 36-й молодежной копф. Екатеринбург, 2005.- С.35-36.

35. Казарина, В.И. Об автоморфизмах частичного четырехугольника PQ(3,10,3)/ В.И. Казарина, А.А. Махнев// Международная алгебраическая конференция, поев. 100-летию со дня рожд. П.Г. Канторовича и 70-летию JI.H. Шеврина. Екатеринбург, 2005.- С.180-181.

36. Казарина, В.И. Об автоморфизмах сильно регулярных графов с Л = 2,/i = 3/ В.И. Казарина, А.А. Махнев// Екатеринбург:Вестник УГТУ-УПИ, 2005.- №17(69).- С.174-194.

37. Казарина, В.И. Об автоморфизмах сильно регулярных графов с А = 2,/л = 3, II/ В.И. Казарина// Сибирские электронные математические известия.- 2005.- Т.З.- С.1-14.

38. Казарина, В.И. Об автоморфизмах частичного четырехугольника PQ(3,14,3)/ В.И. Казарина// Труды 37-й молодежной конф. Екатеринбург.- 2006.- С.36-42.