Локальные подграфы и автоморфизмы графов тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Ефимов, Константин Сергеевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2010
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
004604124
Институт математики и механики Уральского отделения РЛН
На правах рукописи
ЕФИМОВ Константин Сергеевич Локальные подграфы и автоморфизмы графов
(01.01.06 — математическая логика, алгебра и теория чисел)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Екатеринбург - 2010
И 7Ш нШ)
004604124
Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН
Научный руководитель:
доктор физ.-мат. наук, член-корр. РАН МАХНЕВ A.A. Официальные оппоненты:
доктор физ.-мат. наук, профессор БАРАНСКИЙ В.А. кандидат физ.-мат. наук, доцент ЗЮЛЯРКИНА Н.Д.
Ведущая организация:
Южно-Уральский Государственный Университет
Защита состоится 15 июня 2010 г. в 14 ч. 00 м. на заседании совета Д 004.006.03 по защите диссертаций на соискание ученой степени кандидата наук при Институте математики и механики Уральского отделения РАН по адресу: 620219, Екатеринбург, ул. Софьи Ковалевской, д. 16.
С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.
Автореферат разослан /10 5. 2010 г.
Ученый секретарь
диссертационного совета профессор, доктор физ.-мат. наук
КАБАНОВ В.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. С развитием теории групп и теории представлений групп спектр исследований в области симметрии расширился, затронув различные разделы математики, физики, биологии, химии и других наук. В этом потоке выделилось принципиально новое направление, связанное с изучением дистанционно транзитивных графов и их обобщений. Дистанционно транзитивный граф характеризуется тем свойством, что его группа автоморфизмов действует транзитивно на множествах упорядоченных пар равноудаленных вершин графа.
Пусть (7 — транзитивная группа подстановок на множестве П. Если стабилизатор вр точки р 6 Г2, имеет г орбит на П, то говорят, что в имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе С удается построить сильно регулярный граф Г, множество вершин которого П и две вершины р,д смежны в Г, если д £ Г(р) (см. [17]).
Д. Хигман ([17]-[21]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В диссертации рассматриваются неориентированные графы без петель и кратных ребер.
Пусть Г — простой граф. Назовем окрестностью вершины и графа Г подграф всех смежных с и вершин. Окрестность вершины и £ Г будем обозначать через Г(и) или даже через [и]. Окрестность вершины называется локальным подграфом.Через 1\(ц) обозначим подграф всех вершин, находящихся на расстоянии г от и. Граф Г называется регулярным графом степени к, если [о] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберпо регулярным графом с параметрами (ь, к, Л), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в А треугольниках.
Граф Г называется вполне регулярным графом с параметрами (у,к,Х,1л), если Г ре-берно регулярен с соответствующими параметрами и подграф [а] П [Ь] содержит р. вершин в случае ¿{а, Ь) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Если вершины и, и> находятся на расстоянии г в Г, то через ш) (через с*(и, ги)) обозначим число вершин в пересечении Г^+г(и) (Г^^и)) с Г(ги). Заметим, что в реберно регулярном графе число Ъ\ (и, ги) не зависит от выбора смежных вершин и, ги и обозначается через
Цель работы.
1. Изучить вполне регулярные графы с ц < к — 2Ьх + 3.
2. Изучить вполне регулярные графы с ¿>1 = 6.
3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (75,32,10,16).
Методы исследований. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности, метод Хигмена приложения
теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов и подграфов неподвижных точек этих автоморфизмов, а также метод хороших пар.
Научная новизна. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в теории групп и теории графов.
Апробация работы. Результаты диссертации докладывались на международной алгебраической конференции в Санкт-Петербурге (2007 г.), VII международной школе-конференции по теории групп (Челябинск, 2008 г.), международной школе-конференции по теории групп, посвященной 80-летию со дня рождения А.И.Кострикина (Нальчик, 2009 г.), и на 39-й, 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2010 гг.).
Публикации. Результаты диссертации опубликованы в цикле работ, состоящем из 4 статей (одна в журнале из списка ВАК), и 5 тезисов докладов. Из 4 статей 1 написана без соавторов, 1 - тремя авторами (Ефимов К.С., Махнев A.A., Нирова М.С.), остальные - в соавторстве с Махпевым A.A. Все совместные работы написаны в нераздельном соавторстве.
Структура и объем работы. Диссертация состоит из введения, 3 глав и списка литературы, содержащего 39 названий. Общий объем диссертации составляет 86 страниц.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении даны основные определения и обозначения, используемые в диссертации, обсуждается общая мотивировка решаемых задач. В главе I рассматриваются вполне регулярные графы с ß < k—2bi +3. Во второй главе работы исследуются вполне регулярные графы с bi = 6. В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32,10,16).
Дистанционно регулярным графом с массивом пересечений Ьо,..., b¡¡_1; Сд,..., c¿ называется граф диаметра d, в котором для любых вершин u,w € Г, находящихся на расстоянии г, подграф Г(эд) содержит ровно bi вершин, находящихся на расстоянии i + 1 от «, и ровно с, вершин, находящихся ва расстоянии i — 1 от и. Легко понять, что условие дистанционной транзитивности влечет дистанционную регулярность графа. Таким образом, результаты, полученные для дистанционно регулярных графов, применимы и к дистанционно транзитивным графам.
Заметим, что сильно регулярный граф с ß > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с d > 2 — вполне регулярным графом с к = Ьо, А = к — í>i — 1 и д = сг-
Пусть задан класс графов Т. Мы скажем, что граф Г является локально F-графом, если для любой вершины а 6 Г имеем Г(а) S Т. Тогда можно поставить задачу описания локально ^"-графов. Если граф Г вершинно транзитивен, то окрестности всех его вершин
изоморфны, и граф Г является локально J- графом, где Т состоит из графов, изоморфных некоторому графу Д. В этом случае назовем Г локально А-графом. В более общем случае F может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных реберно регулярных графов — это в точности класс связных локально регулярных графов.
Определим несколько сильно регулярных графов, которые будут фигурировать далее, а также являются примерами локально Д- графов.
Пусть М nN — конечные множества порядка тип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется т х п-решеткой-, при т = п он сильно регулярен с параметрами (гг2,2(п - 1),п - 2,2).
Треугольным графом Т{п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т(п) также сильно регулярен и имеет параметры (п(п — 1)/2,2(п — 2), и — 2,4). Окрестность каждой вершины в Т(п) изоморфна 2 х (п — 2)-решетке, т.е. Т(п) — локально 2 х (п - 2)-решетка.
Единственный сильно регулярный граф с параметрами (27,16,10,8) называется графом Шлефли. Единственный сильно регулярный граф с параметрами (16,10,6,6) называется графом Клебша. Граф Шлефли является локально графом Клебша.
Основным результатом главы 1 является классифицикация вполне регулярных графов с р, < k - 2&i + 3.
Пусть Г — сильно регулярный граф с параметрами (v,k,\,/i),bi = k — \ — lBii = k — 2bi+x. Если Г имеет целое собственное значение — m и m > 1, то х = m+bi(m—2)/(m — 1). Легко понять, что х = 1 (каждая пара несмежных вершин в сильно регулярном графе является хорошей) тогда и только тогда, когда Г является пятиугольником.
Если Г — полный мпогодольный граф, то к = (п — l)(i>i + 1) = ц, поэтому х = 2i>i. Таким образом для любого четного х имеется бесконечное семейство полных многодольных графов с долями порядка х/2 + 1 и ц — к — 2Ь\ + х.
Если Г — граф с параметрами (Ац + 1,/j - 1,/л), то ¿>i = ¡л = х и 4х -t-1 — сумма квадратов двух целых чисел. Значит, для нечетного х такого, что 4x4-1 не является суммой квадратов двух целых чисел, не существуют сильно регулярные графы с р. = к — 2bi + х и параметрами (4х + 1,2х, х — 1, х).
Если 4х + 1 = р", р — простое число, то граф Пэли Р(рп), вершинами которого являются элементы поля F порядка рп и две вершины смежны тогда и только тогда, когда их разность является ненулевым квадратом в F, является сильно регулярным графом с параметрами (4х + 1,2х, х - 1, х).
Наименьшее нечетное х такое, что 4х + 1 не является суммой квадратов двух целых чисел, равно 5.
Если Г — псевдогеометрический граф для pGa(s,t), то к — s(t +1), i>i = t(s — a + l),/i = a(i + 1) и x = (i - l)(s - a) + 21.
В случае x = 5 можно взять t = 2, s — a = 1. Таким образом, для графа GQ(2,2) имеем х = 5.
Теперь можно сформулировать ряд предположений.
Верно ли, что для любого натурального числа х существует сильно регулярный граф с ¡i = к — 2bi + х? Верно ли, что для любого нечетного числа X существует лишь конечное число сильно регулярных графов с. ц = к — 2£>i + х? Для каких четных чисел х существуют бесконечные серии сильно регулярных графов с fi — к ~2bi + х и к > /i?
В статье [33] были получены следующие теорема и предложение, направленные на решение данных проблем.
Теорема 1. Пусть х — натуральное число. Тогда выполняются следующие утверждения:
(1) если х нечетно, тпо существует сильно регулярный граф с ц = к — 2bj 4- х;
(2) если х > 3, то существует лишь конечное число сильно регулярных графов с k > ¡i ufi = k — 2bi+x.
Предложение 1. Пусть Г — сильно регулярный граф с параметрами (v, к, A, fi), ¡i — к — 2Ь\ + х < к и 3 < х < 10. Если Г имеет целое собственное значение —т, то х = m + ¡>i(m - 2)/(m — 1) и выполняется одно их следующих утверждений:
(1) х € {3,4} и Г — граф Шли с параметрами (4х + 1,2х,х — 1,х);
(2) х = 5 и Г является дополнительным графом к 4 х 4-решетке, треугольному графу Т(6) или графу Клебша;
(3) х = 6 и Г является одним из следующих графов: (i) граф Пэли с параметрами (25,12,5,6),
(и) граф Хофмана-Синглтона или его дополнение, (Ш) граф с параметрами (26,10,3,4) или его дополнение;
(4) х = 7 и Г является одним из следующих графов: (г) граф Пэли с параметрами (29,14, б, 7),
(и) псевдогеометрический граф для GQ(A, 2), рС2(5,2), р<?з(б, 2) или рС?4(7,2), (Ш) дополнительный граф для псевдогеометрического графа обобщенного четырехугольника GQ(3,3) или для графа Гевиртца;
(5) х = 8 и Г является одним из следующих графов:
(г) граф с параметрами (85,14,3,2), (49,18,7,6) или (49,32,21,20),
(и) дополнительный граф для 5 х 5-решетки или для треугольного графа Т(7);
(6) х = 9 и Г является одним из следующих графов: (i) граф с параметрами (37,18,8,9) или (69,20,7,5),
{и) псевдогеометрический граф 5лярСг(7,2) или длярйз(8,2), (ш) дополнительный граф для псевдогеометрического графа обобщенного четырехугольника GQ{3,5) или для графа с параметрами (77,16,0,6);
(7) х = 10 и Г является одним из следующих графов:
(i) граф с параметрами (41,20,9,10) или граф Гевиртца с параметрами (56,10,0,2), (и) псевдогеометрический граф для pG2{8,2), pGз(9,2), pG$(8,3), р(?з(5,3), р(?2(4,3) или для GQ(3,3),
(й'г) дополнительный граф для графа с параметрами (81,20,1,6) или для псевдогеометрического графа геометрии pGi{l, 2),
(iv) 6 х 6-решетка, треугольный граф Т(8), граф Шлефли или один из трех графов Чанга.
В теореме Ливингстона-Тэйлора (теорема 1.3.3 из [10]) доказано, что во вполне регулярном графе выполняется неравенство fi > к - 2Ь\ +1 и описаны графы с ¡j. = к - 2¡>i +1.
Белоусов И.Н. и Махнев A.A. (см. [8]) классифицировали вполне регулярные графы с ß — к — 2bi + 2. В диссертации рассматривается следующий случай.
Теорема 2. Пусть Г — вполне регулярный граф с параметрами {v, к, А, ß) и ß = к — 2bi + х, х < 3. Тогда выполняется одно из следующих утверждений:
(1) х — 1 и Г — граф икосаэдра или граф прямых регулярного графа без треугольников, имеющего обхват, больший 4;
(2) х = 2 и Г — граф Зейделя или тривалентный граф без треугольников диаметра, большего 2, с ß = 1;
(3) х — 3 и Г — один из следующих графов:
(г) граф Пэли с параметрами (13,6,2,3), куб или граф Клейна,
(гг) граф Тэйлора с параметрами (6i>i — 4,36j — 3,26i — 4, bi) и fci 6 {4,6,10},
(ш) регулярный граф без треугольников степени 4 или граф cbi =4, fc = 6 и А = 1.
Из теоремы 2 вытекает следствие для дистанционно регулярных графов.
Следствие 1. Пусть Г — дистанционно регулярный граф диаметра, большего 2, с ß = k — 2bi + х и х < 3. Тогда выполняется одно из следующих утверждений:
(1) х = 1 и Г — граф икосаэдра, п-угольник, п > б, реберный граф графа Мура или флаг-граф регулярного обобщенного п-угольника, п € {3,4,6}, порядка (s, s) для некоторого s;
(2) х = 2 и Г — додекаэдр, граф Хивуда, Паппа, Кокстера, Дезарга, Бигза-Симса, Фостера или т-клетка Татта, т 6 {8,12};
(3) х = 3 и Г — один из следующих графов: (г) куб или граф Клейна;
(и) граф Тэйлора с параметрами (66j — 4,3i>j — 3,2— 4, bi) и 6j e {4,6,10}; (iii) нечетный граф Ot, его двудольное удвоение, граф инцидентности PG(2,3), Ж?(2,3) с удаленным классом параллельных прямых, GQ(3,3) или GH(3t3).
Глава 2 посвящена изучению вполне регулярных графов с i»i = 6.
При изучении реберно регулярных графов с k > f(bi) для некоторых функций / удается установить оценку v < g(k) (или получить описание графов, для которых не выполняется оценка v < g{k)). Так, в [10, лемма 1.4.2] доказано, что если Г — связный неполный реберно регулярный граф с параметрами (и, к, Л), в котором к > ЗЬь то диаметр Г равен 2 и v < 2к — 2. Фактически доказано, что г; < к — 2+3&i+3/(bi + l), и уточнение границы для числа вершин потребует описания графов с малыми значениями bj и графов, насыщенных хорошими парами вершин.
В монографии Броувера, Коэна и Ноймайера доказано, что связный реберно регулярный граф с ¿>i = 1 является многоугольником или полным многодольпым графом с долями порядка 2. Кроме того, ранее исследовались реберно регулярные графы с bi < 5 (см. [9], [5]). В диссертации изучаются вполне регулярные графы с Ь\ = 6.
Теорема 3. Пусть Г — связный реберно регулярный граф с параметрами (v,k,X). Если £>х = 6 и к > 22, то Г — полный многодельный граф Krx7> г >5 или граф из МР(6).
Теорема 4. Пусть Г — связный вполне регулярный граф с параметрами (и, к, Л, ß) и bi = 6. Тогда выполняется одно из следующих утверждений:
(1) Г — полный многодельный граф Кгх7, граф с параметрами (25,12,5,6), 7x7-решетка, треугольный граф Т(9), дополнительный граф к 5 х 5-решетке или к треугольному графу Т(7), граф Хофмана-Синглтона или его дополнение, граф с параметрами (26,10,3,4) или его дополнение;
(2) Г — полный двудольный граф K^s с удаленным максимальным паросочетанием, граф Тэйлора с параметрами (28,13,6,6), е котором окрестности вершин изоморфны графу Пэли Р( 13) или граф Тэйлора с параметрами (32,15,8,6), а котором окрестности вершин изоморфны треугольному графу Т(6);
(3) /J = 4, к = 12, c¡(u,y) > 6 для любых вершин и, у с d(u,y) = 3 и диаметр Г равен
3;
(4) ц = 3 и 9 < к < 12;
(5) ц = 2 и 7 < к < 11; .
(6) (1 = 1 и окрестность каждой вершины является 1-кокликой, объединением изолированных п-клик для п = 2,3 или 6..
Таким образом, изучение вполне регулярных графов с bi = 6 редуцируется к случаю fc = 10, А = 3.
Теорема 5. Пусть Г — связный вполне регулярный граф с параметрами (v, 10,3, (i). Тогда выполняется одно из следующих утверждений:
(1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т{1) или одним из десяти графов с параметрами (28,10,3,4);
(2) (1 — 3 диаметр Г равен 3 и 34 < и < 37;
(3) /х = 2 и Г является графом Конвея-Смита или графом Доро.
Применяя рассуждения теоремы 5 к дистанционно регулярным графам получим
Следствие 2. Пусть Г — дистанционно регулярный граф с к = 10, А = 3. Тогда выполняется одно из следующих утверждений:
(1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
(2) ц = 2 и Г является графом Конвея-Смита или графом Доро.
В главе 3 выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32,10,16) и уточняется строение группы автоморфизмов указанного графа, в случае, когда он является точечным графом частичной геометрии pGi(4,7). Рассмотрение данного случая завершает изучение автоморфизмов частичных геометрий pGz(4, t).
Частичной геометрией pGa(s,t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t+1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначаете ся GQ(s,t). Если а = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрииpGa(s, t) сильно регулярен с параметрами: v = (s+l)(l-hst/a),
к = + 1), А = (в — 1) + (а — 1)4, ¡1 = + 1). Любой сильно регулярный граф с такими параметрами для некоторых а, з, £ называется псевдогеометрическим графом для
Пусть Г — сильно регулярный граф с параметрами (75,32,10,16), д — автоморфизм простого порядка р графа Г и Г2 = Г1х(д). Через «¡(<?) обозначим число вершин и графа Г с ¿(и, и») = г.
Теорема 6. Пусть Г — сильно регулярный граф с параметрами (75,32,10,16), д — элемент простого порядка р из Аи(;(Г) и П = Р1х(з). Тогда верно одно из утверждений:
(1) — пустой граф, р = 3 и сц(д) £ {0,30,60} или р = 5 и сц(д) делится на 50;
(2) П является п-кликой, и либо п = 3, р = 3 и оч(д) — 6 делится на 30, либо п = Ь, р = 7 и сч(д) = 0;
(3) Л является т-кокликой, р = 2, т нечетно, 3 < т < 15, 01(3) — 2т делится на 10, и в случае т = 15 пара (П, Г — П) является (15,60,32,8,16)-схемой;
(4) П содержит 2-лапу, р = 2 и либо
(г) П — объединение изолированной вершины и октаэдра, либо (И) П — объединение изолированной вершины и Къд-подграфа, либо (ш) |П| = 24 + 1, 4 < г < 15 или г = 17.
В случае, когда сильно регулярный граф с параметрами (75,32,10,16) является точечным графом частичной геометрии 4,7) получим
Следствие 3 Пусть Г — точечный граф частичной геометрии рС2(4,7), в — группа автоморфизмов графа Г, д — элемент простого порядка р из в и (I — Г1х(р). Тогда |С| делит 2' -3 • 52 (для некоторого целого Ь) и верно одно из утверждений:
(1) П — пустой граф, либо р = 3 и а^д) 6 {0,30,60}, либо р — 5 и а1 (<?) 6 {0,50};
(2) р = 2 и выполняются следующие случаи:
(¿) Оц(д) = 0, П — треугольный граф Т(6), каждая точка из Г - Я смежна с 6 точками из П или П является т-кокликой и т е {5,15}, либо
(И) 0:1(5) Ф 0, П — объединение октаэдра и I изолированных точек, 1 < I < 11, I нечетно или П — объединение изолированной точки и точечного графа длярСг{2,3).
ЛИТЕРАТУРА
1. Махнев, A.A. Об одном классе реберно регулярных графов/ A.A. Махнев, И.М. Минакова // Изв. Гомел. гос. ун-та- 2000 - Т.З.- С.145-154.
2. Махнев, A.A. Об автоморфизмах сильно регулярных графов сА = 0, ß = 2/ A.A. Махнев, В.В. Носов // Мат. сб.- 2004,- Т.185, №3.- С.47-68.
3. Махнев, A.A. Об автоморфизмах графа Ашбахера/ A.A. Махнев, Д.В. Падучих // Алгебра и логика.- 2001,- Т.40, №2,- С.125-134.
4. Махнев, A.A. О расширениях частичных геометрий, содержащих малые /¿-подграфы /A.A. Махнев // Дискр. анализ и исслед. операций.- 1996 - Т.З. С.71-83.
5. Махнев, A.A. О сильной регулярности некоторых реберно регулярных графов/ A.A. Махнев // Изв. РАН. Сер. мат.- 2004,- Т.68.- С.159-172.
6. Махнев, A.A. О псевдогеометрических графах некоторых частичных геометрий/ A.A. Махнев // Вопросы алгебры. Вып. 11.- Гомель: Изд-во Гомел. ун-та. 1997 - С. 60-67.
7. Махнев А.А. Об одном классе кореберно регулярных графов/А.А. Махнев ,Д.В. Падучих // Изв. РАН. Сер. мат. 2005,- Т. 69, N 6.- С. 95-114.
8. Белоусов, И.Н. О почти хороших парах вершин в реберно регулярных графах / И.Н. Белоусов, А.А. Махнев // Изв. Уральского гос. ун-та- 2005.- Т. 36, №7. - С.35-48.
9. Казарина, В.И. О реберно регулярных графах с Ьх = 5/ В.И. Казарина, А.А. Махнев // Междунар. конф. "Алгебра, логика и кибернетика": тез. докл.- Иркутск, 2004,- С. 159— 161.
10. Brouwer, А.Е. Distance-regular graphs/ А.Е. Brouwer, A.M. Cohen, A. Neumaier // Berlin etc: Springer-Verlag, 1989.- 495 c.
11. Brouwer, A.E. The Gewirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Haemers // Europ. J. Comb.- 1993.- Vol.14.- P.397-407.
12. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. - Amsterdam:Elsever Sci. 1995.-P.63-107.
13. Buekenhout, F. Finite diagram geometries extending buildings/- F. Buekenhout, P. Pasini // Handbook of incidence geometry: buildings and foundations/ F. Buekenhout - Amsterdam: Elsever Sci. 1995.- P.1143-1255.
14. Cameron, P. Permutation Groups/ P. Cameron.- London: London Math. Soc.; Cambridge Univ. Press, 1999.
15. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang // Sci. Record.- 1949.- Vol.3.- P.604-613.
16. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, щ = 12, n0 = 15 and p*n = 4/ L.C. Chang // Sci. Record.- 1950,- Vol.4.- P.12-18.
17. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman // Math. Z - 1964.-Vol.86- P.145-156.
18. Higman, D.G. On finite affine planes of rank 3/ D.G. Higman // Math. Z.- 1968.-Vol.104.- P.147-149.
19. Higman, D.G. A survey of some questions and resalts about rank 3 permutation groups/ D.G. Higman // Actes Congres Int. Math. Rome.- 1970 - Vol.1.- P.361-365.
20. Higman, D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II/ D.G. Higman // Arth. Math.- 1970.- Vol.21.- P.151-156; 353-361.
21. Higman, D.G. Coherent configurations/ D.G. Higman //Rend. Sem. Mat.Univ. Padova.-1970.- Vol.44.- P. 1-26.
22. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman // Ann. Math. Stat.- I960,- Vol.31.- P.492-497.
23. Hoffman, A.J. On the exceptioal case in a characterization of the arcs of complete graphs/A.J. Hoffman // IBM J. Res. Develop.- I960.- Vol.4.- P.487-496.
24. Hoffman, A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman // Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.
25. Macay, M. Search for properties of the missing Moore graph/ M. Macay, J. Siran // Linear Algebra and its Appl. 2009.
26. Numata, M. On a characterization of a class of regular graphs/ M. Numata // Osaka J. Math.- 1974,- Vol.11.- P.389-400.
27. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher // Lect. ser. 8 - Cambridge: Univer. press, 1997.
28. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel // Linear Algebra and Appl.- 1968.- Vol.1.- P.281-298.
29. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande // Ann. Math. Stat.- 1959.- Vol.30.- P.781-798.
30. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits // Springer Lecture Notes in Math.- Vol.386.
Работы автора по теме диссертации
31. Ефимов, К.С. О сильно регулярных графах с /i = к - 26i + х / К.С, Ефимов, А.А. Махнев // Классы групп, алгебр и их приложения: тез. докл. - Гомель, 2007.- С. 68-69
32. Ефимов, К.С. Вполне регулярные графы с /х < & — 26]+ 3/ К.С. Ефимов, А.А. Махнев // Междунар. алгебр, конф.: тез. докл.- СПб, 2007.- С. 29-31.
33. Ефимов, К.С. Вполне регулярные графы с Ьг = 6 / К.С. Ефимов, А.А. Махнев // Тр. 39-й Всерос. молод, конф., Екатеринбург: Изд-во ИММ УрО РАН 2008. С - 16-18.
34. Ефимов, К.С. Вполне регулярные графы с ц < к — 2bi + 3 / К.С. Ефимов, А.А. Махнев // Тр. Ин-та математики НАН Беларуси.- 2008.- Т. 16, N 1.- С. 28-39.
35. Ефимов, К.С. О реберно регулярных графах с bj = 6 / К.С. Ефимов, А.А. Махнев // 7-я Междунар. шк.-конф. по теории групп: тез. докл.- Челябинск, 2008.- С. 48-51.
36- Ефимов, К.С. Вполне регулярные графы с bi = 6 / К.С. Ефимов, А.А. Махнев // Журн. Сиб. Федер. ун-та 2009,- Т. 2, N 1,- С. 63-77.
37. Ефимов, К.С. О вполне регулярных графах с к = 10, А = 3 / К.С. Ефимов, А.А. Махнев, М.С. Нирова // Алгебра и ее прил.: тр. междунар. конф., посвящ. 80-летию со дня рождения А.И. Кострикина.- Нальчик ,2009.- С. 44-48.
38. Ефимов, К.С. О вполне регулярных графах с к — 10, А = 3 / К.С. Ефимов, А.А. Махнев, М.С. Нирова// Тр. Ин-та математики и механики УрО РАН,- 2010 - Т. 16, N 2,-С. 75-91.
39. Ефимов, К.С. Об автоморфизмах графа с параметрами (75,32,10,16) / К.С. Ефимов // Сиб. электрон. Мат. изв.- 2010.- Т. 7. С. 1-13.
Ризография НИЧ ГОУ ВПО УГТУ-УВД 620002, Екатеринбург, Мира, 19
Введение
1 Вполне регулярные графы с //, < А' — 261 +
1.1 Предварительные результаты.
1.2 Доказа гельство теоремы 1.
1.3 Доказательство предложения.
1.4 Доказательство теоремы 2 и следствия
2 Вполне регулярные графы с Ь\ —
2.1 Предварительные результаты.
2.2 Реберно регулярные графы больших степеней с bi = 6.
2.3 Графы с bi = 6, /х-подграфы большие или коклпковые.
2.4 Графы с bi = 6, //-подграфы малые, по не все кокликовые
2.5 Вполне регулярные графы с к = 10, Л = 3.
3 Автоморфизмы сильно регулярного графа с параметрами (75,32,10,16)
3.1 Предварительные результаты.
3.2 Автоморфизмы графа с параметрами (75,32,10,16)
3.3 Автоморфизмы точечного графа частичной геометрии pGг(4, 7)
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрии, что каждая конечная простая группа дейс твует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([!()]-] 13|, [29], [28]). Например, класс билдингов Титса характеризует группы лиева типа (см. [32]). Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов (см. [10]).
Пусть G — транзитивная группа подстановок на множестве Если стабилизатор Gp точки р £ Г2, имеет г орбит на то говорят, что G имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р\. Д(р), Г(р). Тогда по группе G удастся построить сильно регулярный граф Г, множество вершин которого О, и две вершины p,q смежны в Г, если q Е Г(р) (см. [17]).
Д. Хигман ([17|-[23]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзнтивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметричность графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получепы в пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп па и вершинах или в других обозначениях треугольный граф Т(п). Этот грае}) является сильно регулярным графом с параметрами — 2), п — 2,4).
В работах 1959-60 годов Л. Чан г ([16]) и А. Хоффман ([24], [25)) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т{8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году (см.[15]).
Реберный граф L(Knhn) полного многодольного графа К7щп является ко-реберно регулярным графом с параметрами (mn,m + п — 2,2). Граф К1Г, -п называют m х п решеткой. При m = п решетчатый граф является сильно регулярным графом с параметрами (п2, 2т? — 2, п — 2,2). С. Шрикхандс в [31 ] показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (д, = 4).
Результаты Л. Чанга и С. Шрикханде были объединены Дж. Зейделем ([30]), который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдсль показал, что кроме треугольных графов Т(п) и решетчатых п х тг-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Для изучения реберно регулярных графов полезным оказался метод хороших пар и его обобщения.
Рассматриваются неориентированные графы без петель и кратных ребер. Если га, Ъ - вершины графа Г, то через d(a, b) обозначается расстояние между а и 6, а через ГДга) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г] (а) называется окрестностью в ерш mm, a, и обозначается через [а]. Окрестность вершины называется локальным подграфом. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярны и графом степени к, если [а,] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберпо регулярным графом е паральетралш (v,k, Л), если Г содержит v вершин, является регулярным степени к. и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (v, к. А, /г), если Г реберно регулярен с соответствующими параметрами и под гриф [с/]П[6] содержит /1 вершин в случае d(a, Ъ) = 2. Вполне регулярный граф диаметра 2 называется силы/о регулярным графом.
Число вершин в [а] П [Ь] обозначим через Л(а, 6), если d(a,h) = 1, а соответствующий подграф назовем Х-подгрпфо и.
Если d(a,b) = 2, то число вершин в [а] П [Ъ] обозначим через //(а, 6), a соответствующий подграф назовем fj-подграфом.
Если вершины и, w находятся на расстоянии г в Г, то через bj(u, w) (через Cj(u:w)) обозначим число вершин в пересечении Гг-+х(и)
Рг-1 (гг)) с Г(?и). Заметим, что в реберно регулярном графе число bi(u,w) не зависит от выбора смежных вершин n,w и обозначается через бьГраф Г диаметра d называется дистанционно регулярным с массивом пересечений {bo, bd-ъ съ ■ • • • cd}, если значения bi(u. w) и с-,(и, w) не зависят от выбора вершин u,w на расстоянии i в Г для любого ? = 0,d.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом,, если [а] лежит и Т для любой вершины а графа Г. Если при этом класс F состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локально А-графом.
Пусть Г - реберно регулярный граф с параметрами (г;, к, Л) и Ь\ = А*—Л—1. Пара вернтин u,w называется (почти) хорошей, если d(u,w) = 2 и ц(и.?п) равно к — 26i + 1 (равно к — 2Ь[ + 2). Тройка вершин (u,w,z) называется почти) хорошей, если ш, z Е Г2(11) и w) + /1(1/,, z) не больше 2к — 4/д + 3 (равно 2к - Щ + 4).
Если jj,(u,w) = к — 2b\ + 1, то подграф [и] П [?<;] является кликой и [d\ С и1 U wA для любой вершины d Е [и] Г) [wj.
Если Г содержит хорошую тройку (u,w,z). то подграф [г/,] П [ги] П [z] содержит не более одной вершины.
Аналогичный результат для почти хороших троек был получен А.А. Мах-невым и его учениками:
Пусть Г — связный реберно регулярный граф с параметрами (г>, к. Л), к = З61+7 и 7 > —2. Если (it, w, z) — почти хорошая тройка и Д = [it] П[ги]П[г] — непустой граф, то вершины w. z смежны и выполняется одно из следующих утверждений:
1) |Л| < 2 н 7 < —1;
2) подграф А является 3-кликой, bi = 6, к — 16 и v = 31;
3) подграф Л является 3-кликой, Ъ\ = 3 и Г — граф Клебша;
4) подграф Д является 4-кликой, Ь\ = 5 и Г - граф Шлефли.
С помощью этого результа та были получены новые верхние границы для числа вершин графов с к > ?>Ъ\ — 2. Теория хороших пар используется в диссертации при изучении графов с ц < к — 2Ь\ 3 и графов с Ь\ = 6.
Целыо диссертации является решение следующих задач:
1) изучить вполне регулярные графы с //. < к — 2Ь\ + 3;
2) изучить вполне регулярные графы с Ъ\ = 6;
3) найти возможные автоморфизмы сильно регулярного графа с параметрами (75,32,10,16).
Основными методами исследования являются методы теории конечных групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
1. Исследованы вполне регулярные графы с параметрами (v, к, А) и /1 < к -26) +3.
2. Исследованы вполне регулярные графы с = 6.
3. Выяснены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32, 10,16) и ) точ-пепо строение группы автоморфизмов указанного графа, в случае, когда он является точечным графом частичной геометрии р(?2(4, 7). Рассмотрение данного случая завершает изучение автоморфизмов частичных геометрий pG2(4,t).
Работа носит теоретический характер. Результаты продолжают изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Результаты диссертации докладывались на международной алгебраической конференции в Санкт-Петербурге (2007 г.), VII международной школе-конференции по теории групп (Челябинск, 2008 г.), международной школе-конференции по теории групп, посвященной 80-летию со дня рождения Л.И.Коетрига (Нальчик, 2009 г.), и на 39-й, 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2008-2010 гг.).
Результаты работы докладывались и обсуждались на алгебраических семинарах IIMM УрО РАН.
Основные результаты диссертации опубликованы в работах [33]-[41]. Работы |33]-|40] выполнены в нераздельном соавторстве с А.А. Махнсвым.
Работа состоит из введения, трех глав и списка цитированной литера туры, содержащего 39 наименований.
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются вполне регулярные графы с ji < к — 2Ь\ + 3. Во второй главе работы исследуются вполне регулярные графы с b 1 = 6. В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75,32,10,16).
Приведем основные результаты диссертации.
Пусть Г — сильно регулярный граф с параметрами (v, к, Л, д), Ь\ = к — Х — 1 и д = к — 261 + х. Если Г имеет целое собственное значение — т и т > 1, то х = in + b\(m — 2)/(m — l). Легко понять, что х — 1 (каждая пара несмежных вершин в силыю регулярном графе является хорошей) тогда и только тогда, когда. Г является пятиугольником.
Если Г — полный многодольный граф, то к = (п — l)(b\ +1) = д, поэтому х = 2Ь\. Таким образом для любого четного х имеется бесконечное семейство полных многодольиых графов с долями порядка х/2 -flu //, — к — 2Ь\ + х.
Если Г — граф с параметрами (4д + 1, 2д, // — 1, //,), то Ь\ = ц = х и 4х + 1 — сумма квадратов двух целых чисел. Значит, для нечетного х такого, что 4ж+1 не является суммой квадратов двух целых чисел, не существуют сильно регулярные графы с ц = к — 2Ъ\ + х и параметрами (4.x + 1, 2.r, х — 1, х).
Пример 1. Если + 1 = рп, р - простое число, то граф Пэли Р(р"), вершинами которого являются элементы поля F порядка рп и две вершины смежны тогда и только тогда, когда их разность является ненулевым квадратом в F, является сильно регулярным графом с параметрами (4.x + 1,2а;, ж — 1,ж).
Наименьшее нечетное х такое, что Ах + 1 не является суммой квадратов двух целых чисел, равно 5.
Если Г — псевдогеометрический граф для pGa(s,t). то к = s(t + 1). b\ = t(s -cv + 1). /i = a(t + 1) и x = (t - l)(s - a) + 21.
В случае x = 5 можно взять t = 2, s — a ~ 1. Таким образом, для графа
GQ(2, 2) имеем x = 5.
Теперь можно сформулировать ряд предположений.
Проблема А. Верно ли, что для любого натурального числа х существует сильно регулярный граф с ц = к — 2Ъ\ + х У
Проблема D. Верно ли. что для любого нечетного числа х существует лишь конечное число сильно регулярных графов с р = к — 2Ь\ + х?
Проблема С. Для каких четных чисел х существуют, бесконечные серии сильно регулярных грифов с ц = к — 2Ь\ + х и к > ц?
Первая глава направлена на изучение этих проблем.
Пусть Г является связным реберно регулярным графом с параметрами (г>, /с, Л) и Ь[ = к — Л — 1. Тогда для любых вершин u,w с d(u, w) — 2 имеем p(u,w) = к — 2Ъ\ + ж, где 1 < х < 2Ь\. В работе классифицированы вполне регулярные графы с х < 3.
Следующие результаты является основными в главе I.
Теорема 1 Пусть х натуральное число. Тогда выполняются следующие утверждения:
1) если х нечетно, то существует, сильно регулярный граф с // = к — 2Ъ\ + х;
2) если х > 3, 7по существует, лишь конечное число сильно регулярных графов ск>р,иц = к — 2Ь\ + х.
Предложение 1 Пусть Г — сильно регулярный граф) с параметрами (v, к, Л, ц), рь = к — 2Ь\ +х < к и 3 < х < 10. Если Г имеет целое собственное з?ш-чение —т, то х — т + Ь\{т — 2)/(т — 1) и выполняется одно их следующих утверждений:
1) х 6 {3,4} и Г — граф Пэли с параметрами (4х + 1, 2х, х — 1, х);
2) х = 5 и Г является дополнительным графом к 4 х -{-решетке, треугольному граф) у Г (С)) или графу Клебша;
3) х — б и Г является одним из следующих графов: (г) граф) 11 эли с параметрами (25,12, 5, 6). гг) граф Хофмана-Сипглтона или его дополнение,
Ш) граф с параметрами (26. 10.3,4) или его дополнение;
4) х = 7 и Г ябляется одним из следующих графов: (г) граф Пэли с параметрами (29.14, 6, 7), гг) псевдогеометрический граф) для GQ(4,2), £>С?2(5,2). рСз(6, 2) или pG4( 7,2), дополнительный граф для псевдогеометрического графа, обобщенного четырехугольника GQ(3.3) или для графа Гевиртца;
5) х = 8 и Г является одним из следуют,их графов: г) граф с параметрам/и (85,14,3,2), (49,18,7,6) или (49,32,21,20), (гг) дополнительный граф для 5 х Ъ-решетки или для треугольного графа Т( 7);
6) х = 9 и Г является одним из следующих графов: (г) граф с ■параметрами (37,18, 8, 9) или (69, 20, 7, 5), гг) псевдогеометрический графом для, pG-)(7.i 2) шш Л/г л рСз(8, 2), (///) дополнительный граф для псевдогеометрического графа обобщенного четырехугольника, GQ(3,5) или для граф>а с параметрами (77,16,0,6);
7) ж = 10 и Г является одним из следующих графов: г) граф) с параметрами (41, 20, 9,10) или граф Гевиртца с параметрами (56,10,0,2), гг) псевдогеометрический граф для р(?2(8, 2), pG-j(9,2), pGo(8,3), pG3(5,3), рС2(4,3) или для GQ(3,3), ггг) дополнительный граф для графа с параметрами (81,20,1,6) или для псевдогеометричсского графа геометрwu pG^(7, 2), iu) 6 х 6-решетка. треугольный граф Т(8), граф Шлефли ил,и один из трех графов Чанга.
В теореме Ливиигегона-Тэйлора, (теорема 1.3.3 из [10]) доказано, что во вполне регулярном графе выполняется неравенство /i > к — 2&1 + 1 и описаны графы с fj = A; —26i + l. Белоусов И.Н. и Махнев А.А. ([8]) классифицировали вполне регулярные графы с //, = & — 2Ь[ + 2. В диссертации рассматривается следующий случай.
Теорема 2 Пусть Г - вполне регулярный граф с параметрами (г>, к, А,//) и fj, = к - 2Ь\ 4-х', ж < 3. Тогда выполняется одно из следующих утверждений:
1) .г = 1 и Г — граф икосаэдра или граф прямых регулярного графа без треугольников, имеющего обхват, больший 4;
2) х = 2 и Г — граф Зейделя или тривалентный граф без треугольников диа метра, большего 2, с /х = 1:
3) х — 3 и Г один из следующих графов: граф Пэли с параметрами (13,6,2,3). куб или граф Клейна,
И) граф Тэйлора с параметрами (&Ь\ — 4,3/^ — 3, 2&i — 4, Ъ\) и Ъ\ £ {4,6,10}, ггг) регулярный граф без треугольников стен сии 4 или граф с Ь\ = 4, к = 6 и А = 1.
Для дистанционно регулярных графов получаем
Следствие 1 Пусть Г — дистанционно регулярный граф диаметра, большего 2, с // = к — 2Ь\ + х и х < 3. Тогда выполи,ж тся одно из следующих утверждений:
1) х = 1 и Г — граф икосаэдра, п-угольник, п > 6; реберный граф графа Мура или флаг-граф регулярного обобщенного п-уголышка, п £ {3,4,б}; порядка (s, s) для некоторого s;
2) .г = 2 и Г - додекаэдр, граф Хивуда, Паппа. Кокстера, Дсзарга, Бигза-Сим,са, Фостера или т-клетка Татта, т Е {8,12};
3) х = 3 и Г - один из следующих графов: г) куб или граф Клейна, а) граф Т.) и лора с параметрами (66i — 4, 3fri — 3, 2b\ — 4, 61) и 1ц G {4,6,10}. in) нечетный граф О4, его двудольное удвоение, граф инцидентности PG(2, 3), AG{'2, 3) с удаленным классом параллельных прямых, GQ(3, 3) или GH( 3,3).
При изучении реберно регулярных графов с k > f(b\) для некоторых функции / удаетея установить оценку v < g(k) (или получить описание графов, для которых не выполняется оценка v < g(k)). Так, в [10, лемма 1.4.2] доказано, что если Г — связный неполный реберпо регулярный граф с параметрами (и, к, А), в котором к > ЗЬ\, то диаметр Г равен 2 и v < 2к — 2. Фактически доказано, что v < к — 2 + З61 + S/(b\ + 1), it уточнение границы для числа вершин потребует описания графов с малыми значениями Ь\ и графов, насыщенных хорошими парами вершин.
В монографии Броувера, Коэна и Ноймайера доказано, что связный реберно регулярный граф с b\ = 1 является многоугольником или полным мпо-годольпым с долями порядка 2. Кроме гого, ранее исследовались реберно регулярные графы с Ъ\ < 5 (|9|, [5]). В данной работе изучаются вполне регулярные графы с Ь\ = 6.
Основным результатом второй главы являются
Теорема 3 Пусть Г — связный реберно регулярный граф с параметрами (v, к, А). Если Ъ\ = 6 и к > 22; то Г полный многодолъный граф Кгх7, г > 5 или граф из МР(6).
Теорема 4 Пусть Г — связный вполне регулярный граф) с параметрами (v, /с, А, //) и Ь\ = 6. Тогда Г является одним из следующих графов:
1) полный многодольный граф Krxj, граф с параметрами (25,12, 5, 6). 7х 7-решетка, треугольный граф Т(9). дополнительный граф к 5 х Ъ-решетке или к треугольному графу Т(7), граф Хофмапа-Синглтона или его дополнение, граф с параметрами (26,10.3,4) или его дополнение;
2) полный двудольный граф Kgs с удалелтым максимальным пар о сочетанием, граф Тэйлора с параметрам.и (28,13,6,6), в котором окрестности вершин изоморфны графу Поли Р( 13) или граф Тойлора, с параметрам,и (32.15,8,6), в котором, окрестности вершин изоморфны треугольному граФУ Т(6);
3) fj = 4, к = 12, сз(и,у) > 6 для любых вершин и, у с d(u,y) = 3 и диаметр Г равен 3;
4)/i, = 3u9<K 12;
5) ц, = 2 и 7 < к < 11;
6) jj, = 1 и окрестность каждой вершины является 7-кокликои, объединением, изолированны г п-клик для п = 2, 3 или 6.
Таким образом, изучение вполне регулярных графов с Ь\ = 6 редуцируется к случаю к = 10, Л = 3.
Теорема 5 Пусть Г -- связный вполне регулярный -граф с параметрами (г, 10,3,/х). Тогда выполняется одно из следующих утверждений:
1) диаметр Г равен 2 иТ является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
2) /л = 3 диаметр Г равен 3 и 34 < v < 37;
3) ц = 2 и Г является графом Конвея-Смита или графом Доро.
Рассматривая дистанционно регулярные графы, получаем
Следствие 2 Пусть Г — дистанционно регулярный граф с к = 10, Л = 3. Тогда выполняется одно из следующих утверждений:
1) диаметр Г равен 2 и Г является дополнительным графом к треугольному графу Т(7) или одним из десяти графов с параметрами (28,10,3,4);
2) // = 2 и Г является графом Конвея-Смита или графом Доро.
В третьей главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (75. 32,10,16) и уточняется строение группы автоморфизмов указанного графа, в случае, когда он является точечным графом частичной геометрии pG2(4.7).
Для изучения возможных порядков и подграфов неподвижных точек автоморфизмов дистанционно регулярных графов Г. Хигмен предложил оригинальный метод, использующий теорию характеров конечных групп. Этот метод изложен в монографии П. Камерона (см.[14]), причем он применялся только к изучению инволютивиых автоморфизмов сильно регулярного графа с параметрами (3250,57,0,1). Позднее, в работах [2]-[3] изучаиись автоморфизмы сильно регулярных графов с малыми числами пересечений. В данной работе л тот метод применяется для изучения автоморфизмов сильно регулярного графа с параметрами (75,32,10,16).
Основными результатами третьей главы являются следующие теорема и следствие.
Теорема 6 Пусть Г — сильно регулярный граф с пара метрами (75, 32,10,16), д элемент простого порядка р из Ant(r) и Q, = Fix(g). Тогда верно одно из утверждений:
1) Г2 — пустой граф, р = 3 и n\(g) е {0, 30,60} или р — 5 и а\(д) делится на 50;
2) Q является п-кликой, и либо п = 3, р = 3 и ос\{д) — 6 делится на 30, либо п = 5, р — 7 и о>\(д) = 0;
3) Q является т-кокликой, р = 2, m нечетно, 3 < т < 15, o;i(/;) — 2т делится па 10, и в случае т— 15 пара (О, Г — является (15, 60, 32, 8,16)-схемои;
4) содержит 2-лапу, р = 2 и либо г) О объединение изолированной вершины и октаэдра, либо и) Q — объединение 'изолированной вершины и подграфа, либо (in) |Q| = 2t + 1. 4 < t < 15 или t = 17.
Следствие 3 Пусть Г - точечный граф частичной геометрии pG^^, 7), G - группа автоморф) из мое графа Г, g - элемент простого порядка р из G и Q = Vix(g). Тогда |G| делит 21 • 3 • 52 и верно одно из утверждений: ■
1) Q — пустой граф, либо р = 3 и а \(д) € {0,30,60}, либо р = 5 и ai(g) G {0,50}:
2) р = 2 и либо г) gl\ (д) = 0; О, — треугольный граф Т(6), каждая точка из Г — Q смслсна с 6 точками из Q или Q является rn-кокликой и т £.{5,15}, либо (ii) а\ (д) ф 0; Q,.- объединение октаэдра и I изолированных точек. 1 < I < 11, I нечетно или О — объединение изолированной точки и точечного графа для pG-2(2,3).
1. Махнев, А.Л. Об одном классе реберно регулярных графов/ А. А. Махнсв, И.М. Мннакова// Известия Гомельского гос. ун-та- 2000.- Т.З.- 0.115-154.
2. Махиев, А.А. Об автоморфизмах сильно регулярных графов с Л = О, li = 2 А.А. Махиев, В.В. Носов// Мат. сб.- 2004.- Т. 185, №3,- С.47-68.
3. Махнев, А.А. О сильной регулярности некоторых реберно регулярных графов/ А.А. Махнев// Известия РАН, сер. матем,- 2001,- Т.68.- С.159-172.
4. Махнев, А.А. О псевдогеометрических графах некоторых частичных геометрий/ А.А. Махнев // Вопросы алгебры. Выпуск 11. Гомель: Изд-во Гомельского ун-та. 1997. С. 60-67.
5. Казарина, В.И. О реберно регулярных графах с Ъ\ = 5/ В.И. Казарина, А.А. Махнев // Межд. конф. "Алгебра, логика и кибернетика". Тез. докл. Иркутск 2001, 159-161.
6. Brouwer, A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag- 1989,- 495 c.
7. Brouwer, A.E. The Gewirtz graph: an exercize in the theory of graph spectra/ A.E. Brouwer, W.H. Haemers// Euiop. J. Comb.- 1993,- Vol.14.- P.397-407.
8. Buekenhout, F. Foundations of incidence geometry , F. Buekenhout 1 / Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsevcr Science. Amsterdam.- 1995.- P.63-107.
9. Higman, D.G. Finite permutation groups of rank 3/ D.G. Higman// Math. Z- 1964,- Vol.86.- P. 145-156.18| Higman, D.G. On finite affine planes of rank 3/ D.G. Higman// Math. Z.-1968,- Vol.104.- P. 147-149.
10. Higman. D.G. A survey of some questions and resalts about rank 3 permutation groups/ D.G. Higman// Actcs, Cjngrcs Int. Math. Rome.- 1970.-Vol.l.- P.361^365.
11. Higman, D.G. Characterization of families of rank 3 permutation groups by the subdegrees I, II/ D.G. Higman/ ' Arth. Math.- 1970,- Vol.21.- P.151-156; 353-361.
12. Higman, D.G. Coherent configurations/ D.G. Higman// Rend. Sem. Mat.Univ. Padova.- 1970.- Vol.44.- P. 1-26.
13. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960,- Vol.31.- P.492-497.
14. Hoffman, A.J. On the cxceptioal case in a characterization of the arcs of complete graphs/A.J. Hoffman// IBM J. Res. Develop.- I960.- Vol.4.- P.487-496.
15. Hoffman, A.J. On the line-graphs of the complete bipartite, graph/ A.J. Hoffman// Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.
16. Macay M. Search for properties of the missing Moore graph/ Macay M. Siran J. // Linear Algebra and its Appl. 2009.
17. Numata, M. On a characterization of a class of regular graphs/ AI. Numata// Osaka J. Math.- 1974,- Vol.11.- P.389-100.
18. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher Lecture series 8.- Cambridge: University press.-1997.
19. Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl 1968 - Vol.1.- P.281-298.
20. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhandc// Ann. Math. Stat.- 1959,- Vol.30.- P.781-798.
21. Tils, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации
22. Ефимов, К.С. О сильно регулярных графах с /1 = к — 2Ъ{ + х / К.С Ефимов, А.А. Махнев // Классы групп, алгебр и пх приложения, Гомель2007.- Тез. докл. С. 68-69
23. Ефимов, К.С. Вполне регулярные графы с ц < к — 2&1 + 3 К.С. Ефимов, А.А. Ма,хпев // Межд. алгебр, коне]). Санкт-Петербург 2007.- Тез. докл. С. 29-31.
24. Ефимов, К.С. Вполне регулярные графы с Ъ\ = 6 / К.С. Ефимов, А.А. Махнев // Труды 39-й Всеросе. молод, конф. Изд-во 11 ММ УрО РАН, Екатеринбург 2008. С. 16-18.
25. Ефимов, К.С. Вполне регулярные графы с ц < к~2^+3 / К.С. Ефимов, А.А. Махнев // Труды Института математики НАН Беларуси 2008.- Т. 16, N 1. О. 28-39.
26. Ефимов, К.С. О реберно регулярных графах с Ъ\ = 6 / К.С. Ефимов, А. А. Махнев // VII Международная школа конференция по теории групп2008,- Тез. докл. С. 48-51.
27. Ефимов, К.С. Вполне регулярные графы с Ь\ = 6 / К.С. Ефимов, А.А. Махнев /', Журнал Сибирского Федерального ун-та 2009.- Т. 2, N 1. С. 63 77.
28. Ефимов, К.С. Об автоморфизмах графа с параметрами (75,32,10,16) / К.С. Ефимов // Сибирские Электронные Математические известия2010.- Т. 7. С. 1-13.
