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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

004615041 На правах рукописи

ТОКБАЕВА Альбина Аниуаровна

ПОЧТИ ХОРОШИЕ ТРОЙКИ ВЕРШИН В ГРАФАХ И АВТОМОРФИЗМЫ ГРАФОВ

01.01.06 — математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

-2 п£Н 2010

Екатеринбург — 2010

004615041

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН.

Научный руководитель:

доктор физико-математических наук,

профессор, чл.-корр. РАН МАХНЕВ Алексапдр Алексеевич

Официальные оппоненты:

доктор физико-математических наук, профессор БАРАНСКИЙ Виталий Анатольевич

кандидат физико-математических наук ЧУКСИНА Наталья Владимировна

Ведущая организация: Южно-Уральский государственный университет

Защита состоится 23 ноября 2010 года в 15.30 часов на заседании специализированного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в научной библиотеке Ипститута математики и механики УрО РАН (г. Екатеринбург, ул. С. Ковалевской, 16).

Автореферат разослан ¿¿октября 2010 года

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук

И."Н. Белоусов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы. Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [12]. Например, класс билдингов Титса характеризует группы лиева типа [22]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [11].

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах XX века. Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами (7г(га-1)/2,2(п-2),п-2,4). В работах 1959-60 годов Л. Чанг [15] и А. Хоффман ([17], [18]) независимо показали, что треугольный граф Т[п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая тг = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [14].

Реберный граф Ь(Кт.п) полного многодольного графа Кт,п является кореберно регулярным графом с параметрами (тп, т + п — 2,2). Граф Ц^т.п) называют т х п-решеткой. При т = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2,2). С. Шрикханде в [21] показал, что граф, имеющий параметры пх п решетки является либо решеткой, либо графом Шрикханде (п = 4).

Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [19] были объединены Дж. Зейделем [20], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через ¿(а, Ь) обозначается расстояние между а и Ь, а через 1\(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г

от вершины а.

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

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

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

Граф Г называется вполне регулярным графом с параметрами (v,k,X,ß), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [6] содержит ß вершин в случае d(a, b) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.

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

Пусть Г — реберно регулярный граф с параметрами (v, к, А) и Ъ\ = к—Л— 1. Пара вершин и, w называется (почти) хорошей, если d(u, w) = 2 и ß(u, w) равно к — 2b\ + 1 (равно к — 2bi + 2). Тройка вершин (u, w, z) называется (почти) хорошей, если to, z G Гг(и) и ß{u,w) + p(u,z) не больше 2к - 4&i + 3 (равно 2к — 4Ь\ + 4).

Основанием для развития метода хороших пар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (v, к, А) и Ь\ = к — А — 1. Если вершины и, w находятся на расстоянии 2 в Г, то выполняются следующие утверждения:

(1) степень любой вершины в /х-подграфе из Г не меньше к — 2Ь\\

(2) вершина d имеет степень а в графе [и] П [го], тогда и только тогда, когда [d] содержит точно а — (к — 2bi) вершин вне u1 U ад1;

(3) если ß(u, w) = к — 2bi + 1, то подграф [и] П [iu] является кликой и [с?] С и1 U гу1 для любой вершины d G [и] П [ги];

(4) если Г— (u±UwJ-) содержит единственную вершину z, то ц(и, z) = ß{w, z).

A.A. Махнев [1] получил следующее свойство хороших троек:

Пусть Г — реберно регулярный граф, содержащий хорошую тройку (и, w, z) и 5 = |[и] П [и;] n[z]|. Тогда выполняются следующие утвержде-

ния:

(1) если го) = ц(и:г) = к — 2Ь\ + 1, то 6 = 0 в случае, когда вершины го, г не смежны и 5 < 1 в случае, когда вершины го, 2 смежны;

(2) если ц(и, го) + ц(и, г) = 2к — 4Ь\ + 3, то 5 < 1.

С помощью этих результатов получается новое доказательство классификации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] - [5]). В [6] была доказана

Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (у, к, А), к = ЗЬ\ +7 и 7 > —2. Если (и, го, г) — почти хорошая тройка и А = [и] П [го] П [г] — непустой граф, то вершины го, г смежны и выполняется одно из следующих утверждений:

(1) |Д| < 2 и 7 < -1;

(2) подграф А является 3-кликой, = 6, к = 16 и V = 31;

(3) подграф А является Ъ-кликой, Ь\ = 3 и Г — граф Клебша;

(4) подграф А является 4-кликой, Ь\ = 5 и Г — граф Шлефли.

С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов (в случае к > Исаковой М.М., в случае А; = З61 — 1 Чуксшгой Н.В. и в случае к = — 2 Токбаевой

А.А.).

Цель диссертации. Целью данной работы является решение следующих задач:

1. Найти новые верхние границы для числа вершин реберно регулярных графов с к = 3Ь\ — 2.

2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (76,35,18,14).

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (243,66,9,21).

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

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.

1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к = 3bi — 2.

2. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (76,35,18,14).

3. Определены возможные порядки элементов группы G автоморфизмов сильно регулярного графа с параметрами (243,66,9,21), в частности, установлено, что 7r(G) С {2,3,5,7,11}. Доказано, что граф Г не является реберно симметричным.

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

Апробация работы. Основные результаты работы докладывались

на:

Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010г.).

Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.

Публикации. Основные результаты диссертации опубликованы в работах [23]—[29]. Работы [23]-[28] выполнены в нераздельном соавторстве с A.A. Махневым.

Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем диссертации — 91 стр.

Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы. В главе I рассматриваются реберно регулярные графы с к = ЗЬ\ — 2. Во второй главе выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (76,35,18,14). В третьей главе работы определяются возможные автоморфизмы сильно регулярного

графа Г с параметрами (243,66,9,21). Доказано также, что Г не является реберно симметричным.

Результаты диссертации.

Пусть Г — связный реберно регулярный граф с параметрами (v, к, А), к > 3Ьх. Тогда диаметр Г не больше 2. Основным результатом главы 1 является

Теорема 1 Пусть Г — связный неполный реберно регулярный граф с параметрами (г>, к, А) и к = 3bi — 2. Тогда либо граф Г является реберным графом тривалентного графа без треугольников, либо Г имеет диаметр 2 и выполняется одно из утверэ/сдений:

(1) для некоторой вершины и в Г найдутся две вершины w,z, образующие хорошие пары си, и либо вершины w, z смежны и v < 5i>i + 1, либо вершины tu, z не смео/сны и v < 6bi — 7;

(2) в Г пет вершин, лежащих в двух хороших парах, некоторая вершина и образует хорошую пару с w, и либо v < 6bi — 6, либо b\ = 6 и v < 31;

(3) в Г нет хороших пар и либо

(г) Г не содерэюит почти хороших пар и v < 66i — 6, либо (И) Г содерэюит почти хорошую пару и либо Г — треугольный граф Т(7) или 3 х 3-решетка, либо v < 6bi — 6, либо bi = 6 и v < 31.

Эта теорема уточняет границу для числа вершин, полученную A.A. Махневым и Д.В. Падучих [10].

Частичной геометрией pGa(s, t) называется система инцидентности, состоящая из точек и прямых, в которой каждая прямая содержит s + 1 точку, каждая точка лежит на t + 1 прямой (две прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L. Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s,t). Если а = t, то геометрия называется сетью. Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на одной прямой. Легко понять, что точечный граф частичной геометрии pGa(s, t) сильно регулярен с параметрами: v = (s + 1)(1 + st/a), k = s{t + 1), Л = (5 - 1) + (а - l)t, (j, = a{t + 1).

Любой сильно регулярный граф с такими параметрами для некоторых a,s,t называется псевдогеометрическим графом для pOa(s,t).

В теореме 2 из [7] найдены параметры сильно регулярных графов, в которых окрестности вершин являются псевдогеометрическими графами для pGx(2x,t), где х < 3. В случае х = 2 граф имеет параметры (210,95,40,45), и возможные автоморфизмы такого графа изучались в [8]. В случае х = 3 имеется много возможностей для параметров графа. Но если t = 2, то возможны лишь параметры (64,35,18,20) или (76,35,18,14). Во второй главе диссертации найдены возможные автоморфизмы сильно регулярного графа с параметрами (76,35,18,14) и определены подграфы их неподвижных точек. Для автоморфизма g через »¿(g) обозначим число пар вершин (г«, и9) таких, что d(u, и9) = г.

Теорема 2 Пусть Г — сшито регулярный граф с параметрами (76,35,18,14), g — элемент простого порядка р из Aut(r) и fi = Fix(g). Тогда верно одно из утверждений:

(1) fi — пустой граф, р = 2 и ai(g) € {8,28,48,68} или р = 19 и *i{g) = 38;

(2) fi является п-кликой, либо п = 1, р = 5 и а\(д) € {25,75}, либо р=2ипв {4,6,8,10};

(3) fi является 6-кокликой, р = 7, ai(g) = 70 и любая вершина из Г — fi смежна точно с 3 вершинами из fi;

(4) fi является объединением т изолированных клик порядков щ,..., пт, т > 2, р = 2 и любое число щ четно;

(5) fi codepoicum 2-лапу, р = 3 и либо

(г) fi — четырехугольник и а\(g) £ {6,36,66}, либо (гг) |fi| = 10, ai(s) € {18,48} и fi является К^-подграфом или 5 х 2-решеткой, либо

(Иг) |fi| = 13 и ai(g) € {9,39}, либо (iv) |fi| = 16 гг ai(g) £ {0,30,60};

(6) fi содержит 2-лапу, р = 2 и либо

(г) fi — прямая сумма 2-коклики и 2К2, cti(g) € {10,30,50,70},

либо

(гг) |fi| 6 {8,10,...,32}, либо (iii) |fi| =36 и ai(g) = 40.

Для подмножества вершин S графа Г через Г(5) обозначим Па€з([а] — S). Граф Г называется f-изорегулярным, если для любого i <t и любого г-вершинного подмножества S число |Г(5)| зависит только от изоморфного типа подграфа, индуцированного S. Граф Г на v вершинах называется абсолютно изорегулярным, если он является (v— 1)-изорегулярным. Камерон [13, теорема 8.21] доказал, что каждый 5-изорегулярный граф Г является абсолютно изорегулярным, и с точностью до перехода к дополнительному графу, Г является полным многодольным графом КтУп. пятиугольником, или 3 х 3-решеткой. А каждый точно 4-изорегулярный граф является экстремальным графом Смит (с точностью до перехода к дополнительному графу, Г является псевдогеометрическим графом для pGr(2r,2r3 + 3г2 — 1)). Обозначим такой граф через Izo(r). При г = 1 получим точечный граф единственного обобщенного четырехугольника порядка (2,4), а при г = 2 — граф Маклафлина. A.A. Махнев [9] доказал, что Izo(r) не существует в случае г = 3. Вторая окрестность вершины в графе Izo{r) при г = 3 является сильно регулярным графом с параметрами (640,243,66,108). Вопрос о существовании графа с такими параметрами открыт.

Пусть Г — сильно регулярный граф с параметрами (640,243,66,108), а — вершина графа Г. Тогда Г имеет собственные значения к = 243, г = 3, s = —45 и достигается равенство во втором условии Крей-на: (s + 1 )(к + s + 2rs) < (к + s)(r + I)2. Поэтому [а] является сильно регулярным графом с параметрами (243,66,9,21) и Гг(а) — сильно регулярный граф с параметрами (396,135,30,54). Таким образом, для исследования автоморфизмов сильно регулярного графа с параметрами (640,243,66,108) необходимо изучить автоморфизмы сильно регулярных графов с параметрами (243,66,9,21) и (396,135,30,54).

В третьей главе диссертации найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (243,66,9,21).

Теорема 3 Пусть Г является сильно регулярным графом с параметрами (243,66,9,21), д — автоморфизм простого порядка р графа Г, Q = Fix(<?). Тогда выполняется одно из следующих утверждений:

(1) fi — пустой граф, р = 3 и а\(д) сравнимо с 21 по модулю 54;

(2) Г2 является одновершинным графом, р = 11 и ос\(д) = 66;

(3) П является т-кокликой, т = 3t > 2, 1 < t < 14, р = 3 и а\(д)~9t сравнимо с 27 по модулю 54;

(4) ii — объединение трех клик порядка 4, р = 7 и а\ (д) = 63;

(5) р = 5 и либо

(г) Q является К^-подграфом, ai(g) € {15,105}, либо (И) |0| = 28 и ai(g) = 75, либо (ггг) |fi| = 33 и 0:1(5) = либо (iv) |ft| = 38 и ai(g) = 15;

(6) р = 3, |Г2| = 3t, Qi(sO/18 - (t + 3)/2 делится на 3 и 2 < t < 24 или t в {27,33};

(7) р = 2 и либо

(г) а\(д) = О, |П| делится на 3 и |П| < 93, либо (ii) а\{д) ф О, |П| <75 и 3 —3i + ai(g) делится на 36 или |Г2| = 107 и а^д) = 24.

Если граф является реберио симметричным, то он либо двудольный, либо является вершинно симметричным. Доказано, что сильно регулярный граф с параметрами (243,66,9,21) не является реберно симметричным.

Теорема 4 Пусть Г является сильно регулярным графом с параметрами (243,66,9,21). Тогда группа G = Aut(r) действует интранзитивно на множестве ребер графа Г.

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

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

[1] Махнев A.A.О хороших парах в реберно регулярных графах/ A.A. Махнев, A.A. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет. матем.-2003,- Т.15.- С.77-97.

[2] Махнев A.A. О хороших парах вершин в графах с к > ЗЬх — 2 / A.A. Махнев, И.М. Минакова// Труды Междунар. конф. "Алгебра и линейная оптимизация". Екатеринбург, 2002 - С.172-174.

[3] Белоусов И.Н. О почти хороших парах вершин в реберно регулярных графах / И.Н. Белоусов, A.A. Махнев // Известия Уральского госуниверситета.- 2005.- Т. 36, е 7,- С.35-48.

[4] Махнев A.A. О реберно регулярных графах, не содержащих хороших пар / A.A. Махнев, A.C. Омельченко // Известия Гомельского госунта.- 2008.- Т. 47. - С. 117-127.

[5] Махнев A.A. О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал.- 2008 - Т. 10, е 1,- С. 53-67.

[6] Махнев A.A. О почти хороших тройках вершин в реберно регулярных графах / В.И. Казарина, A.A. Махнев // X Белорусская матем. конф. Тез. докл. Минск,- 2008.- С. 46.

[7] Махнев A.A. О сильно регулярных графах с к = 2 ц и их расширениях / A.A. Махнев // Сиб. матем. журнал,- 2002,- Т. 43, е 3.- С. 609-619.

[8] Махнев A.A. Об автоморфизмах сильно регулярного графа с параметрами (210,95,40,45) / A.A. Махнев, Н.В. Чуксина // VII Международная школа-конференция по теории групп,- Тез. докл-Челябинск,- 2008,- С. 78-79.

[9] Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) / A.A. Махнев // Украинский матем. журнал.- 2002,- Т. 54, е 7.- С. 941-949.

[10] Падучих Д.В. Новая оценка для числа вершин реберно регулярных графов / A.A. Махнев, Д.В. Падучих // Сибирский матем. журнал.-2007,- Т. 48, е 4.- С. 817-832.

[11] Brouwer А.Е. Distance-regular graphs/ А.Е. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag.- 1989.- 495 c.

[12] Buekenhout F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. - Elsever Science. Amsterdam.- 1995.- P.63-107.

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

[14] Chang L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang// Sci. Record.- 1949,- Vol.3.- P.604-613.

[15] Chang L.C. Association schemes of partially balanced block designs with parameters v = 28, ni = 12, no = 15 and = 4/ L.C. Chang// Sci. Record.- 1950,- Vol.4.- P.12-18.

[16] Gardiner A. Homogeneous graphs / A.Gardiner //J. Comb. Theory.-1976.- V. 20.- P. 94-102.

[17] Hoffman A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960.- Vol.31.- P.492-497.

[18] 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.

[19] Hoffman A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman// Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.

[20] Seidel J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel// Linear Algebra and Appl.- 1968.- Vol.l.-P.281-298.

[21] Shrickhande S.S. The uniqueness of the association scheme/ S.S. Shrickhande// Ann. Math. Stat.- 1959,- Vol.30.- P.781-798.

[22] Tits J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics - Vol.386.

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

[23] Токбаева A.A. О числе вершин в реберно регулярных графах с к = 36i — 2 / A.A. Махнев, A.A. Токбаева // Труды 40-й Всеросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург.- 2009.- С. 32-35.

[24] Токбаева A.A. О числе вершин в реберно регулярных графах с к = 36i — 2 / A.A. Махнев, A.A. Токбаева // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина. КБГУ: Нальчик,- 2009. - С. 87-91.

[25] Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / A.A. Махнев, A.A. Токбаева // Тезисы 41-й Всеросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург- 2010.-С. 42-46.

[26] Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Теория групп и ее приложения. Труды межд. конф., посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик,- 2010,- С. 170-172.

[27] Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / A.A. Махнев, A.A. Токбаева // Труды ИММ УрО РАН,- 2010,- Т. 16, е 3,- С. 603-619.

[28] Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Владикавказский матем. журнал.- 2010 - Т. 12, е 4.

[29] Токбаева A.A. Граф с параметрами (243,66,9,21) не является реберно симметричным / A.A. Токбаева // Сибирские электронные матем. известия,- 2010.- Т. 7.- С. 155-161.

ТОКБАЕВА Альбина Анкуарошка

ПОЧТИ ХОРОШИЕ ТРОЙКИ ВЕРШИН В ГРАФАХ И АВТОМОРФИЗМЫ ГРАФОВ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

На правах рукописи

Формат 60*84/16. Печать офс. Бумага офс. Гарнитура «Таимо. Усл. печ. а. 1,0. Тираж 100 »и. Заказ 218. Отпечатано в Издательстве И.П. «Полиграфия». Лицензия № 3070706100020. КБР, г.Налъчкк, ул-Черньшквского, 131.

Введение

1 Реберно регулярные графы с к — Збх —

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

1.2 Хорошие пары вершин в графах с к = 3^1 — 2.

1.3 Оценка для числа вершин в графах с к = 3Ь\ —

2 Автоморфизмы графов с параметрами (76, 35.18,14)

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

2.2 Автоморфизмы графа с параметрами (76,35,18,14).

3 Автоморфизмы графа с параметрами (243,66,9,21)

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

3.2 Автоморфизмы графа с параметрами (243,66,9,21).

3.3 Автоморфизмы малых порядков.

3.4 Реберно симметричный случай.

Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([23], [24], [36], [21]). Например, класс билдингов Титса характеризует группы лиева типа [40]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].

Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах XX века. Пусть Ь(Кп) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т{п). Этот граф является сильно регулярным графом с параметрами (п(п — 1)/2, 2{п — 2),п — 2,4). В работах 1959-60 годов Л. Чанг [28] и А. Хоффман ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [27].

Реберный граф Ь(Кт^п) полного многодольного графа Кт>п является ко-реберно регулярным графом с параметрами (тп,т + п —2,2). Граф Ь(Кт:Т1) называют т х п-решеткой. При т — п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (п — 4).

Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейделем [37], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Пстерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ъ - вершины графа Г, то через с?(а, 6) обозначается расстояние между а и 6, а через Гг(а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.

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

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

Граф Г называется реберно регулярным графом с параметрами {у, к, А), если Г содержит V вершин, является регулярным степени /с, и каждое ребро из Г лежит в Л треугольниках.

Граф Г называется вполне регулярным графом с параметрами {у, к, Л, /л), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[6] содержит (1 вершин в случае 6) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.

Число вершин в [а] П [6] обозначим через Л(а, 6), если с1(а,Ь) = 1, а соответствующий подграф назовем \-подграфом.

Если с?(а, Ь) = 2, то число вершин в [а] П [6] обозначим через //(а, 6), а соответствующий подграф назовем ¡л-подграфом.

Если вершины и,ии находятся на расстоянии г в Г, то через ги) (через Сг(и, ии)) обозначим число вершин в пересечении Г,;+1 (и) (Ггх(г«)) с Г(т). Заметим, что в реберно регулярном графе число Ъ\{и^) не зависит от выбора смежных вершин и,ни и равно Ъ\ = к — А — 1.Граф Г диаметра с1 называется дистанционно регулярным с массивом пересечений {&о> Ьь ■ ■ •, Ьа-1, Сх,., со}, если значения Ь{(и, ги) и С((и, ги) не зависят от выбора вершин и,т на расстоянии г в Г для любого г = 0,

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

Пусть Г — реберно регулярный граф с параметрами (у, к, А) и Ъ\ = к—А—1. Пара вершин и,и> называется (почти) хорошей, если б1{и,ш) — 2 и ¡¿(и,ги) равно к — 26х + 1 (равно к — 2Ьг + 2). Тройка вершин (и,ги,г) называется (почти) хорошей, если ии, г е Г2(и) и [¿(и, ги) + дл(гл, г) не больше 2к — 4Ъ\ + 3 (равно 2к - 4&1 + 4).

Основанием для развития метода хороших пар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (и, к, А) и 61 = к — Л — 1. Если вершины и, ш находятся на расстоянии 2 в Г, то выполняются следующие утверждения:

1) степень любой вершины в /1-подграфе из Г не меньше к — 2Ьу,

2) вершина (I имеет степень а в графе [и] П [ги], тогда и только тогда, когда [с1] содержит точно а — {к — 2Ъ\) вершин вне и1- и ги1-]

3) если /1(и,ги) = к — 2Ъ\ + 1, то подграф [и] П [ги] является кликой и Щ С и1 и и)1- для любой вершины с1 Е [и] П [ги];

4) если Г — (и1- U г/г1) содержит единственную вершину z, то ц(и, z) — ß{w,z).

A.A. Махнев [1] получил следующее свойство хороших троек:

Пусть Г — реберно регулярный граф, содержащий хорошую тройку (u, w, z) и 8 = \[и] П И П [z]|. Тогда выполняются следующие утверждения:

1) если fi(u, w) = fi(u, z) = к — 2Ь\ + 1, то 6 = 0 в случае, когда вершины w, z не смежны и 6 < 1 в случае, когда вершины w, z смежны;

2) если ¡¿(и, w) + fi(u, w) = 2к — 4&i + 3, то 5 < 1.

С помощью этих результатов получается новое доказательство классификации графов Тсрвиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] — [5]). В [6]) была доказана

Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (v,k,X), к = 36i + 7 и 7 > —2. Если (u,w,z) — почти хорошая тройка и А = [и] П [w] П [z] — непустой граф, то вершины w, z смежны и выполняется одно из следующих утверждений:

1) |Д| < 2 и 7 < —1;

2) подграф Д является 3-кликой, 6i = 6, к = 16 и v = 31;

3) подграф Д является 3-кликой, Ьу = 3 и Г — граф Клебша;

4) подграф А является А-кликой, Ъ\ = 5 и Г — граф Шлефли.

С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов (в случае k > 36i Исаковой М.М., в случае к — 3bi — 1 Чуксиной Н.В. и в случае к = 3&i — 2 Токбаевой A.A.).

Цель диссертации. Целью данной работы является решение следующих задач:

1. Найти новые верхние границы для числа вершин реберно регулярных графов с к = 3&1 — 2.

2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (76,35,18,14).

3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (243,66,9,21).

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

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.

1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к = Збх — 2.

2. Определены возможные порядки элементов группы С автоморфизмов сильно регулярного графа с параметрами (76,35,18,14), в частности, установлено, что тг(С) С {2,3,5,7,19}.

3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (243,66,9,21). Доказано, что граф Г не является реберно симметричным.

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

Апробация работы. Основные результаты работы докладывались на:

Международной алгебраической конференции, посвященной 80-летию со дня рождения А.И. Кострикина (Нальчик, 2009 г.), на 40-й и 41-й Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2009-2010 гг.) и на Международной школе-конференции по теории групп, посвященной 75-летию со дня рождения В.А. Белоногова (Нальчик, 2010 г.).

Результаты работы докладывались и обсуждались на алгебраических семинарах ИММ УрО РАН и Кабардино-Балкарского госуниверситета.

Публикации. Основные результаты диссертации опубликованы в работах [41]-[47]. Работы [41]-[46] выполнены в нераздельном соавторстве с A.A. Мах-невым.

Структура и объем работы. Работа состоит из введения, трех глав и списка цитированной литературы, содержащего 47 наименований. Объем диссертации — 91 стр.

1. Махнев, А.А.О хороших парах в реберно регулярных графах/ A.A. Мах-нев, A.A. Веденев, А.Н. Кузнецов, В.В. Носов // Дискрет. матем.-2003.-Т.15.- С.77-97.

2. Махнев, A.A. О хороших парах вершин в графах с к > 3&i — 2 / A.A. Махнев, И.М. Минакова// Труды Междунар. конф. "Алгебра и линейная оптимизация". Екатеринбург, 2002 С. 172-1'74.

3. Белоусов, И.Н. О почти хороших парах вершин в реберно регулярных графах / И.Н. Белоусов, A.A. Махнев // Известия Уральского госуниверситета.- 2005.- Т. 36, № 7.- С.35-48.

4. Махнев A.A. О реберно регулярных графах, не содержащих хороших пар / A.A. Махнев, A.C. Омельченко // Известия Гомельского госун-та.-2008.- Т. 47. С. 117-127.

5. Махнев, A.A. О реберно регулярных графах, в которых каждая вершина лежит не более чем в одной хорошей паре / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал.- 2008.- Т. 10, № 1,- С. 53-67.

6. Махнев A.A. О почти хороших тройках вершин в реберно регулярных графах / В.И. Казарина, A.A. Махнев // X Белорусская матем. конф. Тез. докл. Минск,- 2008,- С. 46.

7. Махнев, A.A. О сильно регулярных графах с к = 2/i и их пасширениях /A.A. Махнев // Сиб. матем. журнал,- 2002,- Т. 43, № 3.- С. 609-619.

8. Махнев, A.A. Об автоморфизмах сильно регулярного графа с параметрами (95,40,12,20) / A.A. Махнев, Н.В. Чуксина // Владикавказский матем. журнал,- 2009.- Т. И, № 4.- С. 44-58.

9. Махнев, A.A. Об автоморфизмах графа Ашбахера/ A.A. Махнев, Д.В. Падучих // Алгебра и логика,- 2001,- Т.40, № 2.- С. 125-134.

10. Махнев, A.A. Об автоморфизмах сильно регулярных графов с Л = 0, ¡1 = 2/ A.A. Махнев, В.В. Носов// Мат. сб.- 2004,- Т.185, № 3.- С. 47-68.

11. Махнев, A.A. Об автоморфизмах графов сА = 1,/л = 2/ A.A. Махнев, И.М. Минакова // Дискрет, матем,- 2004,- Т.16, № 1,- С. 95-104.

12. Белоусов И.Н. О сильно регулярных графах с ¡i = 1 и их автоморфизмах / И.Н. Белоусов, A.A. Махнев // Доклады Академии Наук.- 2006.- Т. 410, № 2,- С. 151-155.

13. Махнев, A.A. О расширениях частичных геометрий, содержащих малые /i-подграфы /A.A. Махнев // Дискр. анализ и исслед. операций,- 1996-Т.З.- С.71-83.

14. Махнев, A.A. О сильной регулярности некоторых реберно регулярных графов / A.A. Махнев // Известия РАН, сер. матем,- 2004,- Т.68.- С. 159172.

15. Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486,165,36,66) / A.A. Махнев // Украинский матем. журнал.- 2002.Т. 54, № 7.- С. 941-949.

16. Махнев А.А. Об одном классе реберно регулярных графов / А.А. Мах-нев, И.М. Минакова // Известия Гомельского госуниверситета, Вопросы алгебры,- 2000,- Т. 3 (16).- С. 145-154.

17. Журтов А.Х. Об автоморфизмах 4-изорегулярных графов / А.Х. Жур-тов, А.А. Махнев, М.С. Нирова //8 Международная школа-конференция по теории групп. Нальчик 2010. Тез. докл.- С. 94-102.

18. Кондратьев, А.С. Распознавание знакопеременных групп простой степени / А.С. Кондратьев, В.Д. Мазуров // Сиб. матем. ж,- 2000.- Т. 41, № 2.- С.359-369.

19. Падучих Д.В. Новая оценка для число вершин реберно регулярных графов / А.А. Махнев, Д.В. Падучих // Сибирский матем. журнал,- 2007.Т. 48, № 4,- С. 817-832.

20. Brouwer, А.Е. Distance-regular graphs/ А.Е. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag.- 1989.- 495 c.

21. Brouwer, A.E. Block designs/ A.E. Brouwer, H.A. Willbrink// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995.- P.349-383.

22. 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.

23. Buekenhout, F. Foundations of incidence geometry / F. Buekenhout// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout. Elsever Science. Amsterdam.- 1995 - P.63-107.

24. Buekenhout, F. Finite diagram geometries extending buildings/ F. Buekenhout, P. Pasini// Handbook of incidence geometry: buildings and foundations/ F. Buekenhout.— Elsever Science. Amsterdam.- 1995.- P. 11431255.

25. Cameron, P. Permutation Groups/ P. Cameron.- London Math. Soc. Student Texts 45.: Cambridge Univ. Press, 1999.

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

27. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang// Sci. Record.- 1949,- Vol.3.- P.604-613.

28. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28,n\ = 12,n0 = 15 andp2 = 4/ L.C. Chang// Sci. Record-1950,- Vol.4.- P.12-18.

29. Gardiner A. Homogeneous graphs / A.Gardiner //J. Comb. Theory.- 1976.-V. 20.- P. 94-102.

30. Guralnik R.M. Subgroups of prime power index in a simple group / R.M. Guralnik // J. Algebra.- 1983.- V. 81, № 2,- P. 304-311.

31. Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman// Ann. Math. Stat.- I960.- Vol.31.- P.492-497.

32. 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.

33. Hoffman, A.J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman// Ann. Math. Stat.- 1964,- Vol.35.- P.883-885.

34. Prager, C.E. Low rank representations and graphs for sporadic groups/ C.E. Prager, L.H. Soicher.- Lecture series 8,- Cambridge: University press.-1997.

35. 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.

36. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande// Ann. Math. Stat.- 1959,- Vol.30.- P.781-798.

37. Macay M. Search for properties of the missing Moore graph / M. Macay, J. Siran // Linear Algebra and its Appl.- 2009.- V. 432.- P. 2381-2398.

38. Tits, J. Buildings of Spherical Type and finite BN-pairs/ J. Tits// Springer Lecture Notes in Mathematics.- Vol.386.Работы автора по теме диссертации

39. Токбаева А.А. О числе вершин в реберно регулярных графах с к — 36i — 2 / А.А. Махнев, А.А. Токбаева // Труды 40-й Вссросс. молод, конф. Изд-во ИММ УрО РАН: Екатеринбург.- 2009.- С. 32-35.

40. Токбаева A.A. О числе вершин в реберно регулярных графах с к = 3bi — 2 / A.A. Махнев, A.A. Токбаева // Алгебра и ее приложения. Труды межд. конф., посвященной 80-летию со дня рождения А.И. Кострикина. КБГУ: Нальчик,- 2009. С. 87-91.

41. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / A.A. Махнев, A.A. Токбаева // Тезисы 41-й Всеросс. молод, конф. Изд-во МММ УрО РАН: Екатеринбург.- 2010.- С. 42-46.

42. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Теория групп и ее приложения. Труды межд. конф., посвященной 75-летию со дня рождения В.А. Белоногова. КБГУ: Нальчик,- 2009,- С. 89-93.

43. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (76,35,18,14) / М.М. Исакова, A.A. Махнев // Труды ИММ УрО РАН,- 2010.- Т. 16, № 3.- С. 186-195.

44. Токбаева A.A. Об автоморфизмах сильно регулярного графа с параметрами (243,66,9,21) / A.A. Махнев, A.A. Токбаева // Владикавказский матем. журнал,- 2010.- Т. 12, № 4,- С.

45. Токбаева A.A. Сильно регулярный граф с параметрами (243,66,9,21) не является реберно симметричным / A.A. Токбаева // Сибирские электронные матем. известия,- 2010,- Т. 7.- С. 155-161.