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

• Падучих, Дмитрий Викторович
• доктор физико-математических наук
• 2008

Оглавление диссертации доктор физико-математических наук Падучих, Дмитрий Викторович

1 Оценка для числа вершин в реберно регулярных графах

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

1.0.2 Хорошие пары в графах с к > ЗЬ\ — 2.

1.0.3 Доказательство теоремы 1.1 и следствия 1.1.

2 Графы без т-корон

2.1 Окрестности вершин — кликовые расширения решеток

2.1.1 Общие результаты.

2.1.2 Доказательство теоремы 2.2.

2.2 Графы без корон с регулярными //-подграфами.

2.2.1 Вспомогательные результаты.

2.2.2 Доказательство предложения 2.

2.2.3 Графы Тервиллигера без корон.

2.2.4 Редуцированные графы без 3-коклик.

2.3 Графы без 3-корон с реберно регулярными /х-подграфами

2.3.1 Вспомогательные результаты.

2.3.2 Доказательство теоремы 2.5 и предложения 2.

2.3.3 Локальная характеризация графов без 3-корон

2.3.4 Восстановление окрестностей

2.4 Несуществование локально /(10,5) графов.

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

2.4.2 Локально /(10,5) графы.

2.5 Окрестности вершин изоморфны половинному свернутому 10-кубу.

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

2.5.2 Доказательство теоремы 2.8.

2.6 //-подграфы в локально графах Грассмана.

2.6.1 Вспомогательные результаты.

2.6.2 Локально (д + 1)хт подграфы в графах Грассмана ^(4, 2).

2.6.3 Локально (q + 1) х (q + 1)-подграфы в графах Грассмана Jq(n, 2).

2.7 Вполне регулярный локально J2(n, 2) граф с ß =

2.8 Вполне регулярные расширения GQ(4,2).

2.8.1 Случай ц = 8.

2.8.2 Случай ц = 16.

2.8.3 О вполне регулярных антиподальных накрытиях клик

2.8.4 Случай ц = 12.

3 Кореберно регулярные графы с двумя значениями Л

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

3.2 Графы с двумя значениями Л, в которых /х-подграфы являются 2-кокликами.

3.3 Графы с Ai = 0.

4 Автоморфизмы дистанционно регулярных графов

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

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

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

4.1.3 Инволюхивные автоморфизмы графа с параметрами (85,14,3, 2)

4.1.4 Группа автоморфизмов графа с параметрами (85,14,3,2).

4.2 Автоморфизмы графа Ашбахера

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

4.2.2 Неподвижные точки автоморфизмов графа Ашбахера.

4.2.3 Группа автоморфизмов графа Ашбахера, четный случай

4.2.4 Группа автоморфизмов графа Ашбахера, нечетный случай.

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

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через с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, 3x3 решеткой, треугольным графом Т(т), т <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. Пусть Г — реберно регулярный граф, имеющий те о/се параметры (у,к,Х), что и один из следующих графов: полный многодольный граф КГХз, 3x3 решетка, треугольный граф Т{т), т < 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, и тройка (<V, Ь, г) равна {1+Рд,(1 + рд)д/(р +1), д) или (1 + /Зр, (1 + /Зр)р/ЦЗ +1), р), соответственно; в частности, /3 + 1 делит р(р — 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 <t <р;

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, А;, А), в котором А > к + 1/2 — у/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 = üj/2 — \nv = и2.

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

Следствие 3.1. Пусть Г — неполный связный реберно регулярный граф с параметрами (v, к, Л). Если Л > к + 1/2-л/2к + 8 (равносильно 2к > b\ + 3Ö1 -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, и граф Д° на множестве вершин {füi,., в котором вершины 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 является четырехугольником или 2x5-решеткой, и в последнем случае для шести вершин из 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.

Список литературы диссертационного исследования доктор физико-математических наук Падучих, Дмитрий Викторович, 2008 год

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, с. 396406.

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.