Содержание к диссертации
Введение
1 Хорошие пары в реберно регулярных графах 10
1.1 О реберно регулярных графах 11
1.2 О хороших парах в графах с А2 25
2 Об автоморфизмах сильно регулярных графов 42
2.1 Введение 42
2.2 Об автоморфизмах графа с параметрами (99,14,1,2) 45
2.3 Об автоморфизмах графа с параметрами (243,22,1,2) 56
3 Об автоморфизмах графа с параметрами (115,18,1,3) 63
Литература 69
- О реберно регулярных графах
- О хороших парах в графах с А2
- Об автоморфизмах графа с параметрами (99,14,1,2)
- Об автоморфизмах графа с параметрами (243,22,1,2)
Введение к работе
Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b — вершины графа Г, то через d(a, b) обозначим расстояние между а и Ь, а через Гі(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Гі(а) будем называть окрестностью вершины а и обозначать через [а]. Через aL обозначим подграф, индуцированный {a} U [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Граф Г назовем реберно регулярным с параметрами (г/,/с, А), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в Л треугольниках. Граф Г — вполне регулярный граф с параметрами (v, к, А, /л), если он реберно регулярен с соответствующими параметрами и [а]П[6] содержит ц вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивио на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 30, 31]. Например, класс билдингов Титса характеризует группы Лиевского типа [32]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [14].
Пусть G — транзитивная группа подстановок на множестве Q. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку р Є Q, имеет г орбит, то говорят, что G является группой ранга г. Пусть
г = 3 и соответствующие 3 орбиты — это {р}, А(р), Г(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого — Q и две вершины р, q смежны в Г, если р Є Л(
Д.Хигмэн [21 — 27] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин, так и на множестве ребер. Такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра d называется дистанционно транзитивным, если для любого і Є {0, ...,d} и для любых вершин u,v,x,y, таких что d(u,v) = d(x,y) = і, существует автоморфизм д графа Г : (и, v)9 — (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [28].
Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+і(и) (Гї_і(и)) с [ги]. Дистанционно регулярным графом называется граф, в котором параметры b((u,w) и Ci(u,w)) не зависят от вершин и, v, а зависят только от расстояния на котором эти вершины находятся в графе Г.
Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов.
В первой главе монографии [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (v,k,X), в котором к > ЗЬ\, то Г имеет диаметр 2 и v < 2к — 2.
Цель работы. В диссертации исследуются строение реберно регулярных графов с к > 3&1 — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Л и /х.
Диссертация состоит из введения, трех глав и списка литературы (33 наименования).
В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v, к, Л). Тогда (см. лемму 1.1.1) степень вершины в любом /і-подграфе из Г не больше к — 2Ъ\. Поэтому для д* = к — 2Ь\ + 1 и любых вершин и, w, находящихся на расстоянии 2, выполняется неравенство n{u,w) > /і*. Пару несмежных вершин {и,и>) назовем хорошей, если [i(u, w) = //*.
В следствии из статьи А. А. Махнева [4] доказано, что если Г - связный реберно регулярный граф с параметрами (v, к, Л), в котором ЗЛ > 2к — 5, то либо Г - многоугольник или граф икосаэдра, либо к = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2к + 4 вершинами.
В параграфе 1.1. данной работы уточняется строение графа, удовлетворяющего условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно регулярных графах.
Следующие результаты являются основными в главе 1.
Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра 2 с параметрами (v,k,\), в котором ЗЛ > 2к — 5 и 2к + 1 < v. Тогда Г пятиугольник, 3x3 решетка или треугольный граф Т(7).
Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами (v, /с, Л), в котором ЗЛ > 2к — 5. Тогда либо (к, Л) = (4,1) и диаметр Г больше 2, либо Г - многоугольник, граф икосаэдра, 3x3 решетка, или треугольный граф Т(7), либо Г - граф диаметра 2 с не более чем 2к вершинами.
Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (г?, к, Л) и d Є Г. Если к > З&і — 2, то либо к = 2>Ъ\ — 1, Г является
многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары, либо для любой вершины d из Г пары (d,Wi) являются хорошимиідля/не более чем трех\вершин иі{ из T2(d). Случай к > ЗЬі — 1 рассмотрен в работе [6].
Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л,д) = (1,2). Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров Лид имеют жестко заданное строение. Так подграф неподвижного множества автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [10]). Хорошо известно (предложение 1.1.2 [14]), что сильный граф с ц > 2 сильно регулярен. Поэтому подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с тах{Л, fi} < 2 сильно регулярны с этими же параметрами или являются кликами.
В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Д.Хигмана работы с автоморфизмами сильно регулярных графов [19]. Во втором параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (99,14,1,2). Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются. В конце параграфа 2.2 работы найдено возможное строение группы G автоморфизмов графа с параметрами (99,14,1,2) при условии, что эта группа содержит инволюцию. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (243,22,1,2).
В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (115,18,1,3), если группа автомор-
физмов этого графа содержит элемент порядка 3.
Пусть Г является сильно регулярным графом с параметрами (г>, &,л,ЛА) и G = Aut(r) — группа его автоморфизмов. Для X С G через Fix(X) обозначим индуцированный подграф на множестве вершин графа Г неподвижных относительно любого автоморфизма из X.
Отметим далее некоторые утверждения, верные для графов с параметрами (v, к, 1,2). Так как Г — сильно регулярный граф, то к > 4. При к = 4 Г имеет параметры (9,4,1,2). Этим параметрам соответствует единственный граф, а именно, 3 х 3-решетка.[2]. В случае к > 4, используя равенство (Л — fi)2 + 4{к — /і) = п2, получим п = 2к+1, к = и2 + и + 2, п — тп = и и —тп = — и — 1. По условию целочисленности для сильно регулярных графов [14] имеем цп = 2(2и+1) делит (тп — 1)к(к + тп) = u(u2 + u + 2)(u2 -}- 2u + 3). Поэтому 2и + 1 делит 63, и и = 1, 3,4,10 или 31. При и = 1 снова возникает 3 х 3-решетка. При и = 3 получается граф с параметрами (99,14,1,2), автоморфизмы которого изучались в работе [9]. При и = 4 получается граф с параметрами (243,22,1,2), автоморфизмы которого изучались в работе [11].
В третьей главе работы рассматривается сильно регулярный граф с параметрами (v,k,l,3).
Доказательство теорем второй и третьей главы опирается на метод Дональда Хигмена работы с автоморфизмами сильно регулярного графа, изложенный в третьей главе монографии Камерона [19]. При этом сильно регулярный граф Г на i> вершинах с собственными значениями к, г, s рассматривается как симметричная схема отношений (X, {Ro, R\, R2}), где X — множество вершин графа Г, ~ Rq — отношение равенства на вершинах графа Г, Ri — отношение смежности в Г и i?2 - отношение смежности в дополнительном графе Г.
Если Р и Q — первая и вторая матрицы собственных значений схемы, то
/ 1 1 1 \
Р = к г s ,
{V — к — 1 —г—1 —5 — 1 у
и PQ = фР = г;/. При этом кратности 1,/, g собственных значений k,r,s графа Г образуют первый столбец матрицы Q.
Подстановочное представление группы G = Aut(T) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(v, С). Пространство Си является ортогональной прямой суммой собственных ф{С)-инвариантных подпространств Wq ф W\ ф W2 матрицы смежности графа Г. Пусть Xi ~ характер представления фцгг Тогда для любого д G получим
Xi(g) = v~l Е Qij<*j(g), j=o
где oti(g) — число точек х из X таких, что (х, х9) Є R(. Заметим, что значения характеров являются целыми алгебраическими числами, а правая часть данной формулы — число рациональное, поэтому Хі{я) является целым числом.
Основными результатами второй главы являются:
Теорема 2.1. Пусть Г является сильно регулярным графом, с параметрами (99,14,1,2), G = Aut(r). Если д — элемент простого порядка из G, A = Fix(g), то выполняется одно из утверлсдений:
А — одновершинный граф и \g\ = 2 или 7;
А — пустой граф и \д\ = 3 или 11; Q2) А — треугольник и \д\ = 3.
В частности, порядок группы автоморфизмов сильно регулярного графа с параметрами (99,14,1, 2) делит 2 З3 7 11.
Следствие 2.1. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), G = Аііі(Г). Если G содерэ/сит инволюцию t, то вы,-
полняется одно из утверждений:
\G\ делится на 7 и делит 42, причем [0(G), і] = 1 и в случае \G\ = 42 подгруппа 0{G) неабелева.
\G\ делит 6.
Теорема 2.2. Пусть Г является сильно регулярным графом с параметрами (243,22,1,2), G — Aut(r). Если р — элемент простого порядка из G, A = Fix(p), то выполняется одно из утверждений:
|р| = 2, |А| = 9 и каждая связная компонента графа А является одновершинным графом, треугольником или 3x3 решеткой;
\р\ == 3, А является пустым графом или 3x3 решеткой;
|р| = 5, А является треугольником;
|р| = 11, А является одновершинным графом.
Основным результатом главы 3 является следующая теорема:
Теорема 3.1. Если Г является сильно регулярным графом с параметрами (115,18,1,3), то порядок группы автоморфизмов графа Г делит число 2Q3^5 23.
Автор выражает глубокую признательность своим научным руководителям профессору А.А. Махневу и д.ф.-м.н В.В. Кабанову за постановку задачи и постоянное внимание.
О реберно регулярных графах
Граф Г диаметра d называется дистанционно транзитивным, если для любого і Є {0, ...,d} и для любых вершин u,v,x,y, таких что d(u,v) = d(x,y) = і, существует автоморфизм д графа Г : (и, v)9 — (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [28]. Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Гі+і(и) (ГЇ_І(И)) с [ги]. Дистанционно регулярным графом называется граф, в котором параметры b((u,w) и Ci(u,w)) не зависят от вершин и, v, а зависят только от расстояния на котором эти вершины находятся в графе Г. Поскольку каждый дистанционно регулярный граф является вполне регулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории дистанционно регулярных графов. В первой главе монографии [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (v,k,X), в котором к ЗЬ\, то Г имеет диаметр 2 и v 2к — 2. Цель работы. В диссертации исследуются строение реберно регулярных графов с к 3&1 — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Л и /х. Диссертация состоит из введения, трех глав и списка литературы (33 наименования). В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v, к, Л). Тогда (см. лемму 1.1.1) степень вершины в любом /і-подграфе из Г не больше к — 2Ъ\. Поэтому для д = к — 2Ь\ + 1 и любых вершин и, w, находящихся на расстоянии 2, выполняется неравенство n{u,w) /І . Пару несмежных вершин {и,и ) назовем хорошей, если [i(u, w) = // . В следствии из статьи А. А. Махнева [4] доказано, что если Г - связный реберно регулярный граф с параметрами (v, к, Л), в котором ЗЛ 2к — 5, то либо Г - многоугольник или граф икосаэдра, либо к = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2к + 4 вершинами. В параграфе 1.1. данной работы уточняется строение графа, удовлетворяющего условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно регулярных графах. Следующие результаты являются основными в главе 1. Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра 2 с параметрами (v,k,\), в котором ЗЛ 2к — 5 и 2к + 1 v. Тогда Г пятиугольник, 3x3 решетка или треугольный граф Т(7). Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами (v, /с, Л), в котором ЗЛ 2к — 5. Тогда либо (к, Л) = (4,1) и диаметр Г больше 2, либо Г - многоугольник, граф икосаэдра, 3x3 решетка, или треугольный граф Т(7), либо Г - граф диаметра 2 с не более чем 2к вершинами. Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (г?, к, Л) и d Є Г. Если к З&і — 2, то либо к = 2 Ъ\ — 1, Г является многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары, либо для любой вершины d из Г пары (d,Wi) являются хорошимиідля/не более чем трех\вершин иі{ из T2(d). Случай к ЗЬі — 1 рассмотрен в работе [6]. Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л,д) = (1,2). Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров
Лид имеют жестко заданное строение. Так подграф неподвижного множества автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [10]). Хорошо известно (предложение 1.1.2 [14]), что сильный граф с ц 2 сильно регулярен. Поэтому подграфы неподвижных точек 2 -автоморфизмов сильно регулярного графа с тах{Л, fi} 2 сильно регулярны с этими же параметрами или являются кликами. В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Д.Хигмана работы с автоморфизмами сильно регулярных графов [19]. Во втором параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (99,14,1,2). Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются. В конце параграфа 2.2 работы найдено возможное строение группы G автоморфизмов графа с параметрами (99,14,1,2) при условии, что эта группа содержит инволюцию. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (243,22,1,2). В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (115,18,1,3), если группа автомор
О хороших парах в графах с А2
В данном параграфе доказывается теорема 1.2. Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (г;, к, Л) и d Є Г. Если к З&і — 2, то выполняется одно из утвершсдений: (1) к = 3&i — 1, Г является многоугольником или графом икосаэдра, и любые две вершины, находящиеся на расстоянии 2, образуют хорошие нары; (2) для любой вершины и из Г пары (и, wi) являются хорошими для не более чем трех вершин wi из Т2(и); (3) для некоторой вершины и из Г пары (и, Wi) являются хорошими для четырех вершин W{ из Г2(11), Ъ\ = 6 и v = 31. Случай к ЗЬі — 1 рассмотрен в работе [6]. В следствии из [4] доказано, что если в реберно регулярном графе к З&і — 2, то либо Г — многоугольник, граф икосаэдра или реберный граф тривалентного графа без треугольников, имеющий диаметр, больший 2, либо диаметр Г равен 2 и число его вершин не больше 2к + 4. Лемма 1.2.1. Пусть Г - реберно регулярный граф с параметрами (v, к, X) и Ь\ = к — X— 1. Если вершины u,w находятся на расстоянии 2 в Г, то выполняются следующие утверждения: (1) степень любой вершины в / -подграфе из Г не меньше к — 2Ъ\; (2) вершина d имеет степень а в графе [и] П [w] тогда и только тогда, когда [d] содержит точно а — (к — 2Ь\) вершин вне uL U w1; (3) если /i(u, w) = // , то подграф [u]r\[w] является, кликой и [d] С Uw1-для любой вершины d Є[и\Г\ [w\; (4) если Ащт codepotcum единственную вершину z, то fi(u,z) = /J(W,Z). Доказательство. Пусть d Є [и] П [w]. Тогда \[d\ — [и]\ = \[d] — [w]\ — Ь\. Поэтому по крайней мере к — 2Ь\ вершин из [d] содержится в [и] П [w]. Утверждение (1) доказано. Пусть с? Є [и] П [w] и степень d в этом /х-подграфе равна а. Тогда к = a + 2&i — \[d\ — (и1- U wL)\. Поэтому [d] содержит а — (к — 2&i) вершин вне и1- U w1-. Утверждение (2) доказано. Утверждение (3) следует из (1), (2). Пусть {z} = AUfW. Так как число ребер между расстоянии 2, образуют хорошие нары; (2) для любой вершины и из Г пары (и, wi) являются хорошими для не более чем трех вершин wi из Т2(и); (3) для некоторой вершины и из Г пары (и, Wi) являются хорошими для четырех вершин W{ из Г2(11), Ъ\ = 6 и v = 31. Случай к ЗЬі — 1 рассмотрен в работе [6]. В следствии из [4] доказано, что если в реберно регулярном графе к З&і — 2, то либо Г — многоугольник, граф икосаэдра или реберный граф тривалентного графа без треугольников, имеющий диаметр, больший 2, либо диаметр Г равен 2 и число его вершин не больше 2к + 4. Лемма 1.2.1. Пусть Г - реберно регулярный граф с параметрами (v, к, X) и Ь\ = к — X— 1. Если вершины u,w находятся на расстоянии 2 в Г, то выполняются следующие утверждения: (1) степень любой вершины в / -подграфе из Г не меньше к — 2Ъ\; (2) вершина d имеет степень а в графе [и] П [w] тогда и только тогда, когда [d] содержит точно а — (к — 2Ь\) вершин вне uL U w1; (3) если /i(u, w) = // , то подграф [u]r\[w] является, кликой и [d] С Uw1-для любой вершины d Є[и\Г\ [w\; (4) если Ащт codepotcum единственную вершину z, то fi(u,z) = /J(W,Z). Доказательство. Пусть d Є [и] П [w]. Тогда \[d\ — [и]\ = \[d] — [w]\ — Ь\. Поэтому по крайней мере к — 2Ь\ вершин из [d] содержится в [и] П [w]. Утверждение (1) доказано. Пусть с? Є [и] П [w] и степень d в этом /х-подграфе равна а. Тогда к = a + 2&i — \[d\ — (и1- U wL)\. Поэтому [d] содержит а — (к — 2&i) вершин вне и1- U w1-.
Утверждение (2) доказано. Утверждение (3) следует из (1), (2). Пусть {z} = AUfW. Так как число ребер между [и] — [w] и [w] — [и] равно 1 ЇМ — [w]\ №(иі z)i то {щ z) — v{w- z)- Лемма доказана. Из леммы 1.2.1 следует, что если любая пара несмежных вершин реберно регулярного графа Г является хорошей, то Г оказывается графом Тервилли-гера без 3-лап и по теореме 1.2.3 [14] Г — пятиугольник или граф икосаэдра. Лемма 1.2.2. Пусть Г - реберно регулярный граф с параметрами (v, к, А). Если Г-не полный граф и А 2к/3 — 1 (эквивалентно к ЗЬ\), то Г имеет диаметр 2, v 2к — 2 и выполняется неравенство kbi {v-k- l)(k+l-2bi). Доказательство. Это лемма 1.4.2 из [14]. Лемма 1.2.3. Пусть Г - связный реберно регулярный граф с параметра ми (v,k,X). Если X к + 1/2 — \j2k + 2, то Г - дополнительный граф) для сильно регулярного графа А с /л(Д) 2. Доказательство. Это второе утверждение теоремы 1.4.3 из [14]. Лемма 1.2.4. Пусть Г - сильно регулярный граф, имеющий параметры (v,k,X,(j). Тогда либо к = 2ц, X = /л — 1 (так называемый половинный случай), либо неглавные собственные значения п — т, —т графа Г - целые . Далее, если т - целое число, большее 1, то га — 1 делит fin к — X [и] — [w] и [w] — [и] равно 1 ЇМ — [w]\ №(иі z)i то {щ z) — v{w- z)- Лемма доказана. Из леммы 1.2.1 следует, что если любая пара несмежных вершин реберно регулярного графа Г является хорошей, то Г оказывается графом Тервилли-гера без 3-лап и по теореме 1.2.3 [14] Г — пятиугольник или граф икосаэдра. Лемма 1.2.2. Пусть Г - реберно регулярный граф с параметрами (v, к, А). Если Г-не полный граф и А 2к/3 — 1 (эквивалентно к ЗЬ\), то Г имеет диаметр 2, v 2к — 2 и выполняется неравенство kbi {v-k- l)(k+l-2bi). Доказательство. Это лемма 1.4.2 из [14]. Лемма 1.2.3. Пусть Г - связный реберно регулярный граф с параметра ми (v,k,X). Если X к + 1/2 — \j2k + 2, то Г - дополнительный граф) для сильно регулярного графа А с /л(Д) 2. Доказательство. Это второе утверждение теоремы 1.4.3 из [14]. Лемма 1.2.4. Пусть Г - сильно регулярный граф, имеющий параметры (v,k,X,(j). Тогда либо к = 2ц, X = /л — 1 (так называемый половинный случай), либо неглавные собственные значения п — т, —т графа Г - целые . Далее, если т - целое число, большее 1, то га — 1 делит fin к — X — 1 и Доказательство. Это лемма 3.1 из [3. В леммах 1.2.5-1.2.6 предполагается, что Г - реберно регулярный граф, ueT,w,ze Г2(и), А = [и]Г\ [w] П [z] и 6 = Д.
Об автоморфизмах графа с параметрами (99,14,1,2)
Теорема 2.1. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), G = Aut(r). Если д — элемент простого порядка из G, Д = Fix(g), то выполняется одно из утверэюдений: (1) Л — одновершинный граф и\д\=2 или 7; (2) Л — пустой граф и \д\ =3 или 11; (2) А — треугольник и \д\ = 3. В частности, порядок группы автоморфизмов сильно регулярного графа с параметрами (99,14,1,2) делит 2 З3 7 11. Следствие 2.1.. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), G = Aut(r). Если G содержит инволюцию t, то выполняется одно из утверждений: (1) G делится на 7 и делит 42, причем [0(G), t] = 1 и в случае \G\ =42 подгруппа 0(G) неабелева. (2) \G\ делит 6. Рассмотрим сильно регулярный граф Г с параметрами А = 1, /л = 2. Пусть G = Aut(r) — группа автоморфизмов Г. Выберем подгруппу X нечетного порядка из G. Пусть Q = Fix(X) — множество вершин графа Г, неподвижных относительно каждого элемента из X. Если а, Ъ — несмежные вершины из Q, то [а] П [Ь] — подграф, допустимый относительно X, поэтому [а] П [Ь] С Г2. Значит Q — либо сильно регулярный граф с Л = 1,// = 2, либо является кликой или пустым графом. Пусть t - инволюция из G, a, b Є Fix(t). Тогда, [а] П [6] = с, d и либо c,d Є Fix(i), либо сь = d. Если [6] nFix(t) содержит несмежные вершины е, /, то вторая вершина подграфа [е] П [/] также попадает в Fix(). Пусть Г — сильно регулярный граф с параметрами (v, к, 1,2). Если X — подгруппа нечетного порядка из G = Aut(r), то Fix(X) является пустым графом, сильно регулярным графом с А = 1,/х = 2, одновершинным подграфом или треугольником. Пусть t — инволюция из G, причем Д = Fix() — непустой граф. Если a,b — несмежные вершины из Л, {c,d} = [а] П [6], то либо с, d Є А, либо с = d и вершины а, 6 находятся на расстоянии, не меньшем 3, в графе Д. В половинном случае Г имеет параметры (9,4,1,2). Этим параметрам соответствует единственный граф, а именно, 3 х 3-решетка. В случае к 4, используя равенство (Л — /i)2 + 4(fc — ц) = п2, получим п = 2и + 1, к = и2 + и-\-2, п — т = ии —т = —и — 1. По условию целочислеиности для сильно регулярных графов [in = 2(2w + l) делит (га — 1)к(к-}-т) = и(и2 + и-\-2)(и2-\-2и-\-3). Поэтому 2и + 1 делит G3, и и = 1,3,4,10 или 31. При и = 1 снова возникает 3 х 3-решетка. При и = 3 получается граф с параметрами (99,14,1, 2), вопрос о существовании которого поставил Зейдель. Пример 2.1. Рассмотрим автоморфизмы 3 X 3-решетки. Пусть X — группа нечетного порядка из Aut(r), Q = Fix(X). Так как \[а]\ = 4, то случаи \0,\ = 1 или 3 невозможны. Поэтому X действует без неподвижных точек на Г и порядок группы автоморфизмов графа Г делит 21 З2 (группа автоморфизмов 3 х 3-решетки является расширением группы Eg с помощью диэдральпой группы порядка 8). Пусть до конца работы Г является графом Зейделя с параметрами (99,14,1,2), G = Aut(r). Предложение 2.1. Пусть Г является графом Зейделя с параметрами (99,14,1,2), у — элемент нечетного простого порядка из Aut(r) и О, = Fix(y). Тогда выполняется одно из следующих утвероісдеиий: (1) Q пусто (у не имеет неподвижных вершин) и \у\ = 3 или 11; (2) Q является одновершинным графом и \у\ = 7; (3) Q является треугольником и \у\ = 3. (4) Q является 3 х 3-решеткой и \у\ = 5. Доказательство. Если Q = {а} является одновершинным графом, то \у\ делит 14. Если Г2 является треугольником {а,Ь,с}, то \[а] — {Ь, с}\ — 12 и \у\ = 3. Если Q является 3 х 3-решеткой, а Є Q, то \[а] — 0,\ = 10 и \у\ = 5. Предложение 1 доказано.
Строение подграфов неподвижных точек инволютивпых автоморфизмов выяснено в предложении 2.2. Предложение 2.2. Пусть Г — сильно регулярный граф с параметрами (99,14,1,2), имеющий инволютивный автоморфгазлі t. Тогда Fix(t) является одним из следующих подграфов: (1) одновершинный граф; (2) треугольник; (3) три изолированных треугольника; (4) вершина и два изолированных треугольника; (5) четыре изолированных вершины и треугольник; (6) п-коклика, п = 3,5 или 7; (7) 3 х 3-решетка. Доказательство предложения 2.2. разобьем на ряд лемм. Пусть t — инволюция из G, A = Fix( ). Для ребра {х, у} графа Г через ху будем обозначать единственную вершину из [х] П [у]. Лемма 2.2.1 Пересечение двух 3 х 3-решетпок из Г является пустым графом, вершиной или треугольником. Доказательство. Заметим, что пересечение двух 3 х 3-решеток Ей Е из Г пусто или является кликой. Если Е П Е является ребром {х, у}, то [х] П [у] содержит по вершине из Е и из Е . Противоречие с тем, что А = 1. Лемма 2.2.2 Связная, компонента графа Д, имеющая более трех вершин, является 3 х 3-решеткой и совпадает с Д. Доказательство. Заметим, что окрестность вершины х из Г — Д содержит не более двух вершин из Д, иначе ц(х,хь) 2. Связная компонента Е графа Д является одновершинным графом, треугольником или вполне регулярным графом степени асА = 1и/х = 2. Если Е имеет более трех вершин, то Е содержит четырехугольник {а, 6; с, d} и еще четыре вершины ас, ad, be, bd. Положим [ас] Г) [ad] = {а, е}, [be] П [bd] = {b, /}. Если е = /, то Д является 3 х 3-решеткой. Так как каждая вершина вне 3x3-решетки смежна с единственной вершиной этой решетки, то Е = Д. Число ребер между Д и Г —Д равно Д(14 — а). С другой стороны, указанное число не больше 2Г - Д. Поэтому Д 99/(8 - а/2). Если а = 6, то Д 99/5, противоречие с тем, что Д 20. Если а = 8, то Д 99/4. Противоречие с тем, что Д .1 + 8 + 8 6/2 + 2 = 35. Если а = 10, то Д 99/3, противоречие с тем, что Д 1 + 10 + 10 8/2 + 2 = 53. Наконец, если а = 12, то Д 99/2, противоречие с тем, что Д 1 + 12 + 12 10/2 + 2 = 75.
Об автоморфизмах графа с параметрами (243,22,1,2)
Пусть в данном параграфе Г — сильно регулярный граф с параметрами (243,22,1,2). Теорема 2.2. Пусть Г является сильно регулярным графом с параметрами (243,22,1,2), G = Aut(r). Если р — элемент простого порядка из G, A = Fix(p), то выполняется, одно из утверждений: (1) p = 2, А = 9 и каждая связная компонентна графа А является одновершинным графом, треугольником или 3x3 решеткой; (2) р = 3, А является пустым графом или 3x3 решеткой; (3) р = 5, А является треугольником; (4) \р\ = 11, А является одновершинным графом. Лемма 2.3.1. Пусть Г — сильно регулярный граф, имеющий параметры (243,22,1,2), G = Aut(r), Р и Q — матрицы собственных значений соответствующей 2-схемы, Х\ характер представления G на подпространстве размерности 110. Тогда Доказательство. Прямые вычисления. Лемма 2.3.2. Пусть Г — сильно регулярный граф, имеющий параметры (243,22,1,2). Тогда Г не содержит двух изолированных 3x3 решеток. Доказательство. Пусть граф Г содержит 3x3 решетку А. Тогда, мощность объединения окрестностей всех вершин из А за вычетом А равна 1С2. Пусть Г содержит решетку А , изолированную от А. Обозначим через Хг-множество вершин из Г — (A U А ), смежных точно с г вершинами из A U А , Х{ — \Х{\. Объединение -подграфов вида [х] П [у], где х Є А, у Є А , содержит 9-9 2 = 162 вершин. Следовательно, Г = A U A U XQ U Х2 и Хо = 63 Вершина х Є XQ смежна с 18 вершинами из Хч и число ребер между XQ и Х2 равно 63 18. Пусть вершина и из Х2 смежна с вершиной а из А. Для вершины b Є Д(а) подграф [и] Г) [b] содержит а и точно одну вершину из .. Для вершины с из Д — а1- подграф [и] П [] содержит 2 вершины из Х . Таким образом, [и] содержит 2 вершины из Д U Д , 12 вершин из А"г и 8 вершин из XQ. Следовательно, число ребер между Хч и Хо равно 162 8, противоречие. Предложение 2.3.1 Пусть д — элемент нечетного простого порядка из Aut(r) и Q = Fix( 7). Тогда выполняется одно из следующих утверждений: (1) Q пусто (д не имеет неподвижных вершин) и \д\ = 3; (2) Q является одновершинным графом и \g\ = 11; (3) П является треугольником и \д\ = 5; (4) Q является 3 х 3-решеткой и \д\ = 3. Доказательство. Если Г2 — пустое множество, то есть д не имеет неподвижных точек, то так как \д\ делит 243, то \д\ = 3. Если Q является одновершинным графом, то \д\ делит 22 и порядок д равен 11. Если Q является треугольником {а, 6, с}, то \[а] — {6, с}\ = 20 и \д\ = 5. Если Г2 содержит две несмежные вершины, то Q — сильно регулярный граф сЛ = 1и/х = 2. По лемме 1.2 Q является 3 х 3-решеткой и для а Є Г2 получим \[а] — Г2 = 18. Отсюда = 3. Предложение 2.1 доказано. В леммах 2.3.3-2.3.6 предполагается, что t — инволюция из G и Д = Fix(i). Пусть Х{ — множество вершин из Г — Д, смежных точно с г вершинами из Д, х{ = \ХІ\. Лемма 2.3.3. Либо каждая связная компонента графа Д является одновершинным графом, треугольником или 3x3 решеткой, либо Д является вполне регулярным графом диаметра, большего 2, с A = 1,/z = 2. Доказательство.
Пусть Е — связная компонента графа Д. Если Е — клика, то Е = 1 или 3. Если Е не является кликой, то но предложению 1.1.2 [2 Е является вполне регулярным графом с А = 1, fi = 2 и Е 9. Если диаметр Е равен 2, то по лемме 1.2 граф Е является 3x3 решеткой. Пусть диаметр Е больше 2. Если Е = А, то выполняется заключение леммы. Пусть Е 12 и и Є А — Е, тогда объединение //-подграфов вида [и] П [х], где ібЕ, содержит не менее 24 вершин. Противоречие с тем, что степень вершины и равна 22. Пусть теперь 11. Тогда, Е содержит хотя бы две вершины а, 6 на расстоянии 2 друг от друга. Следовательно, /х-подграф [а] П [6] содержится в Е. По утверждению 1, добавляя вершины сначала из Л-подграфов, а затем из //-подграфов, можно подсчитать, что Е = 10 или 11. Число треугольников в Е равно fcE/6, где к — степень Е. Если Е = 10 и Е не является кликой, то к = 6. Рассмотрим несмежные вершины а, 6, с из Е, d(a, 6) = 3. Тогда, если d(a,c) = 2, то противоречие с тем, что степень Е равна 6. Аналогичное противоречие получается в случае Е = 11. Лемма 2.3.4. Пусть каждая связная компонента графа А является одновершинным графом, треугольником или 3x3 решеткой. Если А содержит 0 изолированных вершин, у изолированных треугольников и S изолированных 3x3 решеток, то XQ + х\ + Х2 = 243 — 0 — Ъу — 95, х\ + 2#2 = 22/3 + 607 + 162(5 и х2 = 02 + 9т2 + 81(52 + 67/З + 18/35 + Ыу5 -0-91-816 и выполняется одно из утверждений: (1)0 делится на 9, 7 делится на 3; (2) 0 — 1 делится па 9. Доказательство. Пусть А содержит 0 изолированных вершин, у изолированных треугольников и 6 изолированных 3x3 решеток. Тогда А = /3+37+9(5. Покажем, что х\ — a\(t). Пусть (х, Xі) — ребро. Тогда, в треугольнике х, Xі, а вершина а Є А и [х] П А = а, иначе ребро (х, Xі) лежит больше чем в одном треугольнике. Далее, если х Є Хі и х,х — несмежные вершины, то подграф [х] П [х1] содержит вершины а, Ь. Так как а Є А, то b Є А. Следовательно, х смежна более чем с одной вершиной в А. Противоречие с выбором х Є Х\. Подсчитаем число ребер между А и Г — А: 22/3 + 6О7 + 162 5. С другой стороны, по лемме 1.1 Т.ХІ = 243 — 0 — З7 — 9(5 и число ребер из Г — А в А равно Е ІХІ = 220 + 6О7 + 162(5 и Е (Qz,- = /5(/3 - 1 + З7 + 9(5) + 37(0 + З7 — 3 + 9 5) + 9 5(0 + З7 + 9 5 — 9). Так как по лемме 1.1 ХІ = 0 для г 2, то утверждение (1) доказано. Пусть а — изолированная вершина графа А. Так как каждой паре ребер из [а], переставляемых t, отвечает пара вершин из А — а, то число ребер из [а], сдвигаемых t, равно 0 — 1 + З7 + 9 5. Пусть Ь — вершина изолированного треугольника графа Д. Тогда число ребер из [6], сдвигаемых , равно (3 + З7 — 3 + 9(5. Пусть с — вершина изолированной 3 х 3-решетки графа А. Тогда число
