Комбинаторно-алгебраические методы исследования дистанционно-регулярных графов

• Автор: Иванов, Александр Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 147 c. : ил

С ОДЕРЖАНИЕ

Глава I. Общие сведения о дистанционно-регулярных графах и их группах автоморфизмов

§ 1.1. Основные определения

§ 1.2. Дистанционно-регулярные графы в комбинаторике . 22 § 1.3. Дистанционно-транзитивные графы в теории конечных групп

§ 1.4. Импримитивные графы

§ Г.5. Условия реализуемости массивов пересечений

§ 1.6. Реберно-транзитивные графы

Глава 2. Комбинаторные методы исследования

§ 2.Г. Характеристические матрицы и их свойства

§ 2.2. Ограничение диаметра

§ 2.3. Некоторые следствия из ^ -теоремы

§ 2.4. Алгоритм перечисления массивов пересечений.
дистанционно-регулярных графов
§ 2.5. Приемы доказательства несуществования дистанционно-регулярных графов с заданным массивом пересечений
Глава 3. Алгебраические методы исследования
§ З.Г. Существование и единственность дистанционнотранзитивных графов
§ 3.2. Связь з-транзитивности с дистанционной транзитивностью
§ 3.3. Вычисление длин орбит подгруппы в транзитивной
группе подстановок
§ 3.4. Транзитивное расширение групп подстановок

Глава 4. Результаты исследования некоторых конкретных классов графов
§ 4.1. Автоморфные графы степени к =£13 и диаметра а «5
§ 4.2. Дистанционно-транзитивные графы степени 5, 6 и 7
§ 4.3. Примитивные представления неабелевых простых
групп порядка меньше ГО6
§ 4.4, Автоморфные графы, допускающие sn в качестве
группы автоморфизмов
Заключение
Литература
Приложение I
Приложение

Многие задачи прикладной математики допускают естественную формулировку в терминах отношений над элементами соответствующих множеств. Это обуславливает широкое применение методов и результатов теории графов как в прикладных дисциплинах, так и в других разделах математики. При этом особую роль играют графы, обладающие богатой симметрией, то есть большой группой автоморфизмов.
Среди таких графов выделяется класс так называемых дистанционнотранзитивных графов (д.т.г.) , груша автоморфизмов которых действует транзитивно на упорядоченных парах равноудаленных вершин. Являясь весьма нетривиальным, класс д.т.г. охватывает значительную часть графов, интересных как с прикладной, так и с теоретической точек зрения. Отметим лишь, что широко применяемые в теории алгебраических кодов схемы отношений Хэмминга и Джонсона представляют собой д.т.г.
Само определение д.т.г. устанавливает связь метрических (ком-бинаторных)свойств графа со свойствами его группы автоморфизмов.
Это определяет два основных подхода к исследованию д.т.г. Первый основан на использовании комбинаторных методов, второй является сугубо алгебраическим и опирается на теорию конечных груш.
При реализации первого подхода на графы обычно накладывается более слабое условие дистанционной регулярности, являющееся комбинаторной аппроксимацией свойства дистанционной транзитивности.
Граф называется дистанционно-регулярным (д.р.г.) , если для любого з и любых вершин х, и , находящихся на расстоянии э , число таких вершин V , которые находятся на расстоянии г от вершины х и на расстоянии t от вершины п , является функцией лишь б,г и t (не зависит от конкретного выбора вершин х и и ); здесь в,г и t - неотрицательные целые числа, не превосходящие диаметра графа.

если а3+1 = сз+1 и з^а-2 , то аз+2^ ад+1 ;
■ (іі) если в& 2 и а3-1 Ф О то аа_1> Ъд-1 . > при этом,
если ад-1 = Ъд-1 и з^З , ТО ад_2 ^ а^ ;
(ііі) если в «й-2 и ад+2 = О , но ад+1 ф О , то
ав+1>св+1 + Ъз+1*
Доказательство. Рассмотрим случай (і) . Пусть и,х - произвольные вершины на расстоянии э+1 в графе Г. Из условия ад = О и леммы 2.1.2 следует, что блок Е12 характеристичес-кой матрицы Ед+1(и,х) состоит целиком из единиц. Так как то же самое справедливо и для матрицы Ед+1(х,и) , с учетом леммы 2.І.І
заключаем, что блок е21 матрицы Ез+1(х,и) состоит целиком из нулей. Поэтому строка матрицы Ез+1(и,х) , пересекающаяся с блоком е21 , содержит минус единицы лишь в пересечении с блоком
е22 , тем самым ад+1 ^ сд+1 . Пусть теперь ад+1 = сд+1 , тогда блок Е22 состоит целиком из минус единиц. Если цри этом Ъ3+1 ф О , Т.е. 0+1<<1 , ТО блок Е23 состоит из одних единиц. Но отсюда, с учетом леммы 2.1.2, заключаем, что е^2 - нулевой блок. Строка матрицы Ез+1(ц,х) , пересекающаяся с блоком
Е32 , содержит ад+2 нулевых элемента, но ад+1 из них находятся в блоке Е32 , следовательно ад+2^ад+1 и случай (і)
полностью доказан. Случай (іі) доказывается совершенно аналогично рассмотрением пары вершин и,х на расстоянии э-1 и матрицы Еа_і(и*х)
В случае (ііі) матрица Ед+1(и,х) имеет вид
Е11 1
Ед+і(и»Х> = О Е22 О
I-1 -1 Езз
откуда непосредственно следует неравенство ад+1^ъд+1 + са+1 - • Заметим, что частный случай пункта (1) леммы 2.1.3 при з=1 рассмотрен в [48] на стр. 120.