Оглавление
1 Оценка для числа вершин в реберно регулярных графах 20
1.0.1 Предварительные результаты..........................22
1.0.2 Хорошие пары в графах с к. > ЗЬ\ — 2................26
1.0.3 Доказательство теоремы 1.1 и следствия 1.1..........38
2 Графы без т-корон 41
2.1 Окрестности вершин — кликовые расширения решеток . . 42
2.1.1 Общие результаты....................................45
2.1.2 Доказательство теоремы 2.2..........................49
2.2 Графы без корон с регулярными д-нодграфамй..................52
2.2.1 Вспомогательные результаты..........................54
2.2.2 Доказательство предложения 2.1 .....................58
2.2.3 Графы Тсрвиллигера без корон........................59
2.2.4 Редуцированные графы без 3-коклик...................61
2.3 Графы без 3-корон с реберно регулярными д-подграфами . 63
2.3.1 Вспомогательные результаты..........................64
2.3.2 Доказательство теоремы 2.5 и предложения 2.2 ... 67
2.3.3 Локальная характеризация графов без 3-корон ... 70
2.3.4 Восстановление окрестностей ........................73
2.4 Несуществование локально .7(10,5) графов...................75
2.4.1 Предварительные результаты..........................76
2.4.2 Локально 7(10,5) графы..............................78
2.5 Окрестности вершин изоморфны половинному свернутому
10-кубу....................................................86
2.5.1 Пі>едварительньіе результаты........................86
2.5.2 Доказательство теоремы 2.8..........................89
2.6 д-подграфы в локально графах Грассмана.....................90
2.6.1 Вспомогательные результаты..........................91
2.6.2 Локально (</+1) х т подграфы в графах Грассмана
7,(4,2).............................................93
2
2.6.3 Локально (<? +1) х (д + 1)-подграфы в графах Грас-
смана ./7(п, 2)........................................96
2.7 Вполне регулярный локально ./2(71,2) граф с д = 16 .... 101
2.8 Вполне регулярные расширения (7ф(4,2).......................108
2.8.1 Случай у/ = 8........................................114
2.8.2 Случай /х = 16.......................................118
2.8.3 О вполне регулярных антинодальных накрытиях клик 119
2.8.4 Случай // = 12.......................................120
3 Кореберно регулярные графы с двумя значениями Л 128
3.1 Предварительные результаты .................................132
3.2 Графы с двумя значениями Л, в которых /4-подграфы являются 2-кокликами 135
3.3 Графы с Ах = 0..............................................145
4 Автоморфизмы дистанционно регулярных графов 151
4.1 Автоморфизмы сильно регулярного графа с параметрами
(85,14,3,2).................................................153
4.1.1 Предварительные результаты ...........................154
4.1.2 Характеры групп и автоморфизмы графов.................156
4.1.3 Инволютивные автомо])физмы графа с параметрами (85,14,3,2)..........................................161
4.1.4 Группа автоморфизмов графа с
параметрами (85,14,3,2)...............................179
4.2 Автоморфизмы графа Ашбахера ................................180
4.2.1 Предварительные результаты ...........................181
4.2.2 Неподвижные точки автоморфизмов графа Ашбахера................................................186
4.2.3 Группа автоморфизмов графа Ашбахера, четный случай ....................................................189
4.2.4 Группа автоморфизмов графа Ашбахера, нечетный случай..................................................194
3
Введение
Мы рассматриваем неориентированные графы без нетель и кратных ребер. Если а,Ь — вершины графа Г, то через (1(а, Ь) обозначается расстояние между а и 6, а через Г,(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины
а. Подграф ГДа) называется окрестностью вершины а и обозначается через [о]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром о.
Регулярным графом степени к называется Граф Г, такой что для любой вершины и € Г выполняется |Г(м)[ = к. Рсберно регулярным графом с параметрами (и, к, Л) называется регулярный грае}) степени к на и вершинах, любое ребро которого лежит точно в Л треугольниках. Вполне регулярным графом с параметрами (и, к, А, ц) называется реберио регулярный граф с параметрами (ц, /с, А), в котором любые две вершины и, и) € Г на расстоянии 2 имеют ровно /г общих соседей. Сильно регулярным графом с параметрами (и, Л, А,р) называется реберио регулярный граф с параметрами (у, к, А), в котором любые две несмежные вершины и, V) е Г имеют ровно // общих соседей.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии, и геометрии этого класса можно классифицировать. Например, класс билдингов Титса характеризует группы Лиевского типа (1|.
Пусть (7 — транзитивная группа подстановок на множестве П. Если стабилизатор С7Р точки р £ П имеет г орбит, то говорят, что С—группа ранга г. Пусть г = 3 и соответствующие 3 орбиты—это {р},ГхО?), Гг(р). Если Гх(р) и Гг(р) содержат разное число элементов, то на множестве П можно построить сильно регулярный граф Г. Для этого положим, что точка р смежна со всеми точками из ГДр), и для каждого д С б? точка р9 смежна со всеми точками из ГДр)17. Если вместо Г](р) здесь взять Г2(р),
•1
то мы получим дополнительный сильно регулярный граф.
Д. Хигман (см. [2, 3|) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов и действуют транзитивно на множестве {(г/,?/;) | и,%и € Г и с!(и,ги) = г} для любого і < 2. То есть, такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра д называется дистанционно транзитивным, если для любого і Є {(),..., (і) группа Лиі Г действует транзитивно на {(и, и?) \ и, го € Г и д.(и,іо) = і}.
Дистанционно регулярным графом с массивом пересечений (Ь{),. 6^-1«Сі,...,са) называется граф диаметра <1, в котором для любых вершин и, го Є Г, находящихся на расстоянии і, подграф Г(гс) содержит ровно Ьі вершин, находящихся на расстоянии г + 1 от и, и ровно с,- вершин. находящихся на расстоянии г — 1 от и. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы и к дистанционно транзитивным графам.
Заметим, что сильно регулярный граф с /х > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с (I >
2—вполне регулярным графом с к = &о, Л = к - Ьі - 1 и ц = ог.
Пусть задан класс графов Т. Мы скажем, что граф Г является локально Т-графом, если для любой вершины а € Г имеем Г(а) Є Т. Тогда можно поставить задачу описания локально ^-графов. Если граф Г вершинно транзитивен, то окрестности всех его вершин изоморфны, и граф Г является локально Т графом, где Т состоит из графов, изоморфных некоторому графу А. В этом случае назовем Г локально А-графом. В более общем случае Т может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов—это в точности класс связных, локально регулярных графов.
Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально А графов.
Пусть М и ЛГ—конечные множества порядка т и п, соответственно. Два элемента из М х Лг будем считать смежными, если они различаются точно в одной координате. Полученный граф называется гп х п-решеткой; при га = п он сильно регулярен с параметрами (п2. 2(п —
1),п-2,2).
Треугольным графом Т(п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда,
5
когда они пересекаются в точности но одной точке. Граф Т(п) также сильно регулярен н имеет параметры (п(п—1)/2,2(п—2), 7г—2,4). Окрестность каждой вершины в Т(п) изоморфна 2х{п- 2)-решстке, т.е. Т{п)— локально 2 х (zi — 2)-реніетка.
Единственный сильно регулярный граф с параметрами (27,10,10,8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10,6,0) называется графом Клебша. Граф Шлефли является локально графом Клебша.
В главе 1 (см. также (51]) получена новая оценка для числа вершин в реберно регулярных графах. В [12, лемма 4.2.1] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (г;,/с, Л), в котором к > ЗЬі, то диаметр Г равен 2 и выполняется неравенство
kbi > (v - к — 1)(к - 2Ь\ 4-1).
Полученные в главе 1 результаты позволяют уточнить эту оценку.
Пусть о, Ь — вершины графа Г. Число вершин в [а] П [6] обозначим через Л(а, 6) (через р{а,Ь)), если d(a,b) = 1 (если d{a,b) — 2), а соответствующий подграф назовем Х-подграфом {р-подграфом).
Пусть Г — реберно регулярный граф с параметрами (и, к, Л) и Ь\ = А* — Л — 1. Пара вершин и, w называется хорошей {почти хорошей), если d(u,xu) = 2 и p{u,w) равно к — 2bi 4 1 (равно к — 2bi 4 2). Тройка вершин {u\w,z) называется хорошей {почти хорошей), если w,z € Г2(гг) и р{и, w) 4 p{u,z) не больше 2к - ЛЬ\ 4 3 (равно 2к — 4&i 4 4).
Через Kmy,...tin„ обозначим полный n-дольпый граф, с долями порядков т\,...,тпн. Если ту = ... = zпп = т, то соответствующий граф обозначается через КПхт• Граф К ід называется 3-лапой.
Если вершины и, w находятся на расст оянии і в Г, то через b,{u,w) (через Ci(u, w)) обозначим число вершин в пересечении Г,+і(а) (пересечении Гі_і(а)) с [щ]. Заметим, что в реберно регулярном графе с параметрами (г»,/г, А) значение bi(u,w) не зависит от выбора ребра {гг, г/;} и равно к — А — 1.
Теорема 1.1. Пусть Г — связный неполный реберно регулярный граф) с параметрами (г;, к, А) и к > ЗІ)і — 2. Тогда выполняется одно из следующих утвер'ждепий:
(1) для любой вершины w верно неравенство |Г2(ш)|(А; — 26x42) < kbi;
(2) для любой вершины w верно неравенство |Г2(и;)|(А; — 2bi 42) > kb\ и либо Г является реберным графюлі тривалентного графа без треугольников (т.е. к = 4, А = \) и диаметр графа Г больше 2, либо Г является п-угольником, п > о, или графом икосаэдра;
6
(3) Г является полным многодельным графом Кгх2, 3x3 решеткой, треугольным графом Т(т), т < 7, графом Клебша или графом Шлефли и для любой вершины ги верно равенство |Гг(г«)|(А: — 2Ь\ + 2) = кЬ\.
Доказательство утверждения (2) теоремы из [33) некорректно (не доказано утверждение (3) из [33, лемма 3.3)). Следующий результат уточняет данное утверждение.
Предложение 1.1. Пусть Г — связный реберно регулярный граф диаметра 2 с параметрами (у, к, Л) и к = ЗЬ\ + 6, 5 > —2. Тогда выполняются следующие утверждения:
(1) если Г содерэюит такую 3-коклику А, что любые ее две вершины образуют хорошие пары, то 6 = — 1 и Г является шестиугольником, графом икосаэдра или реберным графом тривалентного графа без треугольников, имеющим диаметр больше 2;
(2) если 6 > 0 и для некоторой вершины ги подграф Г2(ю) содерэюит две вершины, образующие хорошие пары с ш, то д < Ь\/2 — 2;
(3) если для некоторой вершины ю подграф Г2(?о) содерэюит три вершины ф,и,г, образующие хорошие поры с гх, то 5 = —2, у — к — 1 = 2&і + 2, Ь\(Ьі - 1) делится па 3, подграф {/, и, г} является кликой, для х Є {/, и, г} подграф Г2(ш) П 1*2(3:) содержит две вершини х',х", для различных вершин т., у Є {/, и, г} подграф [го] П [гг] П [у\ содержит единственную вершину ху, граф {/и, иг, /г] является кликой и |[го] — ([/] и [и] и Ы)| = 4;
(4) если для некоторой вершины ш подграф Г2(г/;) содерэюит четыре вершины, {и, г./, у], образующие хорошие пары с ги, то = 6, к = 16, А = 9, ?; = 31, подграф {гг., г,/,у} является кликой и 11(10, у) > 7 для любой вершины у из Г2 (•?/;) - {гг, г./, у}.
Имеется немного результатов о единственности сильно регулярного графа с данными параметрами {у, к, А, р). В качестве следствия теоремы
1.1 получена единственность некоторых реберно регулярных графов с данными параметрами {у, к, А).
Следствие 1.1. Пусть Г — реберно регулярный граф, имеющий те эюе параметры (у. к, А), что и один из следующих граф)ов: полный много-дольный граф /ГГХв, 3 х 3 решетка, треугольный граф Т(т), т < 7, граф) Клебша или граф Шлефли. Тогда Г изоморфен соответствующему графу.
Глава 2 посвящена изучению графов без т-корон.
Граф с т долями порядка 1 называется т-коропой. При т = 1
и т ~ 2 будем называть т-корону 3-лапой и короной, соответственно. Понятно, что т-корона получается из (т — 1)-короны добавлением одной
7
вершины, смежной со всеми остальными вершинами. Поэтому граф без то-корон—это в точности граф локально без (т - 1)-корон.
Пусть V является n-мерным векторным пространством над полем GF(q). Два m-мернмх подпространства из V будем считать смежными, если они пересекаются но (т — 1)-мерному подпространству. Граф на множестве всех га-мерных подпространств V с такой смежностью называется графом Грассмана и обозначается через Jq(n,m). При т = 2 граф Грассмана сильно регулярен. Граф Грассмана Jq(n,m) не содержит (индуцированных) корон.
В параграфе 2.1 изучаются сильно регулярные графы, у которых окрестность каждой вершины является кликовым ^-расширением р х </-решетки. Интерес к таким графам был вызван тем, что при изучении графов без корон, в которых /i-подграфы являются регулярными графами заданной положительной степени (см. |28, 43|) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым /^-расширением р х <7-решетки.
Теорема 2.1. Пусть Г — сильно регулярный граф с отрицательным собственным значением —т, в котором окрестность каждой вершины является, кликовым fi-расширением р х q-решетки, 2 < р < q. Тогда выполняются следующие утверждения:
(1) число вершин в максимальной клике L графа Г равно \ + fiq или 1 4 fip, и (L,B) является (и,Ь,т,к,\)-схемой, где В — множество сингулярных прямых графа Г, лежащих в L, к = fi + 1, А = 1, и тройка {v,b, г) равна (1 A-fiq, (1 +fiq)q/(fi 4 1). q) или (1 + fip, (l+fip)p/(fi + l),p), соответственно; в частности, 5+1 делит р(р — 1) и q(q — 1);
(2) если р < q, то число (1 4 fiq)-клик в граф)е Г равно pv/(l + fiq), и 1 4 fiq делит р(р — 1)(р — р41), а число (1 4- fip)-клик равно qv/(l 4 fip), и 1 4 fip делит q(q - 1)(д - <7 4 1), если р = q, то 1 4 fip делит 2(р -t)(p -1,04 1)(р 4 1,0-1);
(3) для двух несмежных вершин а, b любая строка (любой столбец) решетки, отвечающей [а], содержит 0 или fi 4 1 вершин из [6], и р = t(fi 4 1), где fi 4 1 < t < р;
(4) если t = fi 4 1, то [а] П [6] является t х t-решеткой, и Г является треугольным графом Т(т) (т > А), графом .7(10,5) или графом Грассмана Jt-i(n,2), п > 4;
(5) если 7п — р — и, то t < р — и, причем равенство достигается лишь при и = 0; в частности, 1фр — 1, и если t = р — 2, то т = р — I, (2fi 4 1 ){р - 2) = fi(q - 1), и fi 4 1 делит 2(р — 1, q);
(6) если t - р, то т = р, и
8
(г) Г является псевдогеометрическим графим для pGfl+i((3q,p — 1), и (fiq -f р - р - 1)(/3 + 1) делит р{р - 1 )0q{Pq + 1),
(гг) если р < q, то Г является геометрическим графом, и каждый р-подграф в графе прямых данной геометрии является объединением непересекающихся ({3 + 1) х (/? +1)-решеток, ft + 1 делит q — 1, ир/3-ь 1 делит q(q - l)(fiq + 1);
(ггг) если р = q, то (/3 Н- I)2 делит р2{р(3 +1).
Заметим, что если Г — псевдогеометрический граф для pG?(p,p — 1), являющийся локально р х р-графом, то Г — дополнительный граф для 4 х 4-решетки в случае р = 3 и граф .7(8.4) п случае р = 4 (отсюда следует изоморфизм .7(8,4) и дополнительного графа для графа Грассмана 72(4,2)).
В теореме 2 из 117) была получена классификация сильно регулярных локально р х (/-графов с 2 < р < q и р < G. Следующая теорема распространяет этот результат на графы, в которых окрестности вершин являются клиновыми расширениями р х (/-решетки.
Теорема 2.2. Пусть Г — сильно регулярный граф, в котором окрестность каждой вершины является кликовым (3-расширением pxq-решетки, 2 < V < </- Если р < G, то выполняется одно из следующих утверждений:
(1) £ = р - 1, и Г является графом Грассмана Jp-\[n, 2);
(2) [3 = р - 2, и либо Г имеет параметры второй окрестности вершины в графе Грассмана ./p~i(4,2), либо является точечным графом частичной геометрии pGp-\((p — 2)q,p — 1), р — 1 делит q — 1;
(3) Д = 2, и Г является псевдогеометрическим графом для частичной геометрии рС73(12,5);
(4) f3 = 1, и Г является либо треугольным графом T(q + 2), либо дополнительным графом для 4 х 4-решетки, г]шфом .7(8,4) или .7(10, 5), либо псевдогеометрическим графом для частичной геометрии pG2(6,5).
В параграфе 2.2 изучаются графы Тервиллигера без корон и графы без 3-коклик с регулярными д-подграфами (см. также |43|).
Пусть а1 — шар радиуса 1 с центром а. Для подграфа А графа Г через А1 обозначим Паєл0"1"- Граф Г назовем слабо редуцированным, если из равенства а1 = Ь~ следует а = Ь. Граф Г назовем редуцированным. если из включения а1 С &1 следует а = 6. Через Гх обозначим подграф на множестве всех вершин а таких, что ftх = Г.
М. Нумата [14) получил классификацию графов без корон, в которых д-подграфы являются изоморфными реберно регулярными графами диаметра 2 (естественно, не имеющими 3-лап). В связи с этим ре-
9
зультатом представляет интерес изучение графов, в кагорых каждый д-подграф является реберно регулярным графом без 3-лап с заданными параметрами (г/, /с', Л').
В статье В.В.Кабанова [28| было получено следующее обобщение результата Ну маты, опирающееся на более ранние работы A.A. Махпева и В.В. Кабанова:
Связный редуцированный граф без корон, содержащий 3-коклику, в котором д подграфы регулярны заданной степени а > 0 и имеют диаметр 2, является графом Грассмаиа, графом Джонсона или его частным, локально треугольным графом или графом Госсста.
Важным этаном в доказательстве этого результата стала лемма 2.1 |28|, в которой доказано, что слабо редуцированный граф без 3-лап, содержащий 3-коклику, в котором д-иодграфы регулярны заданной положительной степени, является редуцированным.
Предложение 2.1. Если Г — связный слабо редуцированный ?.]кіф без 3-коклик, в котором р-подграфы регулярны степени а > 0, то Г является редуцированным графом ггли пятиугольной пирамидой.
В статье A.A. Махнева и В.В. Кабанова (25] было доказано, что если Г—связный граф Тервиллигера без 3-лап, то либо Г является кликовым расширением графа икосаэдра, либо подграф, индуцированный на множестве всех вершин из Г — rL с некликовымн окрестностями, является кликовым расширением пустого графа, клики или графа с д = 1.
Теорема 2.3. Пусть Г — связный граф) Тервиллигера без корон, Г' — подграф на множестве вершин с некликовыми окрестностями. Тогда выполняется одно из следующих утверждений:
(1) Г не содержит 3-коклик и является кликовым расширением 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;
(2) Г не содероісит 3-лап, но содержит 3-коклику, диаметр Г больше 2, и либо
(г) Г является кликовым расширением графа икосаэдра, либо
(и) Г' является кликой, и Г является кликовым расширением графа. Д, где Д содержит 6-клику и 6 или (5—1 вершин степени 1, смежных с различными вершинами клики, либо
(гіг) Г' является кликовым расширением графа с д = 1;
(3) Г содержит 3-лапу, д = 1, и окрестность любой вершины из Г состоит из изолированных клик.
Следствие 2.1. Пусть Г — связный граф), в котором окрестности вершин являются регулярными графами Тервиллигера диаметра 2. Если окрестность некоторой вершины не содерэ/сгпп корон и 3-коклик, то
10
либо Г явлжзпся кликовым расширением пятиугольника или графа икосаэдра, либо Г — локально граф Петерсена, т.е. граф Т(7), граф Конвея-Смит па 63 вершинах диаметра 4 (это аптиподальпое 3-пакрытиеТ(7)) или граф) Доро на 65 вершинах диаметра 3.
Следующая теорема является аналогом результата, полученной) в статье В.В. Кабанова |28| для редуцированных графов без 3-коклик.
Теорема 2.4. Пусть Г — связный редуцированный граф) без 3-коклик, в котором каждый р-подграф регулярен заданной степени а > 0. Тогда Г сильно регулярен, или степень любой вершины из Г равна к или к — 1, подграф) Г' на вершинах степени к является октаэдром, подграф на Г — Г' является 6-кликой и каждая вершина из Г - Г' смежна с 3-кликой из Г'.
Обратно, если Г — сил),но регулярный граф без 3-коклик с параметрами (и,к,\,р), то каждый д-подграф регулярен степени о = 2А + 2-к.
Следствие 2.2. Пусть Г — связный редуцированный граф) без корон, в котором каждый р-подграф) реберпо регулярен с заданными параметрами (*/, к\ А') и имеет диаметр 2. Тогда выполняется одно из следующих утверждений:
(1) А' = 0, и Г совпадает с октаэдром или треугольным графом Т(5);
(2) А' > 0, Г не содержит 3-коклик и является сильно регулярным графом с параметрами (($2 + Зв)2, (ь2 + 25 - 1)(в2 -1- 35 + 1), (5 4- 2)(я3 + 2з2 - 1), (52 -I- 25)(я2 + 2.9 - 1));
(3) А' > 0, Г содержит 3-коклику и является графом Гроссмана, графом Джонсона или его частным, локально треугольным графом или графом Госсета.
В параграфе 2.3 изучаются Графы без 3-корон с реберно [Югулярными //-подграфами. А именно, с помощью классификации графов без корон с регулярными //-подграфами диаметра 2 степени а > 0 (см. выше) в статье |55) были получены следующие две теоремы.
Теорема 2.5. Пусть Г — связный граф без 3-корон, в котором любой р-подграф Д состоит из и' > I вершин, и |Д(х)П Д(?/)| = А' > 0 для любых смежных вершин х,у 6 Д. Если окрестность некоторой вершины из Г является графом Тервиллигера, то Г является либо кликовым (А' +
2)-расширением тп х п-решетки, либо графом Тервиллигера одного из следующих типов:
(I) кликовос расширение 2-пути, 3-пути, пятиугольника или пятиугольной пирамиды;
11
(2) кликовое ]місширеііие графа Д, где Д является объединением 5-клики и 6 или 6—1 вершин степени 1, смежных с различными вершинами этой клики;
(3) кликовое расширение графа икосаэдра или графа без 3 -лап ср. — 1.
Теорема 2.6. Пусті* Г — связный граф без 3-корон, в котором каэ/с-дый р-подграф Д является реберно регулярным графом с параметрами (и\ к', А') и окрестностями вершин диаметра 2. Если 0 < А' < к1 — 1, то либо окрестности вершин в Г являются сильно регулярными графами бе;і 3-коклик, либо Г — локально А-граф, где Д — один из следующих графов:
(1) треугольный граф) Т(п) (п > 6) или граф Шлсфли;
(2) частное графю. Джонсона .7(10, 5) или половинный граф свернутого 10-куба;
(3) граф) Гроссмана «ТгДя, 2), где п > 4.
В параграфах 2.4 и 2.5 доказано несуществование локально .7(10,5) графов и графов, являющихся локально половинным графом свернутого 10-куба (см. [40, 54, 58|). Таким образом, можно исключить случай (2) из теоремы 2.С.
В параграфе 2.6 доказано, что связные компоненты /х-подграфов в локально УДп, 2) графах являются графами Джонсона .7(6,3) или дополнительными графами к 4 х 4-решетке. В частности, у — 2. См. также |55|.
Графы знакопеременных и квадратичных форм над нолем порядка 2 являются вполне регулярными локально Грассмановыми графами с р = 20 (см. [16]).
В параграфе 2.7 доказано, что если Г — вполне регулярный локально «/2(71,2) граф с р = 16, то п = 4 и |Г| = 72 (см. [56]).
Следствие 2.4. Пусть Г — связный граф без 3-корон, в котором каждый р-подграф) Д является связным реберно регулярным графом с параметрами (?/, к\ Л') и окрестностями вершин диаметра 2. Если 0 < Л' < к’ — I, то выполняется одно из следующих утверждений:
(1) либо Г является графом Шлсфли или графом Госсета, либо граф Г имеет параметры ((г2+Зг)2,г3+Зг2+г, 0, г2+г) для некоторого г > 1;
(2) каждый р-подграф) является октаэдром, и Г — половинный граф ректаграфа с сз = 3, являющийся локально треугольным графом;
(3) Г является локально Грассмаповым графом, и либо
(г) р = 16, п — 4, и Г — аптиподальпый граф диаметра 3 на 72 вершинах, либо
(гг) /і = 20, и если для любой вершины а графю, Г граф Га (а) является регулярным степени 15 •2"”1 — 105, то Г имеет накрытие, являю-
12
щееся графом АИ(п, 2) знакопеременных форм или графом (}иа.(і(п— 1,2) квадратичних форм.
В параграфе 2.8 получено описание вполне регулярных локально <7ф(4,2) графов. См. статью [39].
Обобщенным четырехугольником порядка (я, £) называется частичная геометрии рО 1(5,0* 1° есть, каждая прямая содержит .9 + 1 точку, каждая точка лежит на £+1 прямой, и для любой прямой Ь и точки х Ь существует единственная точка у € Ь. коллинеарная с х. Обобщенный четырехугольник порядка (5,1) обозначается через С(2(я,1). Геометрия СС^{в,І) однозначно восстанавливается по своему точечному графу. Мы будем обозначать точечный граф обобщенного четырехугольника порядка ($,£) также через ССЛ«. і).
Нетрудно понять, что граф ССЛ-М) не содержит корон. Следовательно, локально ОС2(в,1) графы не содержат 3-корон. Так как //-подграфы в (762(5, і) являются (і + 1)-кокликами, то в локально (7(2(5,^) графах //-подграфы не содержат треугольников и, следовательно, не удовлетворяют условиям теорем 2.5 и 2.6. Следующая теорема дает описание вполне регулярных локально ОС2(4,2) графов.
Теорема 2.11. Вполне регулярный локально <7(2(4,2)-граф является одним из следующих графов:
(1) единственный сильно регулярный локально (7(2(4,2)-граф с параметрами (126,45,12,18);
(2) единственный дистанционно регулярный локально (7(2(4, 2)-граф) па 378 вершинах с массивом пересечений (45,32,12,1; 1,6,32,45) (это
3-накрытие графа из пункта (1)2.
В главе 3 изучаются кореберно регулярные графы с р — 2, у которых каждое ребро содержится в Аі или А2 треугольниках. Сделаны уточнения результатов [36]. См. работу [49).
Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров Аид имеют жестко заданное строение. Так, непустой подграф неподвижных точек автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 из [311). Для изучения подграфов неподвижных точек автоморфизмов сильно регулярных графов с р = 2 может быть полезна следующая теорема.
Теорема 3.1. Пусть Д — граф, в котором каждое ребро содержится в Аі или А2 треугольниках, и подграф [а] Л [їй] является 2-кокликой для любых двух несмежных вершин и, ш. Тогда либо Д — сильно регулярный граф, либо выполняются следующие утверждения:
13
(1) граф А регулярен степени к, окрестность любой вершины в Д является объединением х изолированных (Аі 4 \)-клик и у изолированных, (А2 4- 1)-клше, число (Лі -\* 2)-клик в Д равно
и(2(у - к - 1) - к(к - А2 - 1))
(Аі 4- 1)(А| 4 2)(А2 — Аі)
(2) для связной компоненты Е графа А1, определенного на множестве вершин графа Д, в котором вершины а, Ь смежны, только если они СМС01СНЫ в А и ||а] П [Ь]\ = Аі, выполняются утверждения:
(г) если х > 1, то Е является вполне регулярным графом с пара-метрами (у£,х(Х\ 4 1), Аь2),
(и) если Е содержит геодезический 4-путь аЬсде, то х > 4, и для и Є Е П (а] — Е(а) имеем и) > 4,
(т) если х = 2, то £ является (Аі 42) х (А! 4 2)-решеткой, а если х -■ 3, то Е является графом диаметра 3,
(»,•) если Е — сильно регулярный граф), то любая связная компонента графа А1 изоморфна Е, граф А*, определенный па множестве {£!,...,£*} связных компонент графа Л1, а* = у/у-ц, в котором вершины £; и llj смежны, если у ф г, и некоторая вершина из Е, смежна с единственной вершиной из является сильно регулярным с параметрами (е, у(А2 4 1), А2 4 2(у>: - к>: - 1), 2у1:);
(3) если у = 1, то либо х = 1 и А является (Аі 4 2) х (А2 4 2)-решеткой, либо х > 1 и выполняются утверждения:
(г) м)южество вершин графа А мооіспо представить в виде разбиения па £ клик Сі,...,Сі порядка А2 4 2, где £ = у/{А2 4 2), и граф А°, определенный па множестве {Сі,..., С*}, в котором клики С, и С^ смео/сны, если д Ф і и некоторая вершина из Сі смежна с вершиной из Су, является частичным четырехугольником с параметрами (£, к — А2 — 1, Аі, 2А2 4 4),
(и) граф А1 является дистанционно регулярным графом диаметра А с массивом пересечений {гс(Аі 41), (х —1)(Аі4І), 2{А241), 1; 1,2, (ж —
1)(Аі4і),ж(Аі4і)}, и если \\ > 0, то А244а;(А]41) является квадратом.
Заметим, что для связной компоненты П графа Л'2, определенной) на множестве вершин графа Д, в котором вершины а, Ь смежны, только если они смежны в Д и |[а] П [6]| = А2, выполняются утверждения, аналогичные сформулированным в теореме. В случае х = 1 выполняется аналог утверждения (3), полученный заменой (т/,А2) па (х,Аі) и обратно.
Для четного натурального числа из через МР(из) обозначим класс реберно регулярных графов Г с параметрами Ьі = Зш/2 — 3, к = из2 — Ъиз/2,
14
Л = и2 — Зш + 2, у = ш2у содержащих пару непсресекающихся подграфов Сії и 122, изоморфных Кшхш/2, причем любая вершина из Г2і (из Г22) несмежна с единственной вершиной в каждой доле из П2 (из £2і), и для любого ребра {б/, с} из £2і подграф Г — ((Iі и е1) является ребром из Г22* Любой граф из МР{2) состоит из двух изолированных ребер, а граф из МР(4) изоморфен графу Клебша (сильно регулярному графу с параметрами (16,10,6,6)). 11о аналогии с листом Мебиуса, т-трапом Мебиуса назовем граф, полученный из графа вершин и ребер боковой поверхности т-призмы, разрезанием по боковому ребру, переворачиванием правой стороны на 180° и склеивания.
В теореме 1.4.3 из [12| доказано, что если Г — связный реберно регу-лярный граф с параметрами (у, к, А), в котором А > к + 1/2 — \/2к 4 2 (равносильно к > Ь\(Ь] 4 3)/2 4- 1), то Г — дополнительный граф для сильно регулярного графа с ц < 2. В следствии 2 из |36| (опирающемся на теорему 2 (36|) получено описание связных, реберно регулярных графов с к > Ь[ (Ьі 4 3)/2 — 2. Однако, доказательство теоремы 2 в (36] некорректно (ошибка в доказательстве леммы 27), поэтому теорема 2 и следствие 2 из |36) нуждаются в уточнении. Скорректированная формулировка теоремы 2 из |36| имеет вид
Теорема 3.2. Пусть Г связный реберно регулярный граф с параметрами (у, к, А), в котором р(и,ш) = А или к — 7 для любых вершин и, ги с сі(и,ю) = 2. Если для каоїсдого ребра {я,Ь} подграф Г - (а1 и Ь1) состоит из двух смежных вершин, тпо выполняется одно из следующих ут вержде 11-ий:
(1) диаметр Г больше 2, и Г получается удалением из полного двудольного графа К^+і^+і максимального паросочетапия;
(2) граф Г сильно регулярен;
(3) для вершины и Є Г подграф {ш Є Г2(и) | ц(и. ш) = к—-у} является полным мпогодольным графом Кухя, з = Ьі 4 2 — 7, 1 < у < и для г;хіфа Л1, определенного на множестве вершин графа Г, в котором две вершимы а,Ь смежны., только если они несмежны г? ]' м р{а,Ь) = А, верны утверждения:
(і.) если у = 1, то Л1 является дистанционно регулярным графом диаметра 4 с массивом пересечений {я?, х — 1,2я, 1; 1,2, х — 1, х], где х— 6] + 2 — уз, множество вершин графа Г можно представить в вида разбиения па і коклик С\,..., С\ (антпподальных классов) порядка в 4-1, где £ = у/(в 4 1), и антиподалъное частное V является частичным четырехугольником с параметрами (£, 61 4 2 — в, 0,2а* 4 2),
(м) если Л1 имеет связную компоненту диаметра 2, то каэ/сдая связная компонента граіфа А.г является сильно регулярным графом с
15
параметрами ((ге2 + х + 2)/2,х,0,2), где х = Ь\ 4- 2 — у я = 4- 1 для
некоторого і не кратного 4, и граф Г*, определенный на множестве {Еі,.. •, Е/} связных компонент граф а Л1, І = 2и/(х2 + ї + 2), в котором вершины Е, и 52 j смежны, если ^ ^ і и некоторая вершина из Е,-смежна с единственной вершиной из 52является сильно регулярным с параметрами (/, г я, в — 14- х(х — 1)/2,ж2 4- х 4- 2).
Если выполняется утверждение (Зг) и Г' является полным двудольным графом, то Г € МР(ш), со > б, Ь\ = Зса/2 — 3, к. = су2 — Зи/2, 5 = Сс?/2 — 1 и V = и1.
Скорректированная формулировка следствия 2 из [36] имеет вид
Следствие 3.1. Пусть Г — неполный связный реберно регулярный граф с параметрами (у, А:, А). Если А > /с 4- 1/2 — у/2к -I 8 (равносильно 2к > Ь'2 4- З&і — 4), то
(1) граф Г является п-уголъником, п > 6, тривалентним графом без треугольников, реберным графом тривалентного графа без треугольников, графом икосаэдра, треугольным графом Т(6) или графом Клебша (во всех этих графах Ь{ < 3), или
(2) граф Г является дополнительным к сильно регулярному графу с Д < 2, или
(3) либо граф Г принадлежит МР(ш), и) = 6,8, либо для графа Д = Г выполняется одно из следующих утверждений:
(г) граф) Д разбивается дополнительными графами для 4-трапов Мебиуса Фі,..., ФГ, где г = у/8 и граф) А* па множестве вершин {Фі,..., Фг}, в котором вершины Ф,- и Фj смеэюны, если некоторая вершина из Ф, смежна с вершиной из Фj в графе Д, является сильно регулярным с параметрами (у/8, і2 — 9,6,16), и А = 12 или 36,
(й) граф) Д можно представить в виде разбиения па 3 х 8-решеток , Пя, где в = у/9, и граф А° на множестве вершин {І2і,..., П,}, в котором вершины ^ и ^ смежны, если некотощя вершина из Г2, смеэ/сна с вершиной из $2^ в графе Д, является сильно регулярным с параметрами (и/9, — 8,18), и А = 7,14 или 28,
(гіг) граф) А па множестве вершин графа Д, в котором вершины и, и) смежны, если они смежны в А и (Д(гг) П Д(г/;)| = 0, — дистанционно регулярный граф) диаметра 4 либо имеющий массив пересечений {136,135,6,1; 1,
2,135,136} и являющийся антиподальным 4-накрытием сильно регулярного графа с параметрами (2432,136,0,8), либо имеющий массив пересечений {х,х — 1,4,1; 1,2, гр — 1, ж} и являющийся антиподальным 3-накрытисм сильно регулярного графа с параметрами ((ж4-2)(ж4-3)/6,ж, 0, 6).
16
В случае к = (6?+36і)/2 в заключении следствия остаются п-угольник, граф икосаэдра, граф из МР(6) и дистанционно регулярный граф диаметра 4 с массивом пересечений {ж, ж — 1,4,1; 1,2,х — 1,х}, являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((ж + 2)(ж + 3)/6,ж,0,6), подтверждающие точность границы к > Ь\(Ь\ -г 3)/2, дающей сильную регулярность графа.
Глава 4 посвящена изучению автоморфизмов дистанционно регулярных графов.
В монографии П. Камерона (27| представлен метод Г. Хигмана, который дает необходимое условие существования автоморфизма дистанционно регулярного графа.
Пусть Г — дистанционно регулярный граф диаметра сI. Подстановочное представление группы <7 = ЛщГ на вершинах графа Г дает матричное представление ф группы С в СЬ(у,С). Пространство Си является ортогональной прямой суммой собственных подпрос транств Ж>Ф‘ * *0Ж* матрицы смежности А графа Г. Для любого д € <2 матрица ф(д) перестановочна с А, поэтому подпространство Ж является ^(<7)-инвариантным.
Пусть Хі~характер представления, полученного ограничением ф на Ж. Тогда
гі
Хх(д) =
>=о
где а^(д)—число вершин ж из Г, таких что гі(ж,ж?) = а С?*,• зависят от параметров Г.
Поскольку значения характеров — целые алгебраические числа, то в случае, когда значения рациональны, х«(.<у) является целым числом. Отсюда получаем условие делимости для оД#), j = 1С помощью этого условия были получены новые ограничения для групп автоморфизмов сильно регулярных графов с параметрами (85,14,3,2) (см. |60|) и (3250,57,0,1) (см. |52|). Эти результаты являются частью серии работ, посвященных изучению групп автоморфизмов сильно регулярных графов с малыми значениями Л и /2.
Б параграфе 4.1 получены результаты о группе автоморфизмов сильно регулярного графа с параметрами (85,14,3,2).
Наименьшим примером сильно регулярного графа с параметрами (?;, к, 3,2) является 5х5-рсшетка, имеющая параметры (25,8,3,2). Следующим набором параметров с Л = 3 и /і = 2, для которого возможно существование сильно регулярного графа, является (85,14,3,2).
Теорема 4.1. Пусть Т—сильно регулярный граф с параметрами (85,14,3,
17
2). Тогда для любого автоморфизма g из Aut Г простого порядка р выполняется одно из следующих утверждений:
(1) р Є {5,17} и Fix д—пустой граф;
(2) р = 7 и Fix д является 1 -кликой, или р = 5 и Fiхд является 5-кликой;
(3) р = 3, Fix# является четырехугольником или 2 х 5-решеткой, и в последнем случае для шести вершин из Fix# их окрестности содержат точно две максимальных 3-клики;
(4) р = 2, окрестность каждой вершины из Fix# связна, Fix# является объединением (р изолированных вершин и гр изолированных треугольников, причем либо ф = I и ip € {4,6}, либо ф = 0 и ip — 5.
В параграфе 4.2 изучается группа автоморфизмов графа Мура степени 57 (графа Ашбахера).
Для регулярного графа степени к и диаметра d на v вершинах выполняется неравенство:
V < 1 + к + к(к - 1) + • • • + к(к - I)*“1.
Графы, для которых достигается равенство, называются графами Мура. Простейшим примером графа Мура служит (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) (£), и Fixt является 56-звездой. Приведенная ниже теорема не делает предположений о существовании И11 вол юции.
Теорема 4.2. Пусть Г—граф Ашбахера и G = Aut Г. Тогда либо
(1) G содержит инволюцию t, и либо 0(G) — Р—силовская 5-подгруппа из G порядка 125, |[Р, t]| = 25, Z(P) действует полурегулярпо па Г, Fix (Cp(t)) —граф Хофмана-Синглтона, и Р содержит 25 подгрупп Ui порядка 5, имеющих пятиугольник в качестве подграфа пеподвиоюпых точек, либо G = Y(t) х X, У—циклическая группа, инвертируемая t, |Fj делит 7,19,55, |ЛГ| делит 7,25,27 или 55, и если X ф 1, то верно одно из утверждений:
(г) Fix А—звезда, \Х\ = 7 и У = 1,
(гг) Fix А -пятиугольник, [Fl делит 5, либо Fix ж— граф Хофмана-Синглтона для некоторого элемента х порядка 5 из X и \Х : (з;)| Є
18
- Київ+380960830922