Графы TI-подгрупп, расширения и автоморфизмы графов тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат наук Зюляркина, Наталья Дмитриевна

• Зюляркина, Наталья Дмитриевна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Зюляркина, Наталья Дмитриевна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ГРАФЫ КОММУТИРОВАНИЯ Т7-ПОДГРУПП §1.1. Предварительные сведения.

§1.2. Линейные группы. §1.2. Унитарные группы. §1.3. Ортогональные группы. §1.4. Симметрические группы.

2. АВТОМОРФИЗМЫ ПОЛУТРЕУГОЛЬНЫХ ГРАФОВ ХИГМЕНА §2.1. Предварительные сведения.

§2.2. Графы с /х = 6. §2.3. Графы с /х = 7. §2.4. Графы с ¡1 = 8.

§2.5. Реберно симметричные полутреугольные графы Хигмена. §2.6. Автоморфизмы графа с массивом пересечений {15,12,6; 1, 2,10}.

3. ГРАФЫ, В КОТОРЫХ ОКРЕСТНОСТИ ВЕРШИН ЯВЛЯЮТСЯ ЮШКОВЫМИ РАСШИРЕНИЯМИ РЕШЕТОК

§3.1. Предварительные сведения. §3.2. Локально решетчатые графы.

§3.3. Графы, в которых окрестности вершин являются кликовыми расширениями решеток.

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

СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Графы TI-подгрупп, расширения и автоморфизмы графов»

ВВЕДЕНИЕ

Теория графов и теория групп тесно связаны на протяжении всей истории своего развития.

С одной стороны, различные виды симметричных графов были построены с помощью известных групп. Отметим в качестве примера сильно регулярные графы ранга 3, связанные с действием группы на множестве, граф Гевиртца, построенный с использованием силовских 3-нодгрупп и инволюций из А6 и т.д.

С другой стороны, информацию о группе можно получить исходя из строения связанного с ней графа. В связи с этим упомянем диаграммы Дынкина для групп лиева типа, граф Грюнберга — Кегеля, построенный при помощи простых делителей порядка группы, графы коммутирования и т. д. Заметим также, что группа может быть описана как группа автоморфизмов заданного графа. При этом свойства группы будут определяться структурой графа и наоборот.

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

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

Отметим, что многие симметричные графы были построены как графы коммутирования на классе сопряженных элементов конечной почти простой группы (например: дополнительный граф к графу 3-транспозиций, графы из башни Судзуки и др.). Более того, спорадические группы Фишера, порожденные 3-транспозициями, были построены как группы автоморфизмов соответствующих графов.

Первая глава диссертации посвящена исследованию групп, содержащих циклическую ТТ-подгрупиу А порядка 4. Изучаются графы коммутирования, построенные на множестве сопряженных с А подгрупп, и определяются их параметры.

Пусть С — конечная группа, А < (?. Будем говорить что А является Т1-подгруппой

группы G если пересечение А и любой сопряженной с ней подгруппы тривиально. Если А — Т7-подгруппа конечной группы G и |Л| четен, то будем говорить, что А — подгруппа корневого типа, если для любого элемента g G G, такого что число четно, индекс

|А : Na(A9)\ является нечетным.

Конечные группы, содержащие 2-группу А, являющуюся TV-подгруппой, изучались М. Судзуки, Ф. Тиммесфельдом, Й. Хоггеймом, A.A. Махневым и Н.Д. Зюляркиной (см. [39], [32], [17], [36],[8], [9], [10]). В настоящий момент наименее исследоваными остались случаи когда А либо циклическая, либо элементарная абелева группа. Заметим, что если А — циклическая группа, то достаточно изучить ситуацию, когда |Л| = 4.

В дальнейшем будем считать, что А — циклическая Т/-подгруппа порядка 4 конечной группы G, порожденная элементом а и ао = а2.

Одним из основных методов исследования групп, содержащих Т7-подгруппу, является индукция. Кроме того существенно различаются случаи, когда G содержит компоненты, а когда нет. Так как А нормализует каждую компоненту группы, то при исследовании групп, содержащих компоненты, вопрос сводится к изучению групп вида G = F*(G)A, где обобщенная подгруппа Фиттинга F*(G) является квазипростой группой. Поэтому для построения индукционных предположений полезно иметь информацию о том, для каких известных квазипростых групп возможна такая конструкция, и какими свойствами в таких группах обладает подгруппа А.

Отметим, что в случае групп G = ХА, где X = F*(G) — квазипростая группа лиева типа, чаще всего встречается ситуация, когда о индуцирует на X внутренний или внутренне-диагональный автоморфизм. Через X* обозначим множество расширений группы X таких, что для группы X из X* любой элемент из X —X индуцирует на X внутренне-диагональный автоморфизм.

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

Если G — группа, А — Ti-подгруппа группы G, то граф коммутирования Г<з(А) определяется следующим образом:

вершинами графа Г (А) = Г<з(Л) являются подгруппы, сопряженные с Л, и две верши-

ны смежны тогда и только тогда, когда они коммутируют.

Особое внимание в теории графов уделяется графам с различными условиями симметричности.

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

Для смежных ( различных не смежных) вершин ад и и> графа Г обозначим через А(ад, ад;) (//(ад, ад>)) число вершин в [ад] П [гу].

Граф Г называется регулярным степени к, если для любой его вершины ад выполняется равенство |[ад]| = к. Граф Г называется реберно регулярным с параметрами (ад, к, Л) если он регулярен степени & на ад вершинах и для любых смежных вершин ад и ад; выполняется равенство А(и, ад;) = Л. Граф Г называется кореберно регулярным с параметрами (ад, к, ц) если он регулярен степени к на ад вершинах и для любых двух не смежных вершин и ни) выполняется равенство /х(ад, го) = (г.

Граф Г — вполне регулярный граф с параметрами (ад, к, А, //), если он реберно регулярен с соответствующими параметрами, и [а] П [Ь] содержит /х вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Если вершины ад, и) находятся на расстоянии г в Г, то через ¿»¿(ад,ад») (через с»(ад,ад;)) обозначим число вершин в пересечении Г*+1(ад) (Гг_г(ад)) с [ад;]. Граф Г диаметра 6, называется дистанционно регулярным с массивом пересечений {Ьо, &1, •.., Ь,1-1,С1,..., Сй}, если значения ¿»¿(ад, ад/) и с,(ад, ад;) не зависят от выбора вершин ад, и} на расстоянии г в Г для любого г — 0,..., й. Граф Г диаметра с? называется дистанционно транзитивным, если для любого г € {0,..., (1} и для любых двух пар вершин (ад, ад;) и (у, г) с й{и, и)) = с?(у, г) = г найдется автоморфизм д графа Г такой, что (ад3, и>9) = (у, г).

Граф Г называется графом Деза с параметрами (ад, к, Ь, а), где Ь > а, если он регулярен с параметром к, и [ад] П [ад] содержит а или Ь вершин для любых двух различных вершин ад, ад из Г.

Если С — группа автоморфизмов графа Г, а — вершина Г, то через Са обознается стабилизатор вершины а в группе (7.

Клыковым (кокликовым) расширением графа Г называется граф, полученный заменой каждой вершины а на клику (коклику) (а), причем разные клики (коклики) попарно не пересекаются и вершина из (а) смежна с вершиной из (Ь) тогда и только тогда, когда а, b смежны в Г. Если |(а)| = ß для любой вершины а, то граф называется кликовым (кокликовым) /^-расширением графа Г.

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

Очевидно, что вершинно симметричный граф будет регулярным, а реберная (коребер-ная) симметричность влечет равенство значений Л(u,w) (fi(u,w)) для любых смежных (различных не смежных) вершин и и w из Г.

Основные результаты первой главы приведены в следующих теоремах:

Теорема 1.1. Пусть G = ХА, X — частное группы SLn(q) по ее центральной подгруппе, q нечетно и либо G ^ X*, либо üq соответствует инволюции типа 1 или п — 1 из GLn(q). Тогда верно одно из следующих утверждений:

(1) п = 2 и Г (А) является кокликой;

(2) п > 3, G G X*, Г(А) является реберно симметричным графом диаметра 2, но не является кореберно регулярным графом, причем для двух несмежных вершин с и g графа Г(Л) число ц(с,д) равно (qn~2 - 1 )qn~2/(q - 1) или (qn~2 - l)qn~3/(q - 1);

(3) п > 3, G ф. X* и Г(А) является кокликой.

Следствие 1.1 .Если G — ХА, X — частное группы SLn(q) по центральной подгруппе, q нечетно, п > 2 uüq соответствует инволюции типа 1 или п— 1 из GLn(q), то граф Г(А) будет графом Деза с параметрами , -—-^rf—-—-—-^гу—1

Теорема 1.2. Пусть G = ХА, X — частное группы SUn(q) по ее центральной подгруппе, q нечетно и либо G X*, либо ао соответствует инволюции типа 1 или п — 1 из Un(q). Тогда верно одно из следующих утверждений:

(1) п = 2 и Г (А) является кокликой;

(2) п > 3, G € X*, Г(А) является реберно симметричным графом диаметра 2, но не является кореберно регулярным графом, причем для двух несмежных вершин с и g графа

Г(Л) число р.(с,д) при четном п равно дп~3(дп~2 — 1)/(д + 1) или Ч- 1), а

при нечетном п равно дп~3(дп~2 + 1)/(д, + 1) или дп~2(дп~3 — 1)/(д + 1);

(3) п > 3, С ^ X*, и Г(А) является кокликой.

Следствие 1.2.Если С = ХА, X — частное группы 8ип(д) по центральной подгруппе, д нечетно, п > 2 и ао соответствует инволюции типа 1 или п — 1 из ип(д), то граф Г (Л) будет графом Деза с параметрами

(Чп~1(дп-1) д"~2(дп~1+1) д"-2(д"~3+1) д"~3(д"-2-1Ь 9+1 ' д+1 ' (9+1) ' 9+1 >

для четного п;

или

/9"~1(д"+1) дп~2(дп~1—1) 9"-3(д"-2+1) д"~2(д"~3-1) ч д+1 ' 9+1 ' д+1 ' (9+1) /

для нечетного п.

Теорема 1.3. Пусть X — это Г^т+и?), Я = 1(4), т > 2 и ао соответствует инволюции типа 2 из 02т+\(я)- Тогда граф Г(Л) является реберно симметричным, но не является кореберно регулярным. Число вершин данного графа равно д2т~1(д2т — 1)/2(д—1), параметры реберной регулярности к и X равны соответственно д2т_3((5г2(т~1) —1)/2(^ — 1) и д2т-5^2(т-2) _ \у2(д — 1). Для различных несмежных вершин с и д параметр ц(с,д) принимает одно из следующих значений:

(1) д2т-5(92(т-2) _ 1)/2(д - 1);

(2) д2(т-2)(дт-1 _ 1)(дт-2 + 1у2(д - 1);

(3) д2(т-2)(9т-1 + 1)(дт-2 _ ^(д - 1);

(4) д2(т-2)(?т-2 _ 1)(д™-3 + - 1);

(5) д2(т-2)(дт-2 + 1)(дт-3 _ ^(д - 1);

(6) д2т-3(д2(т-3) _ 1)/2(д- 1);

(7) ^-3(^2(^-2) _ 1)/2(д — 1).

Все значения ¡л{с,д) из (1)-(7) встречаются в данном графе.

Теорема 1.4. Пусть X — это ^2т+1(д), д = 3(4), т > 2 и ао соответствует инволюции типа 2 из 02т+1(я)- Тогда граф Г (Л) является реберно симметричным, но не является кореберно регулярным. Число вершин данного графа равно д2т-1(д2ш — 1)/2(д+1), параметры реберной регулярности к и X равны соответственно д2т~3(д2<-т~^— 1)/2(д+1)

и с/2т 5(д2("1 2) — 1)/2(<7 + 1). Для различных несмежных вершин с и д параметр ¡л{с,д) принимает одно из следующих значений:

(1) д2т-5(Я2(т-Ъ-1)/2(д+1);

(2) д2(т-2)(9т-1 _ 1)(?т-2 _ !)/2(д + 1);

(3) д2(т-2)(^-1 + Щдт-2 + 1)/2((? + 1);

(4) ?2(т-2)(дт-2 _ _ 1)/2(д + 1);

(5) 92(т-2)(дш-2 + !)(9т-3 + ЦЩд + 1);

(6) д2т~3(д2^ -1)/2(д + 1);

(7) д2т-3(д2(ш-2) _ 1)/2(д 4- 1).

Все значения 1^(с,д) из (1)-(7) встречаются в данном графе.

Теорема 1.5. Пусть X — это П;,т(я)> Я = 1(4), т > 3 и ао соответствует инволюции типа 2 из О^^д)- Тогда граф Г(Л) является реберно симметричным, но не является кореберно регулярным. Число вершин данного графа равно д>2("г-1)(дт — 1)(д"г_1-|-1)/2(д — 1), параметры реберной регулярности к и X равны соответственно дг2(т-2)(дт~1 — 1)(дт_2 + 1)/2{д — 1) и <72(т_3)(дт~2 — 1)(дт_3 + 1)/2{д — 1). Для различных несмежных вершин с и д параметр ц{с, д) принимает одно из следующих значений:

(1) д2(т-3)(дт-2 _ 1)(дт-3 + 1)/2(д _ 1);

(2) 92(т-3)(дш-2 + !)(9т-3 _ ^^(д - 1);

(3) д2ш-5(д2(т-2) _ ^^ _ ^ .

(4) д2т-5(д2(т_3) — 1)/2(д — 1);

(5) ЧЧт-2)(дгп-3 _ !)(дт-4 + гу2(д - 1);

(6) д2(т-2)(9т-2 _ 1)(дт-3 + !)/2(д - 1).

Дсе значения ц(с,д) из (1)-(6) встречаются в данном графе.

Теорема 1.6. Пусть X — это т(д), д = 1(4), т > 3 и ао соответствует инволюции типа 2 из О^^д). Тогда граф Г(А) является реберно симметричным, но не является кореберно регулярным. Число вершин данного графа равно

параметры реберной регулярности к и X равны соответственно д2(т-2)(дт_1 + 1)(дт_2 — 1)/2(д — 1) и д2(т-з)^т-2 _ 1)/2(</ — 1). Для различных несмежных вершин с и

д параметр !л(с,д) принимает одно из следующих значений:

(1) д2(т-3)(9т-2 + !)(д™-3 _ уЩд - 1);

(2) д2(т-3)(дт-2 _ 1)(дт-3 + ^(д - 1);

(3) д2т-5(д2(т-2) _ 1)/2(д — 1);

(4) д2т-5^2(т-3) _ 1)/2(д - 1);

(5) д2(т-2)(дш-3 + 1)(д"»-4 _ 1)/2(д - 1);

(6) д2(т-2)(дт-2 + 1)(д™-3 _ !)/2(д - 1).

Все значения [¿(с,д) из (1)-(6) встречаются в данном графе.

Теорема 1.7. Пусть X — это ^2т(<7), Я. — 3(4), га > 3 и ао соответствует инволюции типа 2 из О^^д). Тогда граф Г(А) является вершинно и реберно транзитивным, но не является кореберно регулярным. Число вершин данного графа равно д2(т_1)(дт — 1)(дт-1 — 1)/2(д+1), параметры реберной регулярности к и X равны соответственно д2(т_2)(дт_1-|-1)(дт~2 + 1)/2(д + 1) и д2(™-з)(дт-2 _ 1)(д"»-з _ 1)/2(д + 1). Для различных несмежных вершин с и д параметр ц(с,д) может принимает одно из следующих значений:

(1) д2(т—3)(дт—2 _ 1)(дт-3 _ 1)/2(д + 1);

(2) д2(™-3)(дт-2 + 1)(д".-3 + 1)/2(? + 1);

(3) д2т-5(д2(1Тг-2) _ 1)/2(д + 1),"

(4) д2т-5(д2(ш-3) _ !)/2(д + 1);

(5) д2(—2)(д—3 + 1)(д—4 + + 1);

(6) д2(«-2)(дш-2 + 1)(дШ-3 + 1)/2(д+ 1).

Все значения ¡г{с,д) из (1)-(6) встречаются в данном графе.

Теорема 1.8. Пусть X — это 0,2т{я)> Ч = 3(4), т > 3 и а0 соответствует инволюции типа 2 из 0^гп(д). Тогда граф Г(Л) является вершинно и реберно транзитивным, но не является кореберно регулярным. Число вершин данного графа равно д2(т_1)(дт + 1)(дт-1 + 1)/2(д+1), параметры реберной регулярности к и X равны соответственно д2(т_2)(дт_ 1 _ 1)(дт~2 - 1)/2(д + 1) и д2(т-з)^т-2 + 1)(д"»-з + 1)/2(д + 1). Для различных несмежных вершин с и д параметр /х(с, д) принимает одно из следующих значений:

(1) д2(™-3)(дт-2 + !)(дт-3 + ^^(д + 1);

(2) д2(—3)(дт-2 _ 1)(дт-3 _ + 1);

(3) д2т-5(д2(т_2) — 1)/2(д + 1);

\

(4) g2m-5(92(m-3) _ l)/2(g+l);

(5) g2(m-2)(9m-3 _ l)(?m-4 _ Xy2{q + 1);

(6) q^m-2)^qm-2 _ ^m-3 _ + 1).

Все значения /х(с, <7) из (1)-(6) встречаются в данном графе.

Теорема 1.9. Пусть X — накрывающая врутьтьа длл Агы п > 5. Тогда справедливы следующие утверждения:

(a) если п < 8, то Г(А) является кокликой;

(b) если п = 8, то Г(Л) — это 3-кокликовое расширение лестничного графа на 70 вершинах (объединение 35 компонент связности, каждая из которых является полным двудольным графом

(c) если п — 9, то Г(А) является 3-кокликовым расширением дистанционно регулярного графа диаметра 4 с массивом пересечений {5,4,4,3; 1,1,2,2};

(d) если п = 10, то Г(А) это 3-кокликовое расширение реберно регулярного графа диаметра 3 на 210 вершинах, с параметрами к = 15 и Л = 0;

(e) если п > 11, то граф Г(А) является реберно симметричным, но не является коре-берно регулярным. Число вершин данного графа равно п(п — 1)(п — 2)(п — 3)/8, параметры к и X равны соответственно (п — 4)(п — 5)(п — 6)(п — 7)/8 и (п — 8)(п — 9)(п — 10)(п —11)/8. Для различных несмежных вершин с и g параметр ц(с, д) принимает одно из следующих значений:

(1) (п - 4)(п - 5)(п - 6)(п - 7)/8;

(2) (п - 5)(п - 6)(п - 7)(п - 8)/8;

(3) (п - 6)(п - 7)(п - 8)(п - 9)/8;

(4) (п - 7)(п - 8)(п - 9)(п - 10)/8.

Все значения ¡л(с,д) из (1) — (4) встречаются в данном графе.

Вторая глава диссертации посвящена исследованию групп автоморфизмов графов. При этом применялся метод Хигмена, основанный на целочисленности характеров мономи-альных представлений указанных групп автоморфизмов. Графу Г соответствует симметричная схема отношений (X, {До, Ri, R2}), где Rq — отношение равенства на множестве вершин X графа Г, Ri — отношение смежности в Г, R^ — отношение смежности в донол-

нителыюм графе Г. Для автоморфизма д графа Г через щ{д) обозначается число вершин и € Г таких, что (и, и9) € Щ. Данный метод позволяет определить возможные простые делители порядка исследуемой группы. В дальнейшем анализируется перестановочность элементов простых порядков с помощью комбинаторных и теоретико-групповых рассуждений. В работе были исследованы автоморфизмы полутреугольных графов Хигмена и дистанционно-регулярного графа с массивом пересечений {15,12,6; 1,2,10}.

Полутреугольным графом Хигмена назовем сильно регулярный граф Г с V = (™) и к = 2(ш — 2). Интерес к таким графам обусловлен результатом Д. Хигмена ([31]), который, изучая графы ранга 3, показал, что если С — группа подстановок ранга 3 степени (™), тп> 5 с подстепенью 2(т —2), то либо С изоморфна 4-транзитивной подгруппе из Зт, действующей на 2-элементных подмножествах, либо (2 изоморфна подгруппе РГЬ2(8) из ¿9, действующей на 2-элементных подмножествах, либо выполняется одно из утверждений:

(1) /л = 6 и т = 9,17,27 или 57;

(2) ¡л = 7 и т — 51;

(3) ц = 8 и т = 28,36,325, 903 или 8128.

Позднее, в [34] были классифицированы графы ранга 3 и в случаях (1-3) имеется единственный граф с д = 6, т = 9, реализуемый с помощью группы Сг(2)'.

Фактически, в [31] было доказано, что сильно регулярный граф Г с V = (™) и к — 2(т — 2) либо изоморфен треугольному графу Т(т) или одному из графов Чанга, либо выполняется одно из утверждений (1-3), либо д = 6, т = 7иГ изоморфен дополнительному графу к Т(7).

Результаты второй главы связанные с условиями (1-3) приведены в следующих теоремах:

Теорема 2.1. Пусть Г — сильно регулярный граф с параметрами (36,14,4,6), С = Аи1(Г), д — элемент простого порядка р из С? и Пх(д) = Тогда выполняется одно из следующих утверждений:

(1) П — пустой граф, р = 2 или 3 и а\(д) — 6г;

(2) является 1 -кликой, р = 7 и а\(д) = 14 или 3-кликой, р = 3 и а\(д) = 6г;

(3) П является 1-кокликой, р = 2 и I Е {4,6,8};

(4) р — 3, С а1- для некоторой вершины а, Г2(а) является 2 х 4 -решеткой (ив этом случае а.\((]) = 0J или Г2 является объедгтением двух или трех изолированных треугольников;

(5) р = 2, |Г2| < 18, степень вершины в графе О, четна и меньше 14.

Теорема 2.2. Пусть Г — сильно регулярный граф с параметрами (136,30,8,6), С = Аи1;(Г), д — элемент простого порядка р из С и Р1х($) = Тогда выполняется одно из следующих утверждений:

(1) Г2 — пустой граф, р = 2 и аг(д) = 20г + 4 или р = 17 и ах(д) = 34;

(2) П является 1 -кликой и р = 3,5 или О, является 3-кликой, р = 7 и ах(д) = 70г + 42 или является 4-кликой, р = 3 и а\(д) = ЗОг + 12 или является 7-кликой, р = 3 и а1(д) = 30г + 24;

(3) О. является Ь-кокликой, р — 3 и Ь е {4,7,10,13,16} или р = 2 и í € {6,8,10,16};

(4) Г2 не является пустым графом, кликой или кокликой, и р € {2,3}.

Теорема 2.3.Пусть Г — сильно регулярный граф с параметрами (351,50,13,6), С = Аи1;(Г), д — элемент простого порядка р из С и Г1х(д) = Тогда порядок группы Са не делится на 25 и выполняется одно из следующих утверждений:

(1) О, — пустой граф, и либо р = 3 и а\{д) = 45г -I- 9, либо р = 13 и а.\(д) = 195г + 30;

(2) ^ является 1-кликой и либо

(г) I = 1, р = 5 и аг(д) = 50я, либо р = 2 и аг(д) = 20я + 10, либо

(И) р = 3, I делится на 3 и а\(д) = 45я — 41 — 6 или р = 2 и ах(д) = ЗОя — 41 — 6;

(3) О. является Ь-кокликой, р = 2, Ь нечетно, 5 < 3 < 25 и си\(д) = ЗОз — 4£ — 6;

(4) р = 7 и Г2 — сильно регулярный граф с параметрами (36,15,6,6) и а\{д) = 105г;

(5) р = 5, 26 < < 116, степень вершины в П не меньше 10 и не больше 40, и ах не содержится в П для любой вершины а € £1;

(6) р = 3, |Г2| < 102 и в случае равенства имеем ос\(д) = 246;

(7) р = 2, не является кликой или кокликой.

Теорема 2.4. Пусть Г — сильно регулярный граф с параметрами (1596,110,55,6), С = АШ;(Г), д — элемент простого порядкар из С и ¥{х(д) = П. Тогда ж (С7) С {2,3,5, 7,11,

19} и выполняется одно из утверждений:

(1) Г2 — пустой граф, и либо р = 2 и а.\(д) = 60г 4- 24, либо р = 3 и а\(д) = 90г — 6, либо р = 7 и а^д) = 210г + 84, либо р = 19 и ах(д) = 570г 4-114;

(2) Г2 является I-кликой, I <28 и либо

(г) I = 1, р = 5 и ах(д) = ЗОг — 10 или р = 11 и а.\(д) = ЗЗОг + 110, либо (и) I делится на 3, р = 3 и а.\(д) +41 — ЗОг — 6;

(3) является 1-кокликой, р = 2, Ь < 56 четно и 4£ + ос\(д) = ЗОг — 6;

(4) — непустой граф, не являющийся кликой или кокликой и р < 11.

Теорема 2.5. Пусть Г — сильно регулярный граф с у = , к = 2{т—2) и ц = 7. Тогда т = 51, Г имеет параметры (1275,98,13,7) и для С = Аи^Г) и элемента д простого порядка р из (7 выполняется одно из утверждений:

(1) Г2 — пустой граф, и либо р = 3 и а\(д) = 60г + 45, либо р = 5 и 0:1(9) = 20г + 5, либо р = 17 и »1 (д) = 340г + 85;

(2) П является либо \Ъ-кликой и р = 2,3,7, либо 8-кликой и р = 7, либо Зп-кликой, п = 1,2,3,4 ир = 3;

(3) О. является Ь-кокликой, р = 7, Ь сравнимо с 1 по модулю 7, 8 < £ < 85 и а\(д) = 7т + 140г + 105;

(4) П = К7,7, р = 13 и ах (д) = 260г - 13;

(5) — непустой граф, содержащий геодезический 2-путъ Ь,а,с и либо

(г) р = 7, \Щ — 71 + 1, 2 < I < 25, не содержит связных компонент, являющихся сильно регулярными графами, либо

(И) р = 5, |Г2| = 5г, 4 < г < 51, если О — сильно регулярный граф, то Г2 является 5 х 5 -решеткой или 10 х 10 -решеткой, либо

(т) р = 3, (3) |Г2| = 31, 3 < I < 90, если Г2 — сильно регулярный граф, то является треугольным графом Т(6), либо

(ги) р = 2, \П\ = 2г + 1, 7 < г < 152.

Теорема 2.6. Пусть Г — сильно регулярный граф с V = (™), к = 2(т —2) и /л = 8. Если т = 28, С? = Аи^Г) ид— элемент простого порядка р из С, то п(С?) С {2,3, 5,7,13} и выполняется одно из следующих утверждений:

(1) iü — пустой граф, и либо р = 3, ot\(д) = 45s + 18, либо р = 7, ai(g) = 63;

(2) является т-кликой, и либо т = 1, р = 13 и ai(g) = 52, либо т = 3, р = 5 и <*i(s) е {75,150,225,300,375};

(3) Q является 2l-кокликой, р = 2, 3 < I < 24 и а\(д) + 221 — 3 делится на 15;

(4) р = 3 и либо

(г) О, является 3 х 3-решеткой или точечным графом обобщенного четырехугольника GQ{2,4), либо

(гг) ai(g) ф 0 и 30 < |i2| < 48, либо (m) oti(g) = 0 и |П| = 33,48,63;

(5) р = 2 и либо

(г) Г2 — объединение 21 изолированных треугольников, I < 10 и а\{д) = ЗОг —6Z + 18,

либо

(гг) аг(д) = 0 и |П| € {18,48}, либо (in) «1 (д) / Он |Г2| < 62.

Следствие 2.1. Сильно регулярный граф с параметрами (378,52,1,8) не является реберно симметричным.

Теорема 2.7. Пусть Г — сильно регулярный граф с v = ),к = 2(т — 2) и ß = 8. Если т = 36, G = Aut(r), д — элемент простого порядка р из G и Q = Fix(5f). Тогда 7t(G) С {2,3,5, 7,17} и выполняется одно из следующих утверждений:

(1) Ü — пустой граф, либо р = 3 и oti(g) = 51 г + 12, либо р = 5 и a\(g) = 85s — 5, либо р = 7 и ai(g) = 119i + 63;

(2) Q является т-кликой, либо т = 1, р = 17 и а\(д) 6 {34,323,612}, либо т = 3, р = 3 и oti{g) = Ыг + 27 или р = 11 и аг(д) = 187г + 44;

(3) является 21-кокликой, р = 2, 2 < I < 33 и аг(д) = 34г + 10/ + 12;

(4) р = 3, степень любой вершины в О. не меньше 8, но не больше 38 и 36 < |fi| < 78;

(5) р = 2, степень любой вершины в fl не меньше 6, но не больше 44 и |Г2| < 80.

Следствие 2.2. Сильно регулярный граф с параметрами (630,68,1,8) не является реберно симметричным.

Теорема 2.8. Пусть полутреугольный граф Хигмена Г является реберно симмет-

ричным. Тогда либо ц, = 4 и Г является треугольным графом, либо ц, = б и т равно 7 или 9.

Исследование дистанционно-регулярного графа с массивом пересечений {15,12,6; 1, 2, 10} представляет интерес ввиду результата из [3], где были найдены массивы пересечений дистанционно регулярных локально циклических графов с числом вершин не большим 1000.

Предложение 2.1. Пусть Г является дистанционно регулярным графом диаметра, большего 2, на v < 1000 вершинах. Если X = 2 и /л > 1, то верно одно из утверждений:

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

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

(3) Г — антиподальный граф с ß > 3 и массивом пересечений {15,12,1; 1,4,15}, {18,15,1; 1,5,18}, {27,24,1; 1,8,27}, {35, 32,1; 1,4,35}, {45,42,1; 1,6,45}, {42,39,1; 1,3,42}, {75,72,1; 1,12, 75}.

Ввиду данного описания предлагается исследование реберно симметричных графов с такими массивами пересечений.

Теорема 2.9. Пусть Г — дистанционно регулярный граф, имеющий массив пересечений {15,12,6; 1,2,10}, G = Aut(r), g — элемент из G простого порядка р и fi = Fix(g). Тогда 7r(G) С {2,3,5} и верно одно из утверждений:

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

(г) р = 5, а3{д) = 60г, а2(д) = 20г + 50/ - 20 и ах{д) = 180 - 80г - 50/; (и) р = 2, а3(д) = 24г и а2(д) = 8г + 20/;

(2) Г2 состоит из вершин, попарно находящихся на расстоянии 3 в Г и либо (г) р = 3, |Г2| = 1, а3(д) = 36г + 6 и а2(д) = 30s + 12г + 9, либо

(гг) р = 5, |ii| = 5, а3(д) = 30 и а2(д) = 95 или |П| = 10, а3(д) = 0 и а2(д) € {100,150};

(3) р — 3 и либо

(г) Г2 является 4-кликой, а3(д) = 36/, / < 3 и а2(д) = 30г + 12/ — 12, либо

(и) £1 — сильно регулярный граф с параметрами (16,6,2,2), 0:3(9) = 0 и а2(д) = 30г - 18;

(4) р = 2, = 2*, а3(д) = 24/ - 12«, а2(д) = 20г + 8/ - 10« и либо

(г) для любой вершины а из О, подграф Гз(а) не пересекает О и |Г2| < 16, либо

(и) содержит вершину степени 1 и |Г2| < 26, либо

(иг) степень любой вершины в П не меньше 3 и не больше 9, а |Г2| < 38.

Следствие 2.3. Пусть Г — дистанционно регулярный граф с массивом пересечений {15,12,6; 1,2,10}. Тогда Г не является реберно симметричным.

В третьей главе диссертации исследуются графы с заданным локальным строением.

Пусть Т — некоторый класс графов. Граф Г назовем локально Т-графом, если [о] лежит в Т для любой вершины а графа Г.

Система инцидентности, состоящая из точек и прямых, называется а-частичной геометрией порядка (5, £), если каждая прямая содержит в + 1 точку, каждая точка лежит на 4 + 1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой Ь, найдется точно а прямых, проходящих через а и пересекающих Ь (обозначение рСа(з, £)). В случае а — 1 геометрия называется обобщенным четырехугольником и обозначается 0(3(8,1). Точечным графом (графом прямых) геометрии точек и прямых называется граф, вершинами которого являются точки (прямые) геометрии, и две различные вершины смежны, если они лежат на общей прямой (содержат общую точку). Легко понять, что точечный граф частичной геометрии рОа(в,1) сильно регулярен с параметрами: V = (в + 1)(1 + вЬ/а), к = з(Ь + 1), А = (в — 1) + (а — 1)£, /л = а(Ь + 1). Сильно регулярный граф, имеющий вышеуказанные параметры для некоторых натуральных чисел называется псевдогеометрическим графом для рСа(в,{).

Граф на множестве пар X х У называется р х д-решеткой, если |Х| = р, |У| = 9, а пары (^ьуО и (х2,У2) смежны тогда и только тогда, когда Х\ = х2 или у\ = у2. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из X в качестве вершин, |Х| = т и пары {а, Ь}, {с, с/} смежны только, если они имеют единственный общий элемент.

Графом Джонсона J(n, т) называется граф, вершинами которого являются ш-подмно-

жества данного п-множества X, и вершины а, Ь смежны тогда и только тогда, когда они пересекаются по (т — 1)-множеству (очевидно Т(п) совпадает с ./(п, 2)). Частным графа Джонсона J(2m,m) назовем граф 3(2т,т), полученный отождествлением каждого т-множества с его дополнением.

Граф Грассмана 7?(п, т), 2 < т < п в качестве вершин имеет т-мерные подпространств заданного п-мерного пространства V над конечным полем порядка д, причем вершины а и Ь смежны, если размерность аГ)Ь равна т — 1. Диаметр ^(п, т) равен 2 только в случае т = 2.

Заметим, что в графе Грассмана Jq(n, т) окрестность каждой вершины является кли-ковым ^-расширением решетки. При изучении графов без корон, в которых /х-подграфы являются регулярными графами заданной положительной степени (см. [11], [12]) наибольшие трудности вызвал случай, когда окрестность каждой вершины является кликовым ¡3 расширением р х ^-решетки.

Через Кт п будем обозначать полный двудольный граф с долями порядков га, п.

Результаты, касающиеся графов, у которых окрестности вершин являются решеткой или кликовым расширением решетки, приведены в следующих теоремах.

Теорема 3.1. Пусть Г - сильно регулярный локально р х д граф. Тогда либо /х = 2р, р ф 1(4), либо Г = 7(10,5), либо Г - лестничный граф (объединение изолированных ребер).

Теорема 3.2. Сильно регулярный локально р х д-граф, р < д, р < 6, изоморфен одному из следующих графов:

(1) объединению полных графов,

(2) треугольному графу Т(д + 2),

(3) графу, дополнительному к 4 х А-графу,

(4) 7(8,4) или 7(10,5),

(5) графу с параметрами (112,36,10,12) (р = д = 6).

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

Список литературы диссертационного исследования кандидат наук Зюляркина, Наталья Дмитриевна, 2015 год

Список литературы

[1] Артин А. Геометрическая алгебра.// М., Наука 1969

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

[3] Буриченко В.П., Махнев A.A. О вполне регулярных локально циклических графах // Современные проблемы математики. Тезисы 42 Всероссийской молодежной конференции. ИММ УрО РАН, Екатеринбург 2011, 181 - 183.

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

[5] Гутнова А.К., Махнев A.A. О графах, в которых окрестности вершин являются псевдогеометрическими графами для pGs2(s,t) // Доклады академии наук 2010, т. 431, N 3, 301-305.

[6] Гутнова А.К., Махнев A.A. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,3) // Доклады академии наук 2010, т. 433, N 6, 727 -730.

[7] Гутнова А.К., Махнев A.A. Графы, в которых окрестности вершин — псевдогеометрические графы для GQ(3,5) // Доклады академии наук 2011, т. 438, N 3, 376 -379.

[8] Зюляркина Н.Д., Махнев A.A. Плотно вложенные подгруппы с абелевым слиянием // Тр. Ин-та математики и механики УрО РАН 1992, т. 2, 19-26.

[9] Зюляркина Н.Д., Махнев A.A. Циклические TJ-подгруппы порядка 4 в исключительных группах Шевалле // Тр. Ин-та математики и механики УрО РАН 1994, т. 3, 41-49.

[10] Зюляркина Н.Д. Циклические Т/-подгруппы порядка 4 в классических группах Шевалле нечетной характеристики // Вопросы алгебры и логики. Труды ИМ СО РАН 1996, 89-110.

[11] Кабанов В.В. О графах без корон с регулярными //-подграфами // Матем. заметки 2000, т. 67, 874 - 881.

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

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

[14] Камерон П., Ван Линт Дж. Теория графов, теория кодирования и блок-схемы // М., Наука 1980

[15] Кондратьев А.С. Граф Грюнберга-Кегеля конечной группы и его приложения // Алгебра и линейная оптимизация. Труды межд. семинара, посвященного 90-летию со дня рождения С.Н. Черникова. Екатеринбург 2002, 141-158.

[16] Лидл Р., Нидеррайтер Г. Конечные поля. // М., Мир, 1988

[17] Махнев A.A. TI-подгруппы в группах типа характеристики 2 // Мат. сборник 1985, т. 127, 239-244.

[18] Махнев А.А. О псевдогеометрических графах некоторых частичных геометрий // Вопросы алгебры, Гомель: Изд-во Томского ун-та, 1997, т. 11, 60-67.

[19] Махнев А.А. Частичные геометрии и их расширения // Успехи матем. наук 1999, т. 54, N 5, 25 - 76.

[20] Aschbacher М. Finite group theory // Cambridge University Press 1986.

[21] Blokhuis A., Brouwer A.E. Locally 4-by-4 grid graphs // J.Graph Theory 1989, v. 13, N 2, 229 - 244.

[22] Brouwer A.E., Cohen A.M., Neumaier A. Distance-Regular Graphs // Springer-Verlag. Berlin Heidelberg New York, 1989.

[23] Brouwer A.E., Haemers W.H. The Gewirtz graph: an exercize in the theory of graph spectra // Europ. J. Comb. 1993, v. 14, 397-407.

[24] Brouwer A.E., Haemers W.H. Spectra of graphs (course notes) // http://www. win.tue.nl/ aeb/

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

[26] Cameron P.J., van Lint J. Graphs, Codes and Desidns // London Math. Soc. Student Texts №22. Cambridge: Cambridge Univ. Press. 1991.

[27] Cossidente A., Penttila T. Hemisystems on the Hermitian surface // J. London Math. Soc. 2005, v. 72, 731-741.

[28] The GAP Group, GAP — Groups, Algorithms, and Programming, Version 4.4.12; 2008. (http://www.gap-system.org)

[29] Goethals J.M., Seidel J.J. The regular 2-graph on 276 vertices // Discrete Math. 1975, v. 12, 143 -158

[30] Harris M.E. Finite groups containing an intrinsic 2-component of Chevalley type over field of odd order // Transactions of the American math.soc. 1982, v. 272, N. 1, 1-65.

[31] Higman D.G. Characterization of families of rank 3 permutation groups by the subdegrees, I // Arch. Math. 1970, v. 21, 151-156.

[32] Hochheim Y. and Timmesfeld F. A note on Tl-subgroups // Arch.Math. 1988, v. 51, 97-103.

[33] Jafarzadeh A., Iranmanesh A. On simple Xn-groups for n = 5,6 // London Math. Soc. Lecture Note Ser. 2007. V. 340. P. 517-526.

[34] Liebeck M.W., Saxl J. The finite primitive permutation groups of rank 3 // Bull. London Math. Soc. 1986, v. 18, 165-172.

[35] Macay M., Siran J. Search for properties of the missing Moore graph // Linear Algebra and its Appl. doi: 10.1016/j.aa.2009.07.018.

[36] Makhnev A.A. A reduction theorem for Tl-subgroups // English transl. in Math.USSR Sb. v. 38, 299-311.

[37] Makhnev A.A. On the graphs with //-subgraphs isomorphic to Kux2 // Proc. Steklov Inst. Math., Suppl. 2. 2001, 169 - 178.

[38] Spence E. Regular two-graphs on 36 vertices // Linear Algebra and Appl. 1995, v. 226228, 459-497.

[39] Suzuki M. Finite groups of even order in which Sylow 2-groups are independent // Ann. of Math. 1964, v. 80, 58-77.

[40] Wilbrink H., Brouwer A. (57,14,1) strongly regular graph does not exist // Proc. Kon. Nederl. Akad. A, 1983, v. 45, 117-121.

[41] Zara F. Graphes lies aux expaces polaires // Eur. J. Comb. 1984, v.5, 255 - 290.

[42] Zavarnitsine A.V. Finite simple groups with narrow prime spectrum // Sibirean electr. Math. Reports 2009. V. 6. P. 1-12.

Работы автора по теме диссертации

[43] Зюляркина Н.Д. О графе коммутирования циклических TI-подгрупи в линейных группах // Труды ИММ УрО РАН 2011, т17, N 4, 114-120.

[44] Зюляркина Н.Д. О графе коммутирования TI-подгрупп в линейных группах.// Алгебра и геометрия. Тез. докл. Межд. конф. Екатеринбург 2011, 78 - 79

[45] Зюляркина Н.Д. О графе коммутирования Т7-подгрупп в унитарных группах // Труды ИММ УрО РАН Екатеринбург 2012, т. 18, N 3, 119-124.

[46] Зюляркина Н.Д. О графе коммутирования TI-подгрупп в ортогональных группах // Тез.докл.1Х Межд. конф. по теории групп, посвященной 90-летию со дня рождения проф. З.И. Боревича, Владикавказ 2012, 61-62.

[47] Зюляркина Н.Д. О графе коммутирования циклических TI-подгрупп в ортогональных группах // Сибирские электр. матем. известия 2013, т. 10, 180-199.

[48] Зюляркина Н.Д. О графе коммутирования TI-подгрупп в симметрических группах // Сибирские электр.матем. известия 2013, т.10, 436-442

[49] Зюляркина Н.Д., Махнев A.A. О сильно регулярных локально решетчатых графах // Дискрет, матем. 1993, т.5, N 4, 145-150.

[50] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов, имеющих ß = 6 // Доклады академии наук 2009, т. 426, N 4, 439-442.

[51] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов с ß = 6 II Труды 40-й Всеросс. молод, конф. Изд-во ИММ УрО РАН, Екатеринбург 2009, 12-15.

[52] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов с ß = 7 // Теория групп и ее приложения. Труды восьмой Международной школы-конференции по теории групп. Нальчик 2010, 107—109.

[53] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов, имеющих р = 111 Доклады академии наук 2011, т. 439, N 1, 21-24.

[54] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов, имеющих ß = 8 /I Доклады академии наук 2011, т. 440, N 2, 155-158.

[55] Зюляркина Н.Д., Махнев A.A. Об автоморфизмах дистанционно регулярного графа с массивом пересечений {15,12,6; 1,2,10} // Доклады академии наук 2011, т. 439, N 4, 443-447.

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

[57] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов Хигмена с ß = 8 II Алгебра и геометрия. Тез. докл. Межд. конф. Екатеринбург 2011, 80-82 .

[58] Зюляркина Н.Д., Махнев A.A. Автоморфизмы полутреугольных графов Хигмена с ß = 8 // Доклады академии наук 2014, т. 457, N 3, 274-277.

[59] Зюляркина Н.Д., Махнев A.A. Автоморфизмы графов Хигмена с ß = 6 // Труды ИММ УрО РАН Екатеринбург 2014, т. 20, N 2, 184-209.

(60] Зюляркина Н.Д., Махнев A.A. Реберно симметричные полутреугольные графы Хиг-мена // Доклады Академии наук 2014, т. 459, N 3, 261-265.

[61] Зюляркина Н.Д., Махнев A.A., Падучих Д.В. О графах, в которых окрестности вершин являются кликовыми расширениями решеток //Доклады Академии наук 2007, т. 416, N 5, 735-739.