Локальное строение графов и их автоморфизмы

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

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

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

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

Д. Хигман (см. [2, 3]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов и действуют транзитивно на множестве {(и, w) | и, w Е Г и d (u, w) — г} для любого г < 2. То есть, такие графы являются дистанционно транзитивными графами диаметра 2.

Граф Г диаметра d называется дистанционно транзитивным, если для любого г е {0,., d} группа Aut Г действует транзитивно на {(u, w) | и, w € Г и d (u, w) = г}.

Дистанционно регулярным графом с массивом пересечений (Ъц,. , ci,., со) называется граф диаметра d, в котором для любых вершин u, w G Г, находящихся на расстоянии г, подграф T (w) содержит ровно bi вершин, находящихся на расстоянии г + 1 от и, и ровно сгвершин, находящихся на расстоянии г — 1 от гг. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы pi к дистанционно транзитивным графам.

Заметим, что сильно регулярный граф с ц > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d > 2—вполне регулярным графом с к = bo, X — к — b — 1 и /j, — С2.

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

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

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

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

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

В главе 1 (см. также [51]) получена новая оценка для числа вершин в реберно регулярных графах. В [12, лемма 4.2.1] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (v, k, X), в котором k > 3&i, то диаметр Г равен 2 и выполняется неравенство kb! > (ук-1)(к-2Ьг + 1).

Полученные в главе 1 результаты позволяют уточнить эту оценку.

Пусть а, b — вершины графа Г. Число вершин в [а] П [Ь] обозначим через Х (а, Ь) (через ?(a, b)), если d (a, b) = 1 (если d (a, b) = 2), а соответствующий подграф назовем Х-подграфом (/i-подграфом).

Пусть Г — реберно регулярный граф с параметрами (v, k, X) и Ь — к — X — 1. Пара вершин и, w называется хорошей (почти хорошей), если d (u, w) = 2 и w) равно к — 2b + 1 (равно к — 2bi + 2). Тройка вершин (u-w, z) называется хорошей (почти хорошей), если w, z е Г2(и) и fi (u, w) + ?(u, z) не больше 2к — АЬ + 3 (равно 2к — 4Ь + 4).

Через Кти., т" обозначим полный п-дольный граф, с долями порядков mi,., mn. Если mi —. = тп = т, то соответствующий граф обозначается через Кпхт¦ Граф называется 3-лапой.

Если вершины u, w находятся на расстоянии г в Г, то через bi (u, w) (через Ci (u, w)) обозначим число вершин в пересечении Г^+1(гг) (пересечении rji (w)) с [ги]. Заметим, что в реберно регулярном графе с параметрами (v, k, А) значение bi (u, w) не зависит от выбора ребра {и, w} и равно к — X — 1.

Теорема 1.1. Пусть Г — связный неполный реберно регулярный граф с параметрами (v, Ar, Л) и к > 3&i — 2. Тогда выполняется одно из следующих утверждений:

1) для любой вершины w верно неравенство T2(w)(k — 2bi+2) < kb;

2) для любой вершины w верно неравенство j (/с — Ч- 2) > kb и либо Г является реберным графом тривалентного графа без треугольников (т.е. к = 4, Л = 1) и диаметр графа Г больше 2, либо Г является п-уголъником, п > о, или графом икосаэдра;

3) Г является полным многодольным графом Кгх2, 3×3 решеткой, треугольным графом Т (т), т <7, графом Клебша или графом Шлефли и для любой вершины т верно равенство |Г2(и-)|(А- — 2Ь + 2) = кЬ.

Доказательство утверждения (2) теоремы из [33] некорректно (не доказано утверждение (3) из [33, лемма 3.3]). Следующий результат уточняет данное утверждение.

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

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

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

3) если для некоторой вершины ги подграф Г2(гу) содержит три вершины образующие хорошие пары с ъи, то 5 = —2, у — к — 1 = 26, + 2, ?>1 (?"1 — 1) делится на 3, подграф {/, и, г} является кликой, для х & {/, и, г} подграф Г2(го) П Г2(ж) содержит две вершины х', х", для различных вершин х, у € •{/, и, г) подграф [ги] П [ж] П [у] содержит единственную вергиину ху, граф {/и, иг, ¡-г} является кликой и | [ги] — ([/] и [и] и = 4;

4) если для некоторой вершины т подграф Г2(ги) содержит четыре вершины {и, г, /, д}, образующие хорошие пары с ги, то Ь — 6, к = 16, Л = 9, у = 31, подграф {и, г, /, д} является кликой и ¿-¿-(ги, у) > 7 для любой вершины у из Г2(гу) — {и, г, /, д}.

Имеется немного результатов о единственности сильно регулярного графа с данными параметрами (у, к, А, у). В качестве следствия теоремы 1.1 получена единственность некоторых реберно регулярных графов с данными параметрами (у, к, Х).

Следствие 1.1. Пусть Г — реберно регулярный граф, имеющий те о/се параметры (у, к, Х), что и один из следующих графов: полный многодольный граф КГХз, 3×3 решетка, треугольный граф Т{т), т < 7, граф Клебша или граф Шлефли. Тогда Г изоморфен соответствующему графу.

Глава 2 посвящена изучению графов без т-корон.

Граф К с т долями порядка 1 называется т-короной. При т ~ 1 и т = 2 будем называть т-корону 3-лапой и короной, соответственно. Понятно, что т-корона получается из (тп — 1)-короны добавлением одной вершины, смежной со всеми остальными вершинами. Поэтому граф без т-корон—это в точности граф локально без (т — 1)-корон.

Пусть V является п-мерным векторным пространством над полем Два т-мерных подпространства из V будем считать смежными, если они пересекаются по (то — 1)-мерному подпространству. Граф на множестве всех то-мерных подпространств V с такой смежностью называется графом Грассмана и обозначается через Jq{n, т). При т — 2 граф Грассмана сильно регулярен. Граф Грассмана ^(п, т) не содержит (индуцированных) корон.

В параграфе 2.1 изучаются сильно регулярные графы, у которых окрестность каждой вершины является кликовым /3-расширением рхд-решетки. Интерес к таким графам был вызван тем, что при изучении графов без корон, в которых //-подграфы являются регулярными графами заданной положительной степени (см. [28, 43]) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым /3-расширением р х (/-решетки.

Теорема 2.1. Пусть Г — сильно регулярный граф с отрицательным собственным значением —т, в котором окрестность каждой вершины является кликовым (3-расширением р х д-решетпки, 2 < р < д. Тогда выполняются следующие утверждения:

1) число вершин в максимальной клике Ь графа Г равно 1 + Рд или 1 + /Зр, и (Ь, В) является (ь, Ь, г, к,)-схемой, где В — множество сингулярных прямых графа Г, лежащих в Ь, к = ?3 + 1, Л = 1, и тройка (.

2) если р < д, то число (1 + Рд)-клик в графе Г равно ри/(1 + Рд), и 1 + Рд делит р[р — 1)(/л — р+ 1), а число (1 + /Зр)-клик равно дь/(1 + /Зр), и 1 + /Зр делит — 1)((1 — д + 1), если р = д, то 1 + /Зр делит 2(р — г)(р-1,Р + 1)(р+1,Р-1);

3) для двух несмежных вершин а, Ь любая строка (любой столбец) решетки, отвечающей [а], содержит 0 или /3 + 1 вершин из [Ь], и ц = г{/3 + 1), где/3 + 1.

4) если Ь = /3 + 1, то [а] П [6] является? х решеткой, и Г является треугольным графом Т (т) (т > 4), графом 7(10,5) или графом Грассмана Л1(п, 2), п > 4;

5) если тп = р — и, то I < р — и, причем равенство достигается лишь при и = 0- в частности, Ь ф р — 1, и если? = р — 2, то т = р — 1, (2/3 + 1){р — 2) = Р (д — 1), и Р + 1 делит 2(р — 1, д);

6) если? = р, то т = р, и г) Г является псевдогеометрическим графом для рСр+1(Рд, р—1), и (рч + р-р- 1){Р + 1) делит р (р- 1)/Зд (/Зд + 1), гг) если р < д, то Г является геометрическим графом, и каждый ц-подграф в графе прямых данной геометрии является объединением непересекающихся (/3 + 1) х (?3 +1)-решеток, (3 + 1 делит <7 — 1, и р (3 +1 делит д (д — 1)(/?д + 1) — ггг) если р = д, то (?3 + I)2 делит р2(р{3 + 1).

Заметим, что если Г — псевдогеометрический граф для 1)) являющийся локально р х р-графом, то Г — дополнительный граф для 4×4-решетки в случае р = 3 и граф, 7(8,4) в случае р = 4 (отсюда следует изоморфизм 7(8,4) и дополнительного графа для графа Грассмана.

М 4,2)).

В теореме 2 из [17] была получена классификация сильно регулярных локально р х д-граф о в с 2 < р < г/ и < 6. Следующая теорема распространяет этот результат на графы, в которых окрестности вершин являются кликовыми расширениями р х ^-решетки.

Теорема 2.2. Пусть Г — сильно регулярный граф, в котором окрестность каэ/сдой вершины является кликовым 0-расширениемру.д-решетки, 2 < р < дЕсли р < 6, то выполняется одно из следующих утверждений:

1) /3 = р — 1, иТ является графом Грассмана </р1 (п, 2);

2) ?3 — р — 2, и либо Г имеет параметры второй окрестности вершины в графе Грассмана ,/р1(4,2), либо является точечным графом частичной геометрии рОр-((р — 2) д, р — 1), р — 1 делит д — 1;

3) (3 = 2, и Г является псевдогеометрическим графом для частичной геометрии рСз (12, 5);

4) /3 = 1, и Г является либо треугольным графом Т (д + 2), либо дополнительным графом для 4×4-решетки, графом 1(8,4) или <7(10, 5), либо псевдогеометрическим графом для частичной геометрии рй<¿-(6, 5).

В параграфе 2.2 изучаются графы Тервиллигера без корон и графы без 3-коклик с регулярными /¿—подграфами (см. также [43]).

Пусть а1- — шар радиуса 1 с центром а. Для подграфа, А графа Г через А1- обозначим Паела±— Граф Г назовем слабо редуцированным, если из равенства а1 = Ь1- следует, а — Ь. Граф Г назовем редуцированным, если из включения а1- С следует, а = Ь. Через Гх обозначим подграф на множестве всех вершин, а таких, что а1- = Г.

М. Нумата [14] получил классификацию графов без корон, в которых /¿—подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап). В связи с этим результатом представляет интерес изучение графов, в которых каждый //-подграф является реберно регулярным графом без 3-лап с заданными параметрами (v', k', А').

В статье В. В. Кабанова [28] было получено следующее обобщение результата Нуматы, опирающееся на более ранние работы A.A. Махнева и В. В. Кабанова:

Связный редуцированный граф без корон, содержащий 3-коклику, в котором ß—подграфы регулярны заданной степени, а > 0 и имеют диаметр 2, является графом Грассмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.

Важным этапом в доказательстве этого результата стала лемма 2.1 [28], в которой доказано, что слабо редуцированный граф без 3-лап, содержащий 3-коклику, в котором /¿—подграфы регулярны заданной положительной степени, является редуцированным.

Предложение 2.1. Если Г — связный слабо редуцированный граф без 3-коклик, в котором ß—подграфы регулярны степени, а > 0, то Г является редуцированным графом или пятиугольной пирамидой.

В статье A.A. Махнева и В. В. Кабанова [25] было доказано, что если Г—связный граф Тервиллигера без 3-лап, то либо Г является кликовым расширением графа икосаэдра, либо подграф, индуцированный на множестве всех вершин из Г — Г-1 с некликовыми окрестностями, является кликовым расширением пустого графа, клики или графа с? = 1.

Теорема 2.3. Пусть Г — связный граф Тервиллигера без корон, Г' — подграф на множестве вершин с некликовыми окрестностями. Тогда выполняется одно из следующих утверждений:

1) Г не содержит 3-коклик и является кликовым расширением 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;

2) Г не содержит 3-лап, но содержит 3-коклику, диаметр Г больше 2, и либо г) Г является кликовым расширением графа икосаэдра, либо (гг) Г' является кликой, и Г является кликовым расширением графа А, где, А содерэюит 8-клику и 8 или 5—1 вершин степени 1, смежных с различными вершинами клики, либо in) Г' является кликовым расширением графа с? = 1;

3) Г содержит 3-лапу,? = 1, и окрестность любой вершины из Г состоит из изолированных клик.

Следствие 2.1. Пусть Г — связный граф, в котором окрестности вершин являются регулярными графами Тервиллигера диаметра 2. Если окрестность некоторой вершины не содержит корон и Ъ-коклик, то либо Г является кликовым расширением пятиугольника или графа икосаэдра, либо Г — локально граф Петерсена, т. е. граф Т (7), граф Конвея-Смит на 63 вершинах диаметра 4 (это антиподальное 3-накрытие Т{7)) или граф Доро на 65 вершинах диаметра 3.

Следующая теорема является аналогом результата, полученного в статье В. В. Кабанова [28] для редуцированных графов без 3-коклик.

Теорема 2.4. Пусть Г — связный редуцированный граф без 3-коклик, в котором каждый ц-подграф регулярен заданной степени, а > 0. Тогда Г сильно регулярен, или степень любой вершины из Г равна к или к — 1, подграф Г' на вершинах степени к является октаэдром, подграф на Г — Г' является 6-кликой и каждая вершина из Г — Г' смежна с 3-кликой из Г'.

Обратно, если Г — сильно регулярный граф без 3-коклик с параметрами (и, к, X, ц), то каждый //-подграф регулярен степени, а = 2А + 2 — к.

Следствие 2.2. Пусть Г — связный редуцированный граф без корон, в котором каждый ц-подграф реберно регулярен с заданными параметрами (V', к', А') и имеет диаметр 2. Тогда выполняется одно из следующих утверждений:

1) А' = 0, и Г совпадает с октаэдром или треугольным графом Т (5);

2) А' > 0, Г не содержит 3-коклик и является сильно регулярным графом с параметрами ((я2 + Зя)2, (б-2 + 2й — 1)(з2 + Зя + 1), (я + 2)(з3 + 2*2 -1),(82 + 2з){З2 + 2.5−1));

3) А' > 0, Г содержит 3-коклику и является графом Грассмана, графом Дэюонсона или его частным, локально треугольным графом или графом Госсетпа.

В параграфе 2.3 изучаются Графы без 3-корон с реберно регулярными //-подграфами. А именно, с помощью классификации графов без корон с регулярными /х-подграфами диаметра 2 степени, а > 0 (см. выше) в статье [55] были получены следующие две теоремы.

Теорема 2.5. Пусть Г — связный граф без 3-корон, в котором любой ц-подграф, А состоит из у' > 1 вершин, и |Л (ж)пА (у)| = А' > 0 для любых смежных вершин х, у Е А. Если окрестность некоторой вершины из Г является графом Тервиллигера, то Г является либо кликовым (А' + 2)-расширением т х п-решетки, либо графом Тервиллигера одного из следующих типов:

1) клиповое расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;

2) кликовое расширение графа А, где, А является объединением д-клики и 6 или <5 — 1 вершин степени 1, смежных с различными вершинами этой клики;

3) кликовое расширение графа икосаэдра или графа без 3-лап с ц = 1.

Теорема 2.6. Пусть Г — связный граф без 3-корон, в котором каждый у-подграф Д является реберно регулярным графом с параметрами (у1, к', А') и окрестностями вершин диаметра 2. Если 0 < Л' < к' — 1, то либо окрестности вершин в Г являются сильно регулярными графами без 3-коклик, либо Г — локально А-граф, где, А — один из следующих графов:

1) треугольный граф Т (п) (п > 6) или граф Шлефли;

2) частное графа Джонсона .7(10, 5) или половинный граф свернутого 10-куба;

3) граф Грассмана ,/2з (п, 2), где п > 4.

В параграфах 2.4 и 2.5 доказано несуществование локально /(10, 5) графов и графов, являющихся локально половинным графом свернутого 10-куба (см. [40, 54, 58]). Таким образом, можно исключить случай (2) из теоремы 2.6.

В параграфе 2.6 доказано, что связные компоненты /¿—подграфов в локально ,/9(п, 2) графах являются графами Джонсона /(6,3) или дополнительными графами к 4×4-решетке. В частности, д = 2. См. также [55].

Графы знакопеременных и квадратичных форм над полем порядка 2 являются вполне регулярными локально Грассмановыми графами с ц = 20 (см. [16]).

В параграфе 2.7 доказано, что если Г — вполне регулярный локально </2(п, 2) граф с ц = 16, то п = 4 и |Г| = 72 (см. [56]).

Следствие 2.4. Пусть Г — связный граф без 3-корон, в котором каждый ц-подграф, А является связным реберно регулярным графом с параметрами (у', к', Л') и окрестностями вершин диаметра 2. Если 0 < Л' < к' — 1, то выполняется одно из следующих утверждений:

1) либо Г является графом Шлефли или графом Госсета, либо граф Г имеет параметры ((г2+3г)2, г3+Зг2+г, 0, г2+г) для некоторого г > 1;

2) каждый ц-подграф является октаэдром, и Г — половинный граф ректаграфа с с-л — 3, являющийся локально треугольным графом;

3) Г является локально Грассмановым графом, и либо г) (л = 16, п = 4, и Г — антиподальный граф диаметра 3 на 72 вершинах, либо и) рь = 20, и если для любой вершины, а графа Г граф Г2(а) является регулярным степени 15 ¦2п~1 — 105, то Г имеет накрытие, являющееся графом АИ (п, 2) знакопеременных форм или графом С^иа (1(п — 1,2) квадратичных форм.

В параграфе 2.8 получено описание вполне регулярных локально 9(4,2) графов. См. статью [39].

Обобщенным четырехугольником порядка (б-, ?) называется частичная геометрия рС?1 ($,?). То есть, каждая прямая содержит 5 + 1 точку, каждая точка лежит на ?+1 прямой, и для любой прямой Ь и точки х? Ь существует единственная точка у? Ь, коллинеарная с х. Обобщенный четырехугольник порядка (в, ?) обозначается через ОЦ (з^). Геометрия СС}(з,{) однозначно восстанавливается по своему точечному графу. Мы будем обозначать точечный граф обобщенного четырехугольника порядка ?) также через.

Нетрудно понять, что граф не содержит корон. Следовательно, локально графы не содержат 3-корон. Так как^{-подграфы} в СС}(з^) являются (? + 1)-кокликами, то в локально графах /хподграфы не содержат треугольников и, следовательно, не удовлетворяют условиям теорем 2.5 и 2.6. Следующая теорема дает описание вполне регулярных локально СС^(4, 2) графов.

Теорема 2.11. Вполне регулярный локально С (^(4, 2)-граф является одним из следующих графов:

1) единственный сильно регулярный локально 0(^(4, 2)-граф с параметрами (126,45,12,18);

2) единственный дистанционно регулярный локально Сф (4, 2)-граф на 378 вершинах с массивом пересечений (45,32,12,1- 1, 6,32,45) (это 3-накрытие графа из пункта (1)/.

В главе 3 изучаются кореберно регулярные графы с [л = 2, у которых каждое ребро содержится в Ах или А2 треугольниках. Сделаны уточнения результатов [36]. См. работу [49].

Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров, А и ^ имеют жестко заданное строение. Так, непустой подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 из [31]). Для изучения подграфов неподвижных точек автоморфизмов сильно регулярных графов с (1 — 2 может быть полезна следующая теорема.

Теорема 3.1. Пусть, А — граф, в котором каждое ребро содержится в Х или А2 треугольниках, и подграф [и] П [го] является 2-кокликой для любых двух несмежных вершин и, т. Тогда либо Д — сильно регулярный граф, либо выполняются следующие утверждения:

1) граф Д регулярен степени к, окрестность любой вершины в, А является объединением х изолированных (Ах + 1)-клик и у изолированных (А2 + 1)-клик, число (А1 + 2)-клик в, А равно у (2(ук- 1) — к (к — А2 — 1)) (А1 + 1)(А1 + 2)(А2-А1) 5.

2) для связной компоненты? графа Л1, определенного на множе-сгпве вершин графа А, в котором вершины а, Ь смежны, только если они смеэ/сны в Д и |[а] П [6]| = Ах, выполняются утверждения: г) если х > 1, то? является вполне регулярным графом с параметрами (г>?, ж (Ах + 1), Ах, 2), п) если? содержит геодезический 4-путь аЬсде, то х > 4, и для и е? П [а] — £(а) имеем и) > 4, ш) если х — 2, то? является (Ах + 2) х (Ах + 2)-решеткой, а если х = 3, то? является графом диаметра 3, ги) если? — сильно регулярный граф), то любая связная компонента графа Л1 изоморфна ?, граф А*, определенный на множестве {£х, .,?,} связных компонент графа Л1, я = у/у^, в котором вершины £ги ?., смеэ/сны, если ] ф г, и некоторая вершина из £г смежна с единственной вершиной из является сильно регулярным с параметрами (в, у (А2 + 1), А2 + 2(г>£ — кя — 1), 2.

3) если у = 1, то либо х = 1 и, А является (Ах + 2) х (А2 + 2)-решеткой, либо х > 1 и выполняются утверждения: г) множество вершин графа, А можно представить в виде разбиения на? клик Си., Сь порядка А2 + 2, где = у/(Х2 + 2), и граф А°, определенный на множестве {Сх,., С^}, в котором клики С{ и С^ смеэ/сны, если ] Ф г и некоторая вершина из С смежна с вершиной из С^, является частичным четырехугольником с параметрами кА2−1,АХ, 2А2 + 4), гг) граф Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {:г (А1 + 1), (х — 1)(Л1 +1), 2(А2 + 1), 1- 1, 2, (х — 1)(Ах+1), а-(А1+1)}, и если Ах > 0, то А^+4а-(Ах+1) является квадратом.

Заметим, что для связной компоненты П графа Л2, определенного на множестве вершин графа Д, в котором вершины а, Ь смежны, только если они смежны в Д и |[а] П [6]| = А2, выполняются утверждения, аналогичные сформулированным в теореме. В случае х = 1 выполняется аналог утверждения (3), полученный заменой (у, А2) на (х, Ах) и обратно.

Для четного натурального числа ш через МР (и>) обозначим класс ре-берно регулярных графов Г с параметрами 6х = Зш/2 — 3, к = ш2 — Зи/2,.

Л = uj2 — Suj + 2, v = ш2, содержащих пару непересекающихся подграфов Qi и Г22, изоморфных КШХш/2, причем любая вершина из (из Г22) несмежна с единственной вершиной в каждой доле из Г22 (из fix), и для любого ребра {d, е} из fix подграф Г — (о?-1 U е1-) является ребром из Любой граф из МР{2) состоит из двух изолированных ребер, а граф из МР (4) изоморфен графу Клебша (сильно регулярному графу с параметрами (16,10,6,6)). По аналогии с листом Мебиуса, т-трапом Мебиуса назовем граф, полученный из графа вершин и ребер боковой поверхности m-призмы, разрезанием по боковому ребру, переворачиванием правой стороны на 180° и склеивания.

В теореме 1.4.3 из [12] доказано, что если Г — связный реберно регулярный граф с параметрами (v, А-, А), в котором, А > к + ½ — у/2к + 2 (равносильно к > b (b-[ + 3)/2 + 1), то Г — дополнительный граф для сильно регулярного графа с ц < 2. В следствии 2 из [36] (опирающемся на теорему 2 [36]) получено описание связных, реберно регулярных графов с к > b (bi + 3)/2 — 2. Однако, доказательство теоремы 2 в [36] некорректно (ошибка в доказательстве леммы 27), поэтому теорема 2 и следствие 2 из [36] нуждаются в уточнении. Скорректированная формулировка теоремы 2 из [36] имеет вид.

Теорема 3.2. Пусть Г — связный реберно регулярный граф с параметрами (v, к, А), в котором fi (u, w) = А или к — 7 для любых вершин u, w с d (u, w) = 2. Если для каэ/сдого ребра {a, b} подграф Г — (а1 U ¿-г1) состоит из двух смежных вершин, то выполняется одно из следующих утверждений:

1) диаметр Г больше 2, и Г получается удалением из полного двудольного графа Kk+, k+1 максимального паросочетания;

2) граф Г сильно регулярегь;

3) для вершины и 6 Г подграф {го 6 Г2(м) | ц (и, w) = к—7} является полным многодольным графом KyXs, s = ?1 + 2 — 7, 1 < 7 < 61, и для графа Л1, определенного на множестве вершин графа Г, в котором две вершины a, b смежны, только если они несмежны в Г и ц (а, b) = А, верны утверждения: г) если у = 1, то Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {ж, х — 1, 2s, 1- 1, 2, х — 1, х}, где х = Ь + 2 — ys, множество вершин графа Г можно представить в виде разбиения на t коклик Ci,., Ct (антиподальных классов) порядка s + l, где t = v/(s + 1), и антиподальное частное Г' является частичным четырехугольником с параметрами (t, b + 2 — s, 0, 2s + 2), гг) если Л1 имеет связную компоненту диаметра 2, то каждая связная компонента графа Лх является сильно регулярным графом с параметрами ((х2 + х + 2)/2, ж, 0, 2), где х = Ьг + 2 — ys = t2 + 1 для некоторого t не кратного 4, и граф Г*, определенный на множестве {Ei,., Е/} связных компонент графа Л1, I = 2v/(x2 + х + 2), в котором вершины Ej и Ej смежны, если j i и некоторая вершина из Е,-смежна с единственной вершиной из Еj, является сильно регулярным с параметрами (I, rs, s — 1 + х (х — 1)/2, х2 + х + 2).

Если выполняется утверждение (Зг) и Г' является полным двудольным графом, то Г б МР (ш), ш > 6, Ьх = Зш/2 — 3, к = и2 — Зи/2, s = uj/2 — nv = и2.

Скорректированная формулировка следствия 2 из [36] имеет вид.

Следствие 3.1. Пусть Г — неполный связный реберно регулярный граф с параметрами (v, к, Л). Если Л > к + ½-л/2к + 8 (равносильно 2к > b + 3O1 -4), то.

1) граф Г является п-угольником, п > 6, тривалентным графом без треугольников, реберным графом тривалентного графа без треугольников, графом икосаэдра, треугольным графом Т (6) или графом Клебша (во всех этих графах bi < 3), или.

2) граф Г является дополнительным к сильно регулярному графу с? < 2, или.

3) либо граф Г принадлежит МР (ш), ш = 6, 8, либо для графа, А = Г выполняется одно из следующих утверждений: г) граф, А разбивается дополнительными графами для 4-трапов Мебиуса <&i,., ФГгде г = v/8 и граф А* на множестве вершин {Фь ., Фг}, в котором вершины Ф¿и Фj смежны, если некоторая вершина из Фг смежна с вершиной из Фj в графе А, является сильно регулярным с параметрами (г>/8, t2 — 9,6,16), ut = 12 или 36, гг) граф, А можно представить в виде разбиения наЗх 3-решеток Q]. ,., Г2., где s = v/9, и граф Д° на множестве вершин {fui,., в котором вершины Qj и Clj смежны, если некоторая вершина из Qi смежна с вершиной из Qj в графе А, является сильно регулярным с параметрами (и/9,t2 — 7,8,18), ut — 7,14 или 28, ш) граф Л на множестве вершин графа А, в котором вершины u, w смежны, если они смежны в, А и |А (и) П Д (ги)| = 0, — дистанционно регулярный граф диаметра 4 либо имеющий массив пересечений {136,135, 6,1- 1,.

2,135,136} и являющийся антиподальным 4-накрытием сильно регулярного графа с параметрами (2432,136,0,8), либо имеющий массив пересечений {х, х — 1,4,1- 1, 2, х — 1, х} и являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((а-+2)(а-+3)/6, х, 0, 6).

В случае к = (й^+З&х)/2 в заключении следствия остаются п-угольник, граф икосаэдра, граф из МР (6) и дистанционно регулярный граф диаметра 4 с массивом пересечений {х, х — 1,4,1- 1,2, ж — 1, а-}, являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((хЬ 2)(а- + 3)/6,ж, 0, б), подтверждающие точность границы к > Ьу (Ь1 + 3)/2, дающей сильную регулярность графа.

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

В монографии П. Камерона [27] представлен метод Г. Хигмана, который дает необходимое условие существования автоморфизма дистанционно регулярного графа.

Пусть Г — дистанционно регулярный граф диаметра й. Подстановочное представление группы (? = Аг^ Г на вершинах графа Г дает матричное представление ф группы С? в С). Пространство Си является ортогональной прямой суммой собственных подпространств И’оФ- - -ФИ^ матрицы смежности, А графа Г. Для любого д Е С? матрица ф (д) перестановочна с А, поэтому подпространство И^- является 1/>(Сг)-инвариантным.

Пусть Хг~характер представления, полученного ограничением ф на IV,. Тогда г з=о где а^{д)—число вершин х из Г, таких что с1(х, х9) = ], а зависят от параметров Г.

Поскольку значения характеров — целые алгебраические числа, то в случае, когда значения С^^ рациональны, ХгО?) является целым числом. Отсюда получаем условие делимости для ] = 1,., с/. С помощью этого условия были получены новые ограничения для групп автоморфизмов сильно регулярных графов с параметрами (85,14,3, 2) (см. [60]) и (3250,57,0,1) (см. [52]). Эти результаты являются частью серии работ, посвященных изучению групп автоморфизмов сильно регулярных графов с малыми значениями Аид.

В параграфе 4.1 получены результаты о группе автоморфизмов сильно регулярного графа с параметрами (85,14,3,2).

Наименьшим примером сильно регулярного графа с параметрами (г*, к, 3, 2) является 5×5-решетка, имеющая параметры (25,8,3, 2). Следующим набором параметров сА = Зид = 2, для которого возможно существование сильно регулярного графа, является (85,14,3,2).

Теорема 4.1. Пусть V—сильно регулярный граф с параметрами (85,14,3,.

2). Тогда для любого автоморфизма g из Aut Г простого порядка р выполняется одно из следующих утверждений:

1) р 6 {5,17} и Fix g— пустой граф;

2) р = 7 и Fix <7 является 1 -кликой, или р = 5 и Fixg является 5-кликой;

3) р — Ъ, Fix<7 является четырехугольником или 2×5-решеткой, и в последнем случае для шести вершин из Fi xg их окрестности содержат точно две максимальных Ъ-клики;

4) р = 2, окрестность каждой вергиины из Fixg связна, Fixg является объединением ip изолированных вершин и ф изолгьрованных треугольников, причем либо ф = 1 и <р G {4, 6}, либо ф — 0 и ip = 5.

В параграфе 4.2 изучается группа автоморфизмов графа Мура степени 57 (графа Ашбахера).

Для регулярного графа степени к и диаметра d на v вершинах выполняется неравенство: v < 1 + к + к (к — 1) + • • - + к (к — l) d1.

Графы, для которых достигается равенство, называются графами Мура. Простейшим примером графа Мура служит (2d + 1)-угольник.

Дамерелл в статье [5] доказал, что граф Мура степени к > 3 имеет диаметр 2. В этом случае v — к2 +1, граф сильно регулярен с, А = 0 и ц, = 1, а степень к равна 3 (граф Петерсена), 7 (граф Хофмана-Синглтона) или 57. Существование графа Мура степени к = 57 неизвестно. Ашбахер в статье [4] показал, что граф Мура с к = 57 не является графом ранга 3. Мы будем называть грае}) Мура с к — 57 графом Ашбахера.

Пусть Г—граф Ашбахера, G = Aut Г. Ранее в работе [31] было доказано, что если G содержит инволюцию t, то G = 0(G)(t), и Fix t является 56-звездой. Приведенная ниже теорема не делает предположений о существовании инволюции.

Теорема 4.2. Пусть Т—граф Ашбахера и G = Aut Г. Тогда либо.

1) G содержит инволюцию t, и либо 0(G) — Р—силовская Ъ-подгруп-па из G порядка 125, |[Р, i]| = 25, Z (P) действует полурегулярно на Г, Fix (Cp (t)) —граф Хофмана-Синглтона, и Р содержит 25 подгрупп Ui порядка 5, имеющих пятгщгольник в качестве подграфа неподвио>сных точек, либо G = Y (t) х X, Y—циклическая группа, инвертируемая t, |У| делит 7,19,55, делит 7,25,27 или 55, и если X ф 1, то верно одно из утверждений: г) FiхХ-звезда, |Х| = 7 и Y = 1, ii) ¥-ixX—пятиугольник, делит 5, либо Fix ж— граф Хофмана-Синглтона для некоторого элемента х порядка 5 из X и Х: (ж)| G.

5,11}, либо Fix ж = FixX для любого неединичного элемента х из X и делит 55, in) FiъХ—граф Петерсена, Х делит 27, |У| делит 5 и если У ф 1, то Fix У является пустым графом, iv) FiхХ—граф Хофмана-Синглтоиа, Х делит 25, |У| делит 5 или 7, и если |У| = 5, то Fix У является пустым графом или пятиугольником, а если |У| = 7, то Fix У является звездой на 51 или на 16 вершинах либо.

2) |G| нечетен и верно одно из утверэ1сдений: г) 19 делит G, G — Ga для некоторой вершины а, и G —подгруппа из группы Фробениуса порядка 3219, гг) 13 делит либо G—подгруппа из циклической группы порядка 65 и каждый неединичиый элемент из G действует без неподвижных точек на Г, либо G—группа Фробениуса порядка 39,.

Иг) 11 делит |G|, G —расширение циклической группы порядка 11 с помощью элементарной абелевой группы U порядка, делящего 25, iv) 7 делит |G|, либо G—подгруппа прямого произведения циклической группы порядка 7 и элементарной абелевой группы U порядка, делящего 25, в случае U ф 1 подграф Fix U является графом Хофмана-Синглтона, либо G—группа Фробениуса порядка 21, v) 7r (G) С {3,5}, либо |G| делит 54, либо G—подгруппа из прямого произведения группы порядка 5 и группы порядка 27, либо G—группа Фробениуса порядка 75 или 543, либо Z (G) — Ь и G/Z (G) —группа Фробениуса порядка 75.

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

Предложение 4.1. Пусть Т—граф Ашбахера, д— автоморфизм простого порядка р графа Г, Q = Fix"?. Тогда выполняется одно из утверждений:

1) £1—пустой граф и р G {5,13};

2) Q—звезда на и вершинах и либо ш = 1 up— 19, либо ш — 56 и р — 2, либо ш — 58 — 7у для некоторого у < 8 и р = 7;

3) Q— пятиугольник и р & {5,11};

4) О,—граф Петерсена и р = 3;

5) О,—граф Хофмана-Синглтона и р = 5.

1. Pain S., Thas J.A. Finite Generalized Quadrangles. Boston: Pitman, 1984.

2. Caldebrank R., Kantor W.M. The geometry of two weight codes // Bull. London Math. Soc. 1986, v. 18, 97−122.

3. Blokhuis A., Brouwer A.E. On locally 4-by-4 grid graphs //J. Graph Theory, 1989, v. 13, № 2, p. 229−244.

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

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

6. Кабанов B.B. О графах без корон с регулярными /i-подграфами // Матем. заметки, 2000, т. 67, № 6, 874−881.

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

8. Makhnev A.A. On the graphs with //-subgraphs isomorphic to Kux2 // Proc. Steklov Inst. Math., Suppl. 2, 2001, p. 169−178.

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

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

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

12. Зарипов С. Р., Махнев A.A., Яблонко И. П. Реберно регулярные графы диаметра 2сА>2&-/3 — 2// Труды Украинского матем. конгресса, Киев 2001, секция 1: Алгебра и теория чисел, Институт математики HAH Украины, Киев 2003, 46−61.

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

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

15. Махнев A.A., Минакова И. М. Об автоморфизмах графов с, А = 1, ц = 2 // Дискрет, матем. 2004, т. 16, № 1, 95−104.

16. Махнев A.A., Носов B.B. Об автоморфизмах сильно регулярных графов с Л = 0, р = 2 // Матем. сборник 2004, т. 185, № 3, 47−68.

17. Белоусов И. Н., Махнев A.A. О почти хороших парах вершин в ре-берно регулярных графах // Изв. Урал. гос. ун-та, 2005, т. 36, № 3, с. 35−48.Публикации.

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

19. Paduchikh D.V. Non-existence of locally .7(10,5)-graphs // Укр. матем. конгресс 2001. Тез. докл. Киев, секция 1, с. 40.

20. Кабанов В. В., Махнев A.A., Падучих Д. В. О графах без корон с регулярными /¿—подграфами // Труды 33-й молодежной конф. ИММ УрО РАН. Екатеринбург 2002, с. 25−28.

21. Кабанов В. В., Махнев A.A., Падучих Д. В. Локальное строение графов без 3-корон с реберно регулярными //-подграфами // Международная конф. Алгебра и ее приложения, Красноярск 2002, с. 55−57.

22. Кабанов В. В., Махнев A.A., Падучих Д. В. О графах без корой с регулярными //-подграфами, II // Матем. заметки 2003, т. 74, с. 396 406.

23. Кабанов В. В., Махнев A.A., Падучих Д. В. О локально решетчатых подграфах в графах Грассмана // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, с. 149−151.

24. Махнев A.A., Падучих Д. В. О сильной регулярности некоторых реберно регулярных графов // Алгебра, логика и кибернетика. Тез. докл. Иркутск 2004, с. 181−183.

25. Махнев A.A., Падучих Д. В. Новая оценка для числа вершин реберно регулярных графов // Труды 36-й молодежной конф. ИММ УрО РАН. Екатеринбург 2005, с. 52−54.

26. Падучих Д. В. Об автоморфизмах сильно регулярного графа с параметрами (85,14,3,2) // Дискрет, матем. 2008, т. 20.