Расширения обобщенных четырехугольников и их автоморфизмы тема диссертации и автореферата по ВАК РФ 01.01.04, доктор наук Нирова Марина Сефовна

• Нирова Марина Сефовна
• доктор наук
• 2015

Оглавление диссертации доктор наук Нирова Марина Сефовна

Введение

Глава 1. Однородные расширения частичных геометрий и обобщенных четырехугольников

§ 1. Расширения частичных геометрий § 2. Вполне регулярные локально С^(4, ¿)-графы Глава 2. Графы с малыми значениями Ъ1 и локально циклические дистанционно регулярные графы § 3. Графы с Ъ1 =

§ 4. Сильно регулярные графы с Ъ1 <

§ 5. Автоморфизмы дистанционно регулярных графов с не более 1000 вершинами

§ 6. Дистанционно регулярные графы с ^ = 1 и не более 1000 вершинами

Глава 3. Плотные сферические схемы, 4-изорегулярные графы и их автоморфизмы

§ 7. Сильно регулярные подграфы из 1го(т) § 8. Автоморфизмы сильно регулярных подграфов из 1го(т) Глава 4. Вполне регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2, и небольшие сильно регулярные графы

§ 9. Графы, в которых окрестности вершин сильно регулярны с собственным значением

§ 10. Автоморфизмы небольших сильно регулярных графов Глава 5. Дистанционно регулярные графы с Л = 2 и не более 4096 вершинами

§ 11. Графы с ^ =1 § 12. Графы с ^ > 1 Литература

Введение диссертации (часть автореферата) на тему «Расширения обобщенных четырехугольников и их автоморфизмы»

Введение

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

Регулярным графом степени к называется граф Г, такой что для любой вершины и Е Г выполняется равенство |Г(и)| = к. Реберно регулярным графом с параметрами (у, к, Л) называется регулярный граф степени к на у вершинах, любое ребро которого лежит точно в Л треугольниках. Вполне регулярным графом с параметрами (у, к, Лназывается реберно регулярный граф с параметрами (у, к, Л), в котором любые две вершины и,ш Е Г на расстоянии 2 имеют ровно ^ общих соседей. Сильно регулярным графом с параметрами (у, к, Лназывается реберно регулярный граф с параметрами (у, к, Л), в котором любые две несмежные вершины и,ш Е Г имеют ровно ^ общих соседей.

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

Заметим, что сильно регулярный граф с ^ > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d > 2 — вполне регулярным графом с к = Ь0, Л = к — Ъ\ — 1 и ^ = с2.

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

Система инцидентности, состоящая из точек и прямых, называется

а-частичной геометрией порядка (в,Ь), если каждая прямая содержит ровно в + 1 точку, каждая точка лежит ровно на Ь +1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой Ь, найдется точно а прямых, проходящих через а и пересекающих Ь (обозначение рОа(в,1)). Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на общей прямой (коллинеарны). Легко понять, что точечный граф частичной геометрии pGa(s,t) сильно регулярен с параметрами: V = (в + 1)(1 + вЬ/а), к = в(Ь +1), Л = (в - 1) + (а - 1)Ь, у = а(Ь + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел а, называется псевдогеометрическим графом для pGa(s,t).

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы лиева типа [1]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [2].

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

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

Граф Г диаметра d называется дистанционно транзитивным, если для любого г Е {0,...^} группа А^Г действует транзитивно на {(п,т) | п,'ш Е Г и d(u,w) = г}. Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп могут

быть представлены как группы автоморфизмов графов ранга 3 [5].

Пусть задан класс графов Т. Мы скажем, что граф Г является локально Т-графом, если для любой вершины а Е Г имеем Г(а) Е Т. Можно поставить задачу описания локально Т-графов. Если граф Г вер-шинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально Т-графом, где Т состоит из графов, изоморфных некоторому графу А. В этом случае назовем Г локально А-графом. В более общем случае Т может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов — это в точности класс связных, локально регулярных графов.

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

Пусть М и N—конечные множества порядка т и п, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется т х п-решеткой; при т = п он сильно регулярен с параметрами (п2, 2(п — 1),п — 2, 2).

Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т(п) также сильно регулярен и имеет параметры (п(п—1)/2, 2(п—2), п—2, 4). Окрестность каждой вершины в Т(п) изоморфна 2 х (п — 2)-решетке, т.е. Т(п)— локально 2 х (п — 2)-решетка.

Единственный сильно регулярный граф с параметрами (27,16,10, 8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10, 6, 6) называется графом Клебша. Граф Шлефли является локально графом Клебша.

В главе 1 получено описание параметров сильно (в — 2)-однородных расширений частичных геометрийpGa(s, Ь) и классифицированы дистанционно регулярные локально GQ(4, Ь)-графы.

В кандидатской диссертации М.С. Нировой классифицированы в-одно-родные и сильно (в — 1)-однородные расширения частичных геометрий pGa(s,t) (см. [6]).

Пара (а, Ь) частичной геометрии (Р, С) называется флагом, если точка а принадлежит прямой Ь, и антифлагом в противном случае. Если (а, Ь) является антифлагом, то через f (а, Ь) обозначим число точек в Ь, коллинеарных а. Геометрия называется ^-однородной, если для любого антифлага (а, Ь) число f (а, Ь) равно 0 или ¡р, и сильно ^-однородной, если это число всегда равно р. Геометрия pGt(s,t) является сетью, а

р03+1(в,1) является 2-схемой с Л = 1. Если Б — частичная геометрия рОа(в,1), то двойственная геометрия (С,Р), в которой каждая точка отождествляется с пучком проходящих через нее прямых, является частичной геометрией рОа(1, в).

В параграфе 1 получено описание параметров сильно (в—2)-однородных расширений частичных геометрий рОа(в, Ь)

Теорема 1.1. Пусть Б — сильно (в—2)-однородная геометрия ЕрСа(в, Ь), Г = Г(Б). Тогда либо геометрия Б является расширением двойственной 2-схемы pG¿+1(2í + 2,Ь), Г — псевдогеометрический граф для сети pG2t(2í + 3, 2Ь) и дополнительный граф к блочному графу является псевдогеометрическим графом для рС4+2(2Ь + 3,Ь2 + 2Ь), либо выполняется одно из следующих утверждений:

(1) а = 1, Г — псевдогеометрический граф для рС6(9, 8), рС2(5, 8), pG4(7, 24), pG6(9, 32) или pG1o(13,120) и геометрия Б — это EGQ(8,1), ЕСд(4, 2), EGQ(6, 4), EGQ(8, 4) или EGQ(12,10) соответственно;

(2) Ь = а > 1, Г является псевдогеометрическим графом дляpG6(9, 8) и геометрия Б — это EpGt(8,í) для некоторого Ь Е {2,..., 5};

(3) Г — псевдогеометрический граф дляpGз(6, 20), pG4(7, 3), pG4(7,4), pG4(7, 8) или pG4(7, 20) и Б — это EpG2(5, 8), EpG2(6,1), EpGз(6, 2), EpG3(6, 4) или EpG3(6,10) соответственно;

(4) Г является псевдогеометрическим графом дляpG5(8,140), pG6(9, 56), pG6(9, 8г) (г Е {2, 4}), pG6(9, 2Ь) (Ь Е {3, 7,13}), pG6(9, 32), pG8(11, 40), pG8(11, 95) илиpG8(11, 2и) (и Е {4,16}) и геометрия Б — это EpG4(7, 80), EpG2(8,14), EpGз(8, 3г), EpG4(8, Ь), EpG5(8, 20), EpGз(10,12), EpG4(10, 38) или EpG5(10,u) соответственно;

(5) 10 <8 < 20, Г — псевдогеометрический граф для одной из геометрий pGg(12,99), pGl2(15,56), pGl2(15,16), pGl2(15,26), pGl5(18,170), pGl6(19, 56), pG17(20, 323), pG18(21,150) илир^18(21, 24) и Б — EpGa(11, 9а) (а Е {3, 4,6}), EpGа(14,4а) (а Е {2, 3, 5, 9}), EpG7(14, 8), EpG7(14,13), EpGa(17,10а) (а Е {2, 3, 8}), EpG9(18, 28), EpGa(19,17а), а Е {3,10,13}, EpG6(20, 45) или EpG15(20,18) соответственно;

(6) 20 <8 < 40, Г — псевдогеометрический граф для одной из геометрий pG32(35,136), pG32(35,136), pG32(35,136) илиpG32(35,104) и Б — это одна из геометрий EpG11(34, 44), EpG28(34,112), EpG7(34, 28) или EpG17(34, 52) соответственно;

(7) 40 <в, Г является псевдогеометрическим графом дляpG48(51, 880) илиpG48(51, 200) и Б — одна из геометрий EpG15(50, 264) или EpGa(50, 4а) (а Е {3, 8, 23, 33}) соответственно.

В работе Ф.Бюкенхаута и К.Юбо [7] рассматривается задача классификации локально полярных пространств, в частности, локально GQ(s, Ь)-

графов. Там же получено решение этой задачи в случае s = 2.

В случае s = 3 описание локально GQ(s, ^-графов завершено в работе А.А. Махнева [8].

В случае s = 4 известны вполне регулярные локально GQ(4, ^-графы для t G {2, 4, 6, 8,11,16} (см. [9-14]). Кроме того, известны сильно регулярные локально GQ(4, ^-графы [15].

В параграфе 2 изучены вполне регулярные локально GQ(4, ^-графы, t G {1,12}. Тем самым завершена классификация дистанционно регулярных локально GQ(4, ^-графов.

Теорема 1.2. Пусть Г — связный вполне регулярный локально GQ(4,12)-граф с параметрами (v, k, X, ß). Тогда диаметр Г равен 3 и ß G {56, 60, 64, 70,80,84}.

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

(1) t = 1, либо ß = 4 и Г — граф Джонсона J(10,5) или его стандартное частное, либо ß = 8 и Г имеет массив пересечений {25,16,1; 1, 8, 25};

(2) t = 2, Г — граф с параметрами (126,45,12,18) на множестве векторов нормы 1 в 6-мерном ортогональном пространстве типа "— " над GF(3) или Г — единственный локально GQ(4, 2)-граф с массивом пересечений {45, 32,12,1; 1,6, 32, 45};

(3) t = 6, Г имеет параметры (726,125, 28, 20) или Г — граф с массивом пересечений {125,96,1;1, 48,125}.

Для реберно регулярного графа с параметрами (v,k, X) параметр Ъ\ равен k—X—1. Глава 2 посвящена изучению графов с малыми значениями Ъ\ и локально циклических дистанционно регулярные графов с числом вершин, не большим 1000.

Хорошо известно, что связный граф с Ъ\ = 1 является многоугольником или полным многодольным графом с долями порядка 2. Вполне регулярные графы с 2 < Ъ\ < 5 изучены в [16-18]. Если Ъ\ = 6, то наиболее сложный случай возникает при k = 10, X = 3. Этот случай изучается в параграфе 3.

Пусть Г — связный граф, в котором окрестности вершин изоморфны графу Петерсена. Тогда [2, теорема 1.16.5] Г является дистанционно регулярным графом с массивом пересечений {10, 6; 1, 6} (граф T(7)), {10, 6,4,1; 1, 2,6,10} (граф Конвея-Смита) или {10, 6, 4; 1, 2, 5} (граф До-ро).

Теорема 2.1. Пусть Г — связный вполне регулярный граф с параметрами (v, 10, 3,ß). Тогда выполняется одно из следующих утверждений:

(1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,

3, 4);

(2) ^ = 3, диаметр Г равен 3 и 34 < у < 37;

(3) ^ = 2 и Г является графом Конвея-Смита или графом Доро.

Из теоремы 2.1 и результатов [19] вытекает классификация вполне регулярных графов с Ь1 = 6.

Следствие 2.1. Пусть Г — связный вполне регулярный граф с Ь1 = 6. Тогда Г является одним из следующих графов:

(1) полный многодольный граф Кгх7, граф с параметрами (25,12, 5, 6), 7 х 7-решетка, треугольный граф Т(9), дополнительный граф к 5 х 5-решетке или к треугольному графу Т(7), граф Хофмана-Синглтона или его дополнение, граф с параметрами (26,10, 3, 4) или его дополнение;

(2) полный двудольный граф К8,8 с удаленным максимальным паросо-четанием, граф Тэйлора с параметрами (28,13, 6,6), в котором окрестности вершин изоморфны графу Пэли Р(13) или граф Тэйлора с параметрами (32,15, 8,6), в котором окрестности вершин изоморфны треугольному графу Т(6);

(3) ^ =1, окрестность каждой вершины является 7-кокликой, или объединением изолированных п-клик для п = 2, 3 или 6;

(4) ^ = 2 и либо

(г) Г является ректаграфом с у < 27 и диаметра, не большего 7 (в случае у = 27 или ¿(Г) = 7 граф Г является 7-кубом), либо

(гг) окрестность каждой вершины в Г является объединением четырех изолированных ребер, либо

(ггг) Г — дистанционно регулярный граф с массивом пересечений {9, 6,1; 1, 2, 9}, граф Конвея-Смита или граф Доро;

(5) ^ = 3 и либо

(г) Г — дистанционно регулярный граф с массивом пересечений {8, 6,1; 1, 3, 8}, либо

(гг) Г — локально девятиугольный граф диаметра 3, каждый ^-подграф является 3-кокликой или объединением изолированной вершины и ребра, Ь2(и,х) < 3 для любых вершин и,х с ¿(и,х) = 2 и |Г3(и)| < 10, либо

(ггг) к = 10, диаметр Г равен 3 и 34 < у < 37, либо (гу) к = 11, диаметр Г равен 3, у = 36 и Г3(и) является 2-кликой для некоторой вершины и;

(6) ^ = 4 и Г — граф Джонсона /(7, 3).

Хотя вполне регулярные графы с малыми значениями параметра Ь1

удалось классифицировать только для Ъ\ < 6, но сильно регулярные графы удалось изучить до Ъ\ < 23.

В параграфе 4 изучаются сильно регулярные графы с Ъ\ < 24.

Графом Джонсона J(n, m) называется граф, вершинами которого являются m-элементные подмножества данного n-элементного множества, причем две вершины а, Ъ смежны, только если |а П Ъ| = m — 1. Графом Хемминга H(n, m) называется граф, вершинами которого являются элементы из Xn, где |X| = m и две вершины смежны, только если расстояние Хемминга между ними равно 1. Граф Пэли P(q) в качестве вершин имеет элементы поля Fq, q = 1 (mod 4), и две вершины а, Ъ смежны, только если Ъ — а является ненулевым квадратом в Fq. Граф Петерсена — это дополнительный граф для треугольного графа T(5) (он имеет параметры (10,3,0,1)). Граф Шрикханде — это единственный сильно регулярный локально шестиугольный граф с параметрами (16,6,2,2). Имеется точно 3 сильно регулярных графа, имеющих параметры графа T(8), но не изоморфных T(8). Эти графы называются графами Чанга.

Сильно регулярные графы с собственным значением —2 были классифицированы Зейделем [2, теорема 3.12.4]. Любой зейделев граф — это либо полный многодольный граф Krx2, либо решетчатый или треугольный граф, либо один из графов Шрикханде, Чанга, Петерсена, Клебша или Шлефли.

Теорема 2.2. Пусть Г является сильно регулярным графом с 0 < Ъ\ < 24. Тогда Г — граф из следующего списка:

(1) граф с параметрами (4Ъ\ + 1, 2Ъ\, Ъ\ — 1,Ъ\), Ъ\ £ {5, 8,14,17,19, 23} или полный многодольный граф Krx(b1+1);

(2) зейделев граф или его дополнение;

(3) псевдогеометрический граф для GQ(s,t), {s,t} £ {{2, 2}, {2, 4}, {3, 3}, {3, 5}, {4,4}, {6, 3}} или его дополнение;

(4) псевдогеометрический граф для сети pGt(s,t), где либо t = 2, s = 3,4, 5,..., 12, либо t = 3, s = 4, 5,..., 9, либо t = 4, s = 6, 7, 8, либо t = 5, s = 8, либо t = s — 2, s = 7, 8, 9;

(5) псевдогеометрический граф дляpG2(4,t) (t = 3, 7), pG2(5,5), pG3(s,

2) (s = 5,6,8,9,12), pG3(5, 7), pG4(7, 2), pG4(7, 3), pG4(8, 3), pG5(9, 3), pG5(14, 2), pG6(8, 5), pGa(15, 2), pGg(15, 2), pGg(18, 2), pGg(15, 3), pGio(15,

3), pGi4(20, 3), pGi5(24, 2), pGi5(19, 3) или pG2o(24, 3);

(6) дополнительный граф либо к графу из пункта (5), либо к псевдогеометрическому графу для GQ(4, 6);

(7) граф с параметрами (50, 7, 0,1), (56,10, 0, 2), (77,16,0, 4), (81, 20,1, 6), (82, 36,15,16), (85, 30,11,10), (85,14,3,2), (99,14,1,2), (100, 33,14,9), (100, 22, 0, 6), (126, 25, 8, 4), (136, 30,8,6), (162,23,4,3), (243,22,1,2),(300,

26, 4, 2), или (400, 21, 2,1);

(8) дополнительный граф для графа из пункта (7).

В параграфе 5 изучаются дистанционно регулярные локально циклические графы.

В.П. Буриченко и А.А. Махнев [20] нашли массивы пересечений дистанционно регулярных локально циклических графов с числом вершин не большим 1000. В [21] найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных локально циклических графов с числом вершин не большим 1000.

Предложение 2.1. Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если А = 2 и ß > 1, то либо Г имеет массив пересечений графа Хэмминга H(n, 3), n = 3, 4, 5,6, либо верно одно из утверждений:

(1) Г — примитивный граф с массивом пересечений {15,12, 6; 1, 2,10}, {19,16,8; 1,2,8}, {24,21,3;1,3,18}, {35, 32, 8; 1, 2, 28}, {51, 48, 8; 1,4,36};

(2) Г — антиподальный граф с ß = 2 и массивом пересечений {2r + 1, 2r - 2,1; 1, 2, 2r + 1}, r G {3, 4,..., 21} - {10,16} и v = 2r(r + 1);

(3) Г — антиподальный граф с ß > 3 и массивом пересечений

{15,12,1; 1, 4,15}, {18,15,1; 1, 5,18}, {27, 24,1; 1, 8, 27}, {35, 32,1; 1, 4, 35}, {45, 42,1; 1, 6, 45}, {42, 39,1; 1, 3,42}, {75, 72,1; 1,12, 75}.

В [22-25] найдены возможные простые порядки автоморфизмов графов с 4 первыми массивами пересечений из пункта (1) заключения предложения. В параграфе 2.3 изучаются автоморфизмы гипотетического дистанционно регулярного графа с массивом пересечений {51, 48, 8; 1, 4, 36}. Тем самым завершается описание автоморфизмов графов из пункта (1) заключения предложения. Ни один из этих графов не является реберно симметричным.

Граф с массивом пересечений {51, 48, 8; 1, 4, 36} имеет v = 1 + 51 + 612 + 136 = 800 вершин и спектр 511,11102 , 3425, -9272, причем Г2 - сильно регулярный граф с параметрами (800,612,468,468) и неглавными собственными значениями 12, -12.

Теорема 2.3. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {51, 48,8; 1, 4, 36}, G = Аи1(Г), g — элемент из G простого порядка p и П = Fix(g). Тогда n(G) С {2, 3, 5,17} и выполняются следующие утверждения:

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

(i) p = 5, ai(g) = 400 + 100/ - 60s, «2(0) = 120s и a3(g) = 400 -100/ - 60s, либо

(ii) p =2, ai(g) = 400 + 40r — 24t, a2(g) = 48t и a3(g) = 400 — 40r —

24t;

(2) p = 17, |Q| = 1, a2(g) = 204 и либо a1(g) = 595,a3(g) = 0, либо a1(g) = 255 и a3(g) = 340;

(3) p =3, либо

(i) 2 < |Q| < 14 и Q состоит из вершин попарно находящихся на расстоянии 3, либо

(ii) 14 < |Q| < 62, либо

(iii) аз(#) = 0, ai(g) = 120r + 40 — 5ao(g), ^(g) = 760 + 4ao(g) — 120r и 65 < |Q| < 98;

(4) p =2, |Q| четно и либо

(i) a1(g) = a(g) = 0 и Q G {32, 80}, либо

(ii) 4 < |Q| < 62, либо

(iii) аз(^) = 0, ai(g) = 80r — 5ao(g) = 0, a2(g) = 20ao(g) + 800 — 80r и 64 < |Q| < 106.

Следствие 2.2. Граф с массивом пересечений {51, 48, 8; 1, 4, 36} не является реберно симметричным.

В параграфе 6 изучаются дистанционно регулярные графы с ß = 1 и числом вершин не большим 1000.

Заметим, что В.П. Буриченко и А.А. Махнев не рассматривали случай ß =1. А.А. Махнев поставил задачу нахождения массивов пересечений антиподальных дистанционно регулярных графов диаметра 3 с X =2, ß = 1 и числом вершин, не большим 1000. В параграфе 2.4 решена более общая задача. Найдены массивы пересечений антиподальных дистанционно регулярных графов диаметра 3 с X < 2 и ß = 1. Далее, найдены возможные порядки и подграфы неподвижных точек автоморфизмов дистанционно регулярного графа с массивом пересечений {42, 39,1; 1,1, 42}.

Предложение 2.2. Пусть Г является антиподальным дистанционно регулярным графом диаметра 3 с X < 2 и ß = 1. Тогда выполняется одно из следующих утверждений:

(1) X = 0 и k G {2,6, 56};

(2) X = 1 и Г — дистанционно транзитивный граф с массивом пересечений {2е, 2е — 2,1; 1,1, 2е};

(3) X = 2, Г имеет массив пересечений {42, 39,1; 1,1, 42} и спектр 421, 6774, —130, —5903.

Существование графа в пункте (1) предложения равносильно существованию сильно регулярного графа с параметрами ((k + 1)2 + 1, k + 1, 0, 1) (графа Мура).

Теорема 2.4. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {42, 39,1; 1,1, 42}, G = Аи^Г), д — элемент из G простого порядка р и П = Пх(д). Тогда выполняются следующие утверждения:

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

(г) р = 43, а3(д) = 0, а1(д) = 430г и г Е {0,1, 2, 3}, либо

(гг) р = 5, а3(д) = 200в + 120, а1(д) = 50Ь + 40 и 5Ь + 20в < 155, либо

(ггг) р =2, а3(д) = 80в + 40, а1(д) = 80/ и 1 + в < 21;

(2) П лежит в антиподальном классе графа Г и либо (г) р =7, |П| = 26 и |а2(д)| > 42 ■ 26, либо

(гг) р = 3, |П| Е {1, 4,..., 40} и |а1(д)| < 421П |, либо (ггг) р =2, |П| Е {2, 4,..., 38} и |а2(д)| > 42|П|;

(3) р =13 и П является 4-кликой;

(4) р = 2 и П — шестиугольник или вторая окрестность вершины в графе Хофмана-Синглтона.

Следствие 2.3. Группа автоморфизмов дистанционно регулярного графа с массивом пересечений {42, 39,1; 1,1, 42} действует интранзитивно на множестве вершин.

В главе 3 изучаются 4-изорегулярные графы, их сильно регулярные подграфы и автоморфизмы. Для подмножества вершин Б графа Г через Г(Б) обозначим Паез([а] — Б).

Граф Г называется Ь-изорегулярным, если для любого г < Ь и любого г-вершинного подмножества Б число |Г(Б)| зависит только от изоморфного типа подграфа, индуцированного Б. Заметим, что класс 2-изорегулярных графов совпадает с классом сильно регулярных графов. Граф Г на у вершинах называется абсолютно изорегулярным, если он является (у — 1)-изорегулярным. Далее, Ь-изорегулярный граф называется точно Ь-изорегулярным, если он не является (Ь + 1)-изорегулярным.

Камерон [26, теорема 8.21] доказал, что каждый 5-изорегулярный граф Г является абсолютно изорегулярным и, с точностью до перехода к дополнительному графу, является полным многодольным графом Ктхп, пятиугольником или 3 х 3-решеткой. Далее, каждый точно 4-изорегулярный граф, с точностью до перехода к дополнительному графу, является псевдогеометрическим графом для pGr(2г, 2г3 + 3г2 — 1). Через Тго(г) будем обозначать такой граф. При г =1 получим точечный граф единственного обобщенного четырехугольника порядка (2, 4), а при г = 2 — граф Маклафлина.

Существование плотной сферической 5-схемы в Бп-1 (см. [27]) равносильно существованию графа /го(г), где п = (2г + 1)2 — 2. В [27, следствие

4.7] доказано несуществование плотных 5-схем для бесконечного набора значений параметра г: 3,4, 6,10,12, 22, 28, 30, 34, 42, 46,... .

В параграфе 7 найдены параметры 6 сильно регулярных подграфов из Г = Тго(г): X = [а], А = Г2(а) для вершины а € Г; Х(6), Х2(Ь) для вершины Ь € X; А(с), А2(с) для вершины с € А.

Предложение 3.1. Пусть Г — псевдогеометрический граф для (2г, 2г3 + 3г2 — 1). Тогда он имеет V = 8г4 + 16г3 + 6г2 — 2г — 1 вершин и собственные значения к = 4г4 + 6г3,г, —(2г3 + 3г2) кратностей 1,/ = 8г4 + 16г3 + 2г2 — 6г, д = 4г2 + 4г — 2 соответственно. Далее, для любой вершины а

(1) подграф X = [а] — псевдогеометрический граф для рСг-1(2г — 1, г3 + г2 — г — 1), имеет v1 = 4г4 + 6г3 вершин и собственные значения к1 = 2г4 + г3 — 3г2 + г, г1 = г, 51 = —(г3 + г2 — г) кратностей 1,/1 = 4г4 + 6г3 — 4г2 — 4г + 2, д1 = 4г2 + 4г — 3 соответственно;

(2) подграф А = Г2(а) сильно регулярен, имеет v2 = 4г4 + 10г3 + 6г2 — 2г — 2 вершин и собственные значения к2 = 2г4 + 3г3, г2 = г, з2 = — (г3 + 2г2) кратностей 1, /2 = 4г4 + 10г3 + 2г2 — 6г, д2 = 4г2 + 4г — 3 соответственно.

Предложение 3.2. Пусть X является псевдогеометрическим графом для рСг-1(2г — 1, г3 + г2 — г — 1). Тогда он имеет V = 4г4 + 6г3 вершин и собственные значения к = 2г4 + г3 — 3г2 + г, г, — (г3 + г2 — г) кратностей 1, / = 4г4 + 6г3 — 4г2 — 4г + 2, д = 4г2 + 4г — 3 соответственно. Далее, для любой вершины Ь € X

(1) подграф X(b) — псевдогеометрический граф для рСг-2(2г — 2,

(г3 — 3г — 2)/2), имеет v1 = 2г4 + г3 — 3г2 + г вершин и собственные значения г4 — г3 — 3г2 + 3г, г, — (г3 — 3г)/2 кратностей 1, /1 = 2г4 + г3 — 7г2 — 3г + 3, д1 = 4г2 + 4г — 4 соответственно;

(2) подграф X2(b) сильно регулярен с параметрами (2г4+5г3+3г2 — г — 1, г4 + г3 — г2, (г4 — г3 — 3г2 + 3г)/2, (г4 — г2)/2) и собственными значениями г4+г3 — г2, г, —(г3 + 2г2 — г)/2 кратностей 1, 2г4+5г3 — г2 — 5г+2, 4г2+4г — 4 соответственно.

Предложение 3.3. Пусть А является сильно регулярным графом с параметрами (4г4 + 10г3 + 6г2 — 2г — 2, 2г4 + 3г3, г4 — 2г2 + г, г4 + г3) и собственными значениями к = 2г4 + 3г3,г, —(г3 + 2г2) кратностей 1, 4г4 + 10г3 + 2г2 — 6г, 4г2 + 4г — 3 соответственно. Если г > 2, то для любой вершины с € А

(1) подграф А(с) является сильно регулярным графом с параметрами (2г4 + 3г3, г4 — 2г2 + г, (г4 — 2г3 — 3г2 + 6г)/2, (г4 — г3 — 2г2 + 2г)/2) и

собственными значениями r4 — 2r2 + r, r, — (r3 + r2 — 2r)/2 кратностей 1, 2r4 + 3r3 — 4r2 — 4r + 3, 4r2 + 4r — 4 соответственно;

(2) подграф A2(c) сильно регулярен с параметрами (2r4 + 7r3 + 6r2 — 2r — 3, r4 + 2r3, (r4 — 3r2 + 2r)/2, (r4 + r3)/2), собственными значениями r4 + 2r3, r, —(r3 + 3r2)/2 кратностей 1, 2r4 + 7r3 + 2r2 — 6r, 4r2 + 4r — 4 соответственно.

Далее, с помощью метода Хигмена для автоморфизма g графа Izo(r) найдена формула для значения характера, полученного при проектировании на подпространство размерности 4r2 + 4r — 2

X2(g) = (ao(g) — ai(g)/r)/((r + 1)(2r + 1)) + (2r2 + 2r — 1)/(r + 1).

Найдены возможные простые порядки автоморфизмов g графа Izo(r) таких, что подграф Q = Fix(g) является пустым, кликой или кокликой.

Теорема 3.1.

(1) Если Q — пустой граф, то

(i) p делит (2r + 1)(4r3 + 6r2 — 1), в частности, p =2,

(ii) если p = 3, то r = 1 (mod 3), a1(g) = wr(2r + 1) и w + 1 делится на r + 1 .

(2) Если Q является n-кликой, то n =1 и либо p = 37, r = 37u + 17, либо p = 2.

(3) Если Q является m-кокликой, m > 2, то 3 < m < 4r2 + 4r — 2, p делит r и m + 1.

А.А. Махнев [28] доказал, что псевдогеометрический граф для pG2(5, 32) не существует. Так как окрестность вершины в графе Izo(3) является псевдогеометрическим графом для pG2(5, 32), то и граф Izo(3) не существует. Однако вопрос о существовании сильно регулярного графа с параметрами (640,243,66,108) (это параметры второй окрестности вершины в графе Izo(3)) остается открытым.

В параграфе 8 найдены возможные автоморфизмы сильно регулярного графа с параметрами (640,243,66,108).

Пусть Г является сильно регулярным графом с параметрами (640,243, 66,108), a — вершина графа Г. Тогда Г имеет собственные значения k = 243, r = 3,s = —45 и достигается равенство во втором условии Крей-на (s + 1)(k + s + 2rs < (k + s)(r + 1)2. Поэтому [a] является сильно регулярным графом с параметрами (243,66,9,21) и Г2(a) является сильно регулярным графом с параметрами (396,135,30,54). В работах [29, 30] найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с параметрами (243,66,9,21) и

(396,135,30,54). С помощью этих результатов найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (640,243,66,108). При этом решалась задача восстановления автоморфизма графа по его действию на окрестности и на антиокрестности неподвижной точки.

Теорема 3.2. Пусть Г является сильно регулярным графом с параметрами (640, 243, 66,108), G = Aut(r), g — элемент простого порядка p из G, П = Fix(g). Тогда выполняется одно из следующих утверждений:

(1) П — пустой граф, либо p = 5 и ai(g) £ {240, 480}, либо p = 2 и ai(g) £ {96,192,288,384,480, 592};

(2) П является 1-кликой, p = 3 и a1(g) = 99;

(3) П является m-кокликой, m > 2, p =3 и (|П|, a1(g)) £ {(4, 204), (13, 87), (13, 519), (22,402), (31, 285), (37, 351),(40,168)};

(4) p =3, П является регулярным графом степени 3t, 0 < t < 24, ai(g) = 54r + 9t + 135q + 6s, s = 0 и 28 < |П| = 1 + 3t + 3s < 100;

(5) p = 2, П содержит вершину степени 2t + 1, a1(g) = 36r + 6t + 45q + 12s +12, q четно, -2 < q < 6, s = 0 и 16 <|П| = 2t + 2 + 6s < 154.

Следствие 3.1. Сильно регулярный граф с параметрами (640, 243, 66, 108) не является реберно симметричным.

В главе 4 изучаются вполне регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2, небольшие сильно регулярные графы и их автоморфизмы.

А.Л. Гаврилюком и А.А. Махневым предложена программа изучения вполне регулярных графов, в которых окрестности вершин — сильно регулярные графы с данными параметрами и собственным значением 2.

В работе [31] получено описания класса Q сильно регулярных графов с собственным значением 2. Там же классифицированы графы, в которых окрестности вершин — графы из Q с параметром А' = 1. В работах [32-35] получено описание графов, в которых окрестности вершин — графы из Q с параметром А' = 0.

Предложение 4.1. Г £ Q, то выполняется одно из следующих утверждений:

(1) Г — объединение изолированных треугольников, четырехугольник или пятиугольник;

(2) Г — псевдогеометрический граф для pG(2s-6)/3(2s/3, s — 3), s делится на 3, или псевдогеометрический граф для pGs-2(s, s — 2);

(3) Г иммет параметры v = (2s2 + 5s + 3)/3, k = (2s2 — 4s)/3, А = (2s2 — 13s + 24)/3, ß = (2s2 — 10s + 12)/3, и s = —1 (mod 3);

(4) Г — псевдогеометрический граф для pGs-2(s,t), где (s,t) принадлежит либо

(i) {(3, 3), (3, 5), (3, 9)}, либо

(ii) {(4,1), (4, 7), (4, 9), (4,12), (4,17), (4, 27)}, либо

(iii) {(5,1), (5, 7), (5, 9), (5,12), (5,17), (5, 27)}, либо

(iv) {(6,18), (7, 25), (8, 3), (8, 5), (8,15), (8, 21), (9, 42)}, либо

(v) {(14,2), (14,4), (14, 32), (32,5)};

(5) Г имеет параметры либо

(i) (26,15, 8, 9), (36,14,4, 6), (45, 32, 22, 24), (50, 7, 0,1), (56,10, 0, 2), (76, 30, 8,14), (77,16,0, 4), либо

(ii) (81, 20,1, 6), (99, 56, 28, 36), (100, 22, 0, 6), (105, 52, 21, 30), (105, 32, 4,12), (120, 42, 8,18), (126,100, 80, 84), либо

(iii) (126, 50,13, 24), (154, 72, 26, 40), (162, 56,10, 24), (162, 92, 46, 60), (176, 70,18, 34), (225,128, 64, 84), (232,154, 96,114), (243,110, 37, 60), либо

(iv) (253,112, 36, 60), (300,182,100,126), (351, 210,113,144), (375, 272,190,216), (441,352,276,300), (476,342,236,270), (540,392,274,312), (703,520,372,420), (1344,221,88,26), (1911,270,105,27).

В работе [36] приведено описание вполне регулярных графов, в которых окрестности вершин либо являются псевдогеометрическими графами для pGs-2 (s, t), либо сильно регулярны с параметрами v = (2s2 + 5s + 3)/3, k = (2s2 - 4s)/3, A = (2s2 - 13s + 24)/3, ц = (2s2 - 10s + 12)/3, и s = — 1 (mod 3).

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

Теорема 4.1. Пусть Г — связный вполне регулярный граф, в котором окрестности вершин сильно регулярны с параметрами (v', k', A', из пункта (5) заключения предложения 4.1. Если A' > 2, то верно одно из следующих утверждений:

(1) Г — сильно регулярный граф с параметрами (100,36,14,12), в котором окрестности вершин имеют параметры (36,14, 4, 6);

(2) ^(Г) = 3 и либо

(i) ^ G {18, 24, 36} и окрестности вершин имеют параметры (105, 32, 4,12), либо

(ii) ^ = 35 и окрестности вершин имеют параметры (162, 56,10, 24), либо

(iii) ^ = 66 и окрестности вершин имеют параметры (243,110, 37, 60), либо

(iv) ^ = 70 и окрестности вершин имеют параметры (253,112, 36,

Эта теорема существенно уточняется в статье И.Н. Белоусова, А.А. Махнева и М.С. Нировой [50], завершающей реализацию вышеуказанной программы.

Теорема 4.2. Пусть Г — связный вполне регулярный граф, удовлетворяющий условиям теоремы 4.1. Тогда ^(Г) = 2.

Теорема 4.3. Пусть Г — сильно регулярный граф с параметрами (100, 36, 14,12), G = АШ;(Г), g — элемент простого порядка p из G и Q = Fix(g). Тогда выполняется одно из следующих утверждений:

(1) Q — пустой граф, либо p = 5 и a1(g) G {0,100}, либо p =2 и a1(g) G {0, 20, 40,..., 100};

(2) Q является n-кликой, либо p = 7 и n = 2, a1(g) = 42 или n = 9 и a1(g) G {14, 84}, либо p = 3, n G {1, 4, 7,10} и a1(g) + 4n делится на 10;

(3) Q является l-кокликой, 2 < l < 10, то либо p = 3, a1(g) = 10r — 4/ и l G {4, 7,10}, либо p = 2, a1(g) = 20s — 4l, каждая вершина из Г — Q смежна с четным числом вершин из Q и l G {4,6, 8,10};

(4) p =3, |Q| = 3t + 1, 4 < t < 9 и 12t + 4 + Ö1(g) G {70,100,130,160};

(5) p =2, |Q| = 2s, 2 < s < 25 и 8s + a1(g) делится на 20.

Следствие 4.1. Пусть Г — реберно симметричный сильно регулярный граф с параметрами (100, 36,14,12), в котором котором окрестности вершин сильно регулярны с параметрами (36,14, 4, 6). Тогда Г — граф ранга 3 и группа АШ;(Г) изоморфна Aut(J2).

Из этого следствия и результатов [31-36] получаем

Следствие 4.2. Пусть Г — дистанционно регулярный граф, в котором окрестности вершин — графы из Q. Тогда либо окрестности вершин в Г — объединения изолированных треугольников, либо Г — сильно регулярный граф с параметрами (6, 4, 2, 4), (27,16,10, 8), (35,16, 6, 8), (100,36,14,12), (162,56,10,24), (176,40,12,8), (210,95, 40,45), (245, 64,18, 16), (275,112, 30, 56), (372, 56,10, 8) или (486,100, 22, 20), либо диаметр Г больше 2 и выполняется одно из следующих утверждений:

(1) Г является локально псевдо pG2(4, t)-графом Тэйлора;

(2) Г — граф икосаэдра или граф Джонсона J(8, 4);

(3) Г — граф Тервиллигера с массивом пересечений {50, 42,1; 1, 2, 50} или {50, 42, 9; 1, 2, 42};

(4) Г — антиподальное 3-накрытие сильно регулярного графа с параметрами (162, 56,10, 24), имеющее массив пересечений {56, 45,16,1; 1,8, 45,56};

(5) Г имеет массив пересечений {81,60,1; 1, 20, 81}.

В параграфе 10 изучаются сильно регулярные графы с числом вершин, не большим 100, и их автоморфизмы.

Хорошо известно, что имеются 30 наборов параметров неизвестных сильно регулярных графов с числом вершин, не большим 100. Из результатов Бехбахани и Лама [37] следует, что только 11 из них могут отвечать реберно симметричным графам.

Предложение 4.2. Пусть Г — неизвестный реберно симметричный сильно регулярный граф с числом вершин, не большим 100, и G = АШ;(Г). Тогда выполняется одно из следующих утверждений:

(1) Г имеет параметры (85, 30,11,10) и п^) = {2, 3,5,17};

(2) Г имеет параметры (85, 54, 33, 36) и п^) = {2, 3,5,17};

(3) Г имеет параметры (88, 27, 6, 9) и {2, 3,11} С п^) С {2, 3, 5,11};

(4) Г имеет параметры (88, 60, 41, 40) и п^) = {2, 3,5,11};

(5) Г имеет параметры (96, 45, 24,18) и п^) = {2, 3,5};

(6) Г имеет параметры (96, 50, 22, 30) и п^) = {2, 3,5};

(7) Г имеет параметры (96, 60, 38, 36) и п^) = {2, 3,5};

(8) Г имеет параметры (99,42, 21,15) и {2, 3, 7,11} С п^) С {2, 3, 5, 7,11};

(9) Г имеет параметры (99,56, 28, 36) и {2, 3, 7,11} С пЙ С {2, 3, 5, 7,11};

(10) Г имеет параметры (100, 33, 8,12) и п^) = {2, 3, 5,11};

(11) Г имеет параметры (100, 66, 44,42) и п^) = {2, 3, 5,11}.

А.А. Махневым и М.С. Нировой предложена программа класифика-ции реберно симметичных сильно регулярных графов с параметрами из заключения предложения 4.2 и сделан первый шаг на пути реализации этой программы.

Теорема 4.4. Пусть Г — сильно регулярный граф с параметрами (85, 30, 11,10), д — элемент простого порядка р из Аи^Г) и А = Пх(д). Тогда выполняется одно из следующих утверждений:

(1) А — пустой граф и либо р = 5, а1(д) Е {25, 70}, либо р =17 и

а1(д) = 34;

(2) А является в-кликой, и либо

(г) р = 2 и в = 3, а1(д) Е {4, 22,40,58, 76} или в = 5, а1(д) Е {14, 32, 50,68} или в = 7, а1(д) Е {6, 24, 42, 58, 76}, либо

(гг) р = 3 и в =1, а1 (д) Е {12, 39,66} или в = 4, а1 (д) Е {0, 27, 54} или в = 7, а1(д) Е {15, 42, 69};

(3) р = 5, А является 7-кокликой и 7 = 5, а1(д) Е {5,50} или 7 = 10, а1(д) Е {30, 75};

(4) р =3, |А| = 3Ь +1, 2 < Ь < 7 и (12Ь — 30 + а1(д))/9 сравнимо с 1 по модулю 3;

(5) р =2, |А| = 2в + 1, 2 < в < 13 и 8в — 30 + а1(д) делится на 18.

Следствие 4.3. Сильно регулярный граф с параметрами (85, 30,11,10) не является вершинно симметричным.

В работах [38-41] доказано несуществование реберно симметричных сильно регулярных графов с параметрами (88, 27,6, 9), (88, 60, 41, 40), (96, 45,24,18), (96, 50,22,30), (96, 60,38,36), (99, 42, 21,15)и(99, 56,28,36). Завершает вышеуказанную программу

Теорема 4.5. Пусть Г — сильно регулярный граф с параметрами (100, 33, 8,12), д — элемент простого порядка р из АШ;(Г) и А = Пх(д). Тогда выполняется одно из следующих утверждений:

(1) А — пустой граф, р = 2 и а1(д) = 20* или р = 5 и а1(д) = 0,50,100;

(2) А является 4-кликой, р =2 и а1(д) — 12 делится на 20, или р =3 и а1(д) — 12 делится на 30;

(3) А является 7-кокликой, либо

(г) 7 =1, р =3 и и а1(д) = 3, 33, 63, 93 или р =11 и а1(д) = 33,

либо

(гг) р = 3, 7 = 4, 7,..., 16 и а1(д) — 37 делится на 30;

(4) А является объединением п > 2 изолированных ш^-клик, р = 2, Ш € {2,4} и |А| < 20;

(5) А содержит геодезический 2-путь и либо (г) р =3, |А| = 3* + 1, 3 < Ь < 8, либо

(гг) р = 2, |А| = 2в, 3 < 5 < 25.

Следствие 4.4. Сильно регулярные графы с параметрами (100, 33, 8,12) и (100,66, 44, 42) не являются реберно симметричными.

В главе 5 найдены массивы пересечений дистанционно регулярных графов с Л = 2 и не более 4096 вершинами.

В.П. Буриченко и А.А. Махнев [20] нашли массивы пересечений дистанционно регулярных графов с Л = 2, ^ > 1 и числом вершин не большим 1000. Отметим, что в [20] пропущены массивы {9,6, 3; 1, 2, 3} графа Хемминга Н(3, 4) с V = 64 и {12, 9, 6, 3; 1, 2, 3,4} графа Хемминга Н(4, 4) с V = 256 вершинами и массив {33, 30,15; 1, 2,15}, зато имеется лишний массив {13,10, 7; 1, 2, 7} (граф с таким массивом пересечений не существует).

В § 11 найдены допустимые массивы пересечений дистанционно регулярных графов с Л = 2, ^ =1 и не более 4096 вершинами.

Теорема 5.1. Пусть Г — дистанционно регулярный граф с Л = 2, ^ =1, имеющий не более 4096 вершин. Тогда Г имеет один из следующих массивов пересечений:

(1) {21,18; 1,1} (V = 400);

(2) {6, 3, 3, 3; 1,1,1, 2} (Г — обобщенный восьмиугольник порядка (3,1), V = 160), {6, 3, 3; 1,1, 2} (Г — обобщенный шестиугольник порядка (3,1),

V = 52), {12,9, 9; 1,1,4} (Г — обобщенный шестиугольник порядка (3, 3),

V = 364), {6, 3, 3, 3, 3, 3; 1,1,1,1,1, 2} (Г — обобщенный двенадцатиугольник порядка (3,1), V = 1456);

(3) {18,15, 9; 1,1,10} (V = 1 + 18+270+243 = 532, Г3 — сильно регулярный граф), {33, 30, 8; 1,1, 30}, {39, 36,4; 1,1, 36}, {21,18,12, 4; 1,1, 6, 21} (V = 1 + 21 + 378 + 756 + 144 = 1300, д4 4 = 0).

В § 12 завершена классификация дистанционно регулярных графов с Л = 2 и не более 4096 вершинами.

Следствие 5.1. Пусть Г — дистанционно регулярный граф диаметра, большего 2, с Л = 2, имеющий не более 4096 вершин. Тогда выполняется одно из утверждений:

(1) Г — примитивный граф с массивом пересечений {6, 3, 3; 1,1, 2}, {9, 6, 3; 1, 2, 3}, {12, 9, 9;1,1, 4}, {15,12, 6; 1, 2,10} {18,15, 9; 1,1,10}, {19, 16, 8; 1, 2, 8}, {24, 21, 3; 1, 3,18}, {30, 27, 24; 1, 2,10}, {33, 30, 8; 1,1, 30}, {33, 30,15; 1, 2,15}, {35, 32, 8; 1, 2, 28}, {35, 32, 28; 1,4, 8}, {39, 36, 4; 1,1, 36}, {39, 36, 20; 1, 2, 20}, {39, 36, 22; 1, 2,18}, {39, 36, 27; 1, 4,13}, {42, 39, 24; 1, 2,12}, {48, 45, 9; 1,1, 40}, {51, 48, 8; 1, 4, 36}, {51, 48, 24; 1, 2, 24}, {55,52, 34; 1, 2, 22}, {58, 55, 8; 1, 2, 44}, {60, 57,16; 1, 4, 30}, {60,57, 32; 1, 4,18}, {63, 60,10; 1, 2, 54}, {63,60,49;1,4,15}, {68,65,32;1,4,40}, {75,72,8; 1, 2, 60}, {75,72,42;

1, 4, 50}, {75, 72, 31; 1, 8, 45}, {80, 77, 61; 1, 7, 20}, {90, 87, 60; 1,15,18}, {99, 96,12; 1, 4,88}, {99, 96, 20; 1, 4, 72}, {99, 96, 6; 1,6, 88}, {120,117, 5; 1, 5,108}, {143,140,34;1,7,110}, {147,144,39; 1,12,117}, {224,221,32;1,16,208} ;

(2) Г — антиподальный граф с ^ = 2 и массивом пересечений {2г + 1, 2г — 2,1; 1, 2, 2г + 1}, г Е {3, 4,..., 44} —{10,16, 28, 34, 38} и V = 2г(г + 1);

(3) Г — антиподальный граф с ^ > 3 и массивом пересечений

{15,12,1; 1, 4,15}, {18,15,1; 1, 5,18}, {27, 24,1; 1, 8, 27}, {35, 32,1; 1, 4, 35}, {45, 42,1; 1, 6, 45}, {42, 39,1; 1, 3,42}, {63, 60,1; 1, 4,63}, {75, 72,1; 1,12, 75}, {99, 96,1; 1, 4, 99}, {108,105,1; 1, 5,108}, {147,144,1; 1,16,147}, {171,168,1;1,12,171}, {243,240,1;1,20,243};

(4) Г — примитивный граф с массивом пересечений {6, 3, 3, 3; 1,1,1, 2}, {12, 9,6, 3; 1, 2, 3, 4}, {21,18,12, 4; 1,1, 6, 21}, {15,12, 9,6, 3; 1, 2, 3, 4, 5}, {6, 3, 3, 3, 3, 3; 1,1,1,1,1, 2}, {18,15,12, 9, 6, 3; 1, 2, 3, 4, 5,6}.

Отметим, что к списку Буриченко-Махнева добавились только массивы некоторых обобщенных многоугольников, графов Хемминга Н(п, 4), двух графов с ^ =1, массив {33, 30,15; 1, 2,15} и массивы графов диаметра 3 с числом вершин, большим 1000.

Список литературы диссертационного исследования доктор наук Нирова Марина Сефовна, 2015 год

ЛИТЕРАТУРА

1. Tits J. Buildings of Spherical Type and finite BN-pairs, Springer Lecture Notes in Mathematics, v. 386, 1974.

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

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

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

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

6. Махнев А.А., Нирова М.С. Об однородных расширениях частичных геометрий // Труды Института математики и механики УрО РАН 2007, т. 13, N 1, 148-157.

7. Buekenhout F., Hubaut X. Locally polar spaces and related rank 3 groups //J. Algebra 1977, v. 45, 391-434.

8. Махнев А.А. Локально GQ(3,5)-графы и геометрии с короткими прямыми // Дискр. матем. 1998, т. 10, 72-86.

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

10. Махнев А.А., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(4,4)-графах // Доклады академии наук 2010, т. 434, N 5, 583-586.

11. Махнев А.А., Падучих Д.В., Хамгокова М.М. О вполне регулярных локально GQ(4,6)-графах // Доклады академии наук 2011, т. 439, N 2, 146-149.

12. Махнев A.A., Падучих Д.В. О вполне регулярных локально GQ(4,8)-графах // Доклады академии наук 2012, т. 443, N 1, 58З-58б.

13. Махнев A.A., Падучих Д.В. Обобщенный четырехугольник GQ^,^) и его расширения //XI Белорусская математическая конф. Тез. докл. Минск: Институт математики HAH Беларуси, 2012. С. 39-40.

14. Кагазежева A^. О локально GQ(4,11)-графах // Математический форум (Итоги науки. Юг России), т. б Группы и графы, Владикавказ 2012, 28-39.

15. Махнев A.A. О сильно регулярных локально GQ(4,t)-графах // Сибирский матем. журнал 2008, т. 49, N 1, 1б1-182.

16. Махнев A.A. О сильной регулярности некоторых реберно регулярных графов // Известия PAH, сер. матем. 2004, т. б8, 159-172.

17. Васильев QA., Махнев A.A. О вполне регулярных графах с b; = 4 // Известия Гомельского госуниверситета. Гомель 200б, 101-108.

18. Казарина В.И., Махнев A.A. О реберно регулярных графах с b1 = 5 // Владикавказский матем. журнал 2009, т. 11, N 1, 29-42.

19. Ефимов К.С., Махнев A.A. О вполне регулярных графах с k = 11, Л = 4 // Ученые записки Казанского университета 2012, т. 154, N 2, 83-92.

20. Буриченко В.П., Махнев A.A. О вполне регулярных локально циклических графах // Современные проблемы математики. Тезисы 42 Всероссийской молодежной конференции. ИММ УрО PAH, Екатеринбург

2011, 11-14.

21. Буриченко В.П., Махнев A.A. Об автоморфизмах сильно регулярных локально циклических графов // Доклады академии наук 2011, т. 441, N 2, 151-155.

22. Буриченко В.П., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12, б; 1, 2,10} // Доклады академии наук 2012, т. 444, № 3, 305-309

23. Белоусов ИЛ. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {19,1б, 8; 1, 2, 8} // Доклады академии наук

2012, т. 443, № 3, 305-309

24. Махнев A.A., Падучих Д.В. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {24, 21, 3; 1, 3,18} // Aлгебра и логика 2012,

25. Махнев A.A., Циовкина Л.Ю. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {35, 32, 8; 1, 2, 28} // Труды Института математики и механики 2012, т. 18, N 1, 235-241.

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

27. Nebe G., Venkov B. On tight spherical designs // Алгебра и анализ 2012, т. 24, N 3, 163-171.

28. Махнев А.А. О несуществовании сильно регулярных графов с параметрами (486,

165,36,66) // Украинский матем. журнал 2002, т. 54, N 7, 941-949.

29. Махнев А.А., Токбаева А.А. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) // Владикавказский матем. журнал 2010, т. 12, N 4, 35-45.

30. Исакова М.М., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (396,135,30,54) // Владикавказский матем. журнал 2010, т. 12, N 3, 32-42.

31. Кабанов В.В., Махнев А.А., Падучих Д.В. О сильно регулярных графах с собственным значением 2 и их расширениях // Труды Института математики и механики УрО РАН 2010, т. 16, N 3, 105-116.

32. Гаврилюк А.Л., Махнев А.А. Дистанционно регулярные графы, в которых окрестности вершин изоморфны графу Хофмана-Синглтона // Доклады академии наук 2009, т. 428, N 2, 157-160.

33. Гаврилюк А.Л., Махнев А.А., Падучих Д.В. О графах, в которых окрестности вершин изоморфны графу Гевиртца // Труды Института математики и механики УрО РАН 2010, т. 16, N 2, 35-47.

34. Махнев А.А., Падучих Д.В. Вполне регулярные графы, в которых окрестности вершин изоморфны графу Хигмена-Симса // Труды Института математики и механики УрО РАН 2011, т. 17, N 4, 189-198.

35. Махнев А.А., Падучих Д.В. Вполне регулярные графы, в которых окрестности вершин изоморфны графу Матье // Труды Института математики и механики УрО РАН 2012 т. 18, N 3, 189-198.

36. Зюляркина Н.Д., Махнев А.А. О расширениях сильно регулярных графов с собственным значением 2 // Доклады академии наук 2012, т. 442, N 1, 7-10.

37. Behbahani M., Lam C. Strongly regular graphs with non-trivial automorphisms // Discrete Math. 2011, v. 311, N 2-3, 132-144.

38. Ефимов К.С., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (88,27,6,9) // Доклады академии наук 2012, т. 445, N 3, 247-250.

39. Журтов А.Х., Махнев А.А., Кагазежева А.М. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) // Доклады академии наук 2012, т. 445, N 3, 247-250.

40. Белоусов И.Н., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (96,60,38,36) // Доклады академии наук 2013, т. 451, N 3, 247-250.

41. Ефимов К.С., Махнев А.А. Об автоморфизмах сильно регулярных графов с параметрами (99,42,21,15) и (99,56,44,42) // Доклады академии наук 2013, т. 449, N 3, 247-250.

42. Cameron P.J., Hughes D.R., Pasini A. Extended generalized quadrangles // Geom. Dedic. 1990, v. 35, 193-228.

43. Hobart S.A., Hughes D.R. EpGs with minimal ц. II // Geom. Dedic. 1992, v. 42, 129-138.

44. Neumaier A. Strongly regular graphs with smallest eigenvalue — m // Arch. Math. 1979, v. 33, 392-400.

45. Hobart S.A., Hughes D.R. Extended partial geometries: nets and dual nets // Europ. J. Comb. 1990, v. 11, 357-372.

46. Махнев А.А. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) // Украинский матем. журнал 2002, т. 54, N 7, 941-949.

47. Brouwer A.E., Haemers W.H. Spectra of graphs (course notes) // http://www.

win.tue.nl/ aeb/

48. Blokhuis A., Brouwer A., E. Locally 4-by-4 grid graphs //J. Graph Theory 1989, v. 13, 229-244.

49. Махнев А.А. Аффинные овоиды и расширения обобщенных четырехугольников // Матем. заметки 2000, т. 68, N 2, 266-271.

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

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

52. Brouwer A.E. Homepage, URL: http://www.win.tue.nl/ aeb/ table of parameters of strongly regular graphs (30.11.2011).

53. Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.

54. Гаврилюк А.Л., Махнев А.А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {56, 45,1; 1, 9, 56} // Доклады академии наук 2010, т. 432, N 5, 512-515.

55. Махнев А.А. Дистанционно регулярный граф с массивом пересечений {56, 45,1; 1, 9, 56} не является вершинно симметричным // Доклады академии наук 2010, т. 435, N 4, 451-454.

56. Кондратьев А.С., Храмцов И.В. О конечных четырепримарных группах // Труды ИММ УрО РАН 2011, т. 17, N 4, 142-159.

57. Gardiner A. Homogeneous graphs //J. Comb. Theory 1976, v. 20, 94-102.

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

59. Cameron P., Goethals J., Seidel J. Strongly regular graphs having strongly regular subconstituents //J. Algebra 1978, v. 55, 257-280.

60. Горшков И.Б. О гипотезе Томпсона для простых групп со связным графом простых чмсел // Алгебра и логика 2012, т. 51, N 2, 168-192.

Публикации автора по теме диссертации

61. Ефимов К.С., Махнев А.А., Нирова М.С. О вполне регулярных графах с k = 10, А = 3 // Труды Института математики и механики УрО РАН 2010, т. 16, N 2, 75-90.

62. Журтов А.Х., Махнев А.А., Нирова М.С. Об автоморфизмах 4-изорегулярных графов // Труды Института математики и механики УрО РАН 2010, т. 16, N 3, 93-104.

63. Махнев А.А., Нирова М.С. Об автоморфизмах сильно регулярного графа с параметрами (640,243,66,108) // Доклады академии наук 2011, т. 440, N 6, 743-746.

64. Нирова М.С. Сильно (s — 2)-однородные расширения частичных геометрий pGa(s,t) // Труды Института математики и механики УрО РАН 2011, т. 17, N 4, 244-257.

65. Махнев А.А., Нирова М.С. О небольших симметричных сильно регулярных графах // Доклады академии наук 2012, т. 444, N 1, 23-27.

66. Махнев А.А., Нирова М.С. О графах, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012, т. 444, N 3, 258-261.

67. Нирова М.С. О сильно регулярных графах с b1 < 24 // Труды Института математики и механики УрО РАН 2012, т. 18, N 3, 187-194.

68. Белоусов И.Н., Махнев А.А., Нирова М.С. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012, т. 447, N 5, 258-261?.

69. Махнев А.А., Нирова М.С. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {51,48, 8; 1, 4, 36} // Математический форум (Итоги науки. Юг России). Т. 6 Группы и графы. Владикавказ: ЮМИ ВНЦ РАН и РСО-А 2012, 129-141.

70. Нирова М.С. Об антиподальных дистанционно регулярных графах с ß =1 // Доклады академии наук 2013, т. 448, N 4, 378-381.

71. Нирова М.С. Реберно симметричные сильно регулярные графы с числом вершин, не большим 100 // Сибирские электронные математические известия 2013, т. 10, 22-30.

72. Нирова М.С. Дистанционно регулярные локально GQ(4,12)-графы // Сибирские электронные математические известия 2012, т. 9, 653-659.

73. Махнев А.А., Нирова М.С. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {51, 48,8; 1, 4, 36} // Доклады академии наук 2013, т. 449, N 3, 258-261.

74. Makhnev A.A., Nirova M.S. On distance-regular graphs with Л = 2 // Jornal of Siberian Federal Univ. 2014, т. 7, N 2, 188-194.

75. Ефимов К.С., Махнев А.А., Нирова М.С. О вполне регулярных графах с k = 10, Л = 3 // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина, Нальчик 2009, 44-48.

76. Журтов А.Х., Махнев А.А., Нирова М.С. Об автоморфизмах 4-изорегулярных графов // Теория групп и ее приложения. Труды VIII Международной школы-конференции по теории групп. Нальчик 2010, 100-107.

77. Белоусов И.Н., Махнев А.А., Нирова М.С. О расширениях сильно регулярных графов с собственным значением 2 // Алгебра и линейная оптимизация. Тез. докл. Международной конф. Екатеринбург 2012, 2527.

78. Махнев А.А., Нирова М.С. О небольших симметричных сильно регулярных графах // Алгебра и линейная оптимизация. Тез. докл. Международной конф. Екатеринбург 2012, 124-125.

79. Нирова М.С. Об антиподальных дистанционно регулярных графах с ß = 1 // Теория групп и ее приложения. Тез. докл. Международной школы-конференции. Владикавказ 2012, 94-96.

80. Нирова М.С. О локально GQ(4,12)-графах // Современные проблемы математики. Тез. докл. 44 Международной молодежной школы-конференции. Екатеринбург 2013, 85-87.

81. Нирова М.С. О реберно симметричных сильно регулярных графах с числом вершин, не большим 100 // Алгебра и комбинаторика. Тез. докл. межд. конф., посвященной 60-летию А.А. Махнева, Екатеринбург 2013, 390-394.

82. Махнев А.А., Нирова М.С. О дистанционно регулярных графах с Л = 2 // Теория групп и ее приложения. Труды Межд. школы-конф. Нальчик 2014, 41-42.