О некоторых классах вершинно-транзитивных графов

• Автор: Горяинов, Сергей Викторович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Екатеринбург
• Количество страниц: 118 с. : ил.

Содержание
Введение

1 Определения, обозначения и предварительные результаты

1.1 Сильно регулярные и дистанционно регулярные графы

1.2 Схемы отношений

1.3 Графы Деза

2 Об изоморфизме между дистанционно-регулярными графами

2.1 Предварительные определения и результаты

2.2 Графы Мэтона М{2, д) и графы Мухаметьянова Тв и О

2.3 Г^~М(2,д)

2.4 Г^~М{2,д)

3 О вершинной связности одного класса графов Деза
3.1 Вспомогательные результаты
3.2 Вершинная связность графов Деза из класса V
3.2.1 Сведение задачи к трем случаям
3.2.2 Графы Деза, полученные из графов п х гг-решетки
3.2.3 Графы Деза, полученные из Т(п)
3.2.4 Графы Деза, полученные из спорадических графов Зей-деля
3.2.5 Доказательство теоремы
3.3 Заключение
4 Точные графы Деза, имеющие 14, 15 и 16 вершин
4.1 Отбор допустимых наборов параметров
4.2 Перебор матриц смежности

4.3 Отбор попарно неизоморфных графов
4.4 Поиск конструкций для найденных графов Деза
4.5 Заключение
5 Кэли-Деза графы, имеющие менее 60 вершин
5.1 Вспомогательные результаты
5.2 Описание алгоритма
5.2.1 Получение вспомогательной информации из системы GAP
5.2.2 Нумерация подмножеств элементов групп
5.2.3 Построение дерева перебора
5.3 Результаты
Список литературы
Приложения
Приложение А: Основные процедуры
Приложение Б: Результаты перебора Кэли-Деза графов
Для фиксированной группы
Для фиксированного графа

Введение
Комбинаторика — раздел математики, изучающий различные задачи построения и перечисления дискретных объектов и отношения на них. Задача построения заключается в построении и изучении необходимых и достаточных условий существования множеств с заданными свойствами.
Одними из первых в этой области были исследования, связанные с вероятностными аспектами азартных игр (кости, карты).
В дальнейшем появились новые постановки комбинаторных задач, которые уже представляли самостоятельный интерес. С другой стороны, благодаря развитию других математических дисциплин, в частности анализа и алгебры, стали доступны иные средства решения комбинаторных задач. Например, Стирлингом была получена асимптотика факториальной функции.
На стыке комбинаторики с анализом возникла самостоятельная аналитическая комбинаторика, использующая, в частности, аппарат теории функций комплексного переменного и теории производящих функций. На стыке с линейной алгеброй и теорией групп появилась так называя алгебраическая комбинаторика, включающая в себя, в большей степени, теорию дизайнов (блок-схем), теорию кодирования и теорию графов. Так, язык линейной алгебры оказался удобным для описания самих дискретных объектов, тогда как теория групп (и теория конечных групп, в частности) естественным образом описывает определенного рода симметрии этих объектов. Классическим примером ’’богатых” с точки зрения количества симметрий объектов являются Платоновы тела. Отметим свойства эквивалентности как вершин, так и ребер этих фигур. На языке теории групп эти свойства носят название вершинной и реберной транзитивности графа, отвечающего Платонову телу, вершинами которого являются вершины Платонова тела, а ребра этого графа соотвеству-ют ребрам Платонова тела. Свойства вершинной и реберной транзитивности графа определяются через транзитивное действие группы автоморфизмов на

2 Об изоморфизме между дистанционно-регулярными графами
2.1 Предварительные определения и результаты
В работе [48] были предложены две новых конструкции антиподальных дистанционно регулярных графов, связанных с группой PSL,2(q), при этом автор оставил открытым вопрос об изоморфизме полученных графов уже известным с тем же массивом пересечений. В данной главе мы покажем, что дистанционно-регулярные графы, построенные в [48], изоморфны графам Мэтона при подходящих значениях параметров.
2.2 Графы Мэтона М (2, q) и графы Мухаметьянова Г д и Г,/
Напомним, что группа PSL2(q), q = рп, содержит ровно два класса сопряженных элементов порядка р (см. Лемма 2.2.1 ниже). Пусть Гд — граф, множеством вершин которого является множество В — gG U {g~l)G, где gG — класс сопряженных элементов порядка р в группе G — PSL2(pn), а множеством ребер является {{х, у)ху~1 Є В}, где р — нечетное простое число и q — рп > 5. Обозначим через Г д граф, полученный из графа Г в удалением ребер, соединяющих коммутирующие элементы из В.
Теорема 2.1 (Теорема 1, Теорема 2, [48]). Если q = 1 (mod 4), то граф Гд является дистанционно-регулярным с массивом пересечения {q, q—3,1; 1,2, q}.
Пусть Tj — граф, множеством вершин которого является множество всех элементов порядкар группы G, а множество ребер — множество {{гг, у}ху~1 Є J}, где J — класс сопряженных инволюций группы G.
Теорема 2.2 (Следствие 1, [48]). Если q = 1,3 (mod 8), то граф Tj не связен, и компонентами связности являются два изоморфных друг другу дистанционно-регулярных графа Г^, Г" с массивом пересечений {q, q — 3,1; 1,2 ,q}.