Симметрические расширения графов

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

Содержание
Введение
1 Существование локально конечных графов с бесконечным числом симметрических расширений посредством конечного графа
1.1 Достаточное условие существования у локально конечного графа бесконечного числа накрывающих симметрических расширений посредством одного и того же конечного графа
1.2 Примеры графов, имеющих бесконечное число накрывающих симметрических расширений посредством одного и того
же конечного графа
2 Симметрические д-расшпрения решеток Аа
2.1 Условие периодичности для симметрических д-расширений решеток
2.2 АмЛДсимметрические д-расширения решеток Лй и условие периодичности для них
2.3 Критерий конечности множества симметрических д-расширений решетки Л2 и некоторые его применения
3 Аьіо(Л-симметрические 2-расширения решеток А'1
3.1 АиЛДсимметрические 2-расширения решеток Ай для с[
и сі = 2
3.2 Аміо(Л<і)-симметрические 2-расширения решеток Аа для произвольного (1
4 АгфЛ-симметрические д-расширения решеток Аа для не-

больших (1 и
4.1 А«£о(Л)-симметрические 3-расширения решеток для
с! = 1 и с?
4.2 А л £о ( А1) -сим метри ческие 4-расширения решетки Л1 и конечность числа (Л2)-симметрических 4-расширений решетки

4.3 Аио(Л2)-симметрические 4-расширения решетки Л2
Список литературы

Введение
Диссертационная работа посвящена изучению симметрических расширений графов. Пусть Г и Д — графы (под графом здесь и далее понимается неориентированный граф без петель и без кратных ребер). В соответствии с [1] связный граф Г называется симметрическим расширением графа Г посредством графа Д, если существуют такая вершинно-транзитивная группа Є автоморфизмов графа Г и такая система импримитивности а группы Є на множестве У (Г) вершин графа Г, что фактор-граф Г/сг изоморфен графу Г и блоки системы а порождают в Г подграфы, изоморфные графу Д. Ясно, что симметрическое расширение графа Г посредством графа Д существует лишь для Г и Д, допускающих вершинно-транзитивные группы автоморфизмов, причем граф Г должен быть связным. Если в приведенном выше определении симметрического расширения графа Г посредством графа Д отказаться от условия связности графа Г, то получим определение обобщенного симметрического расширения графа Г посредством графа Д. Если при этом р — изоморфизм графа Г/сг на граф Г, то будем говорить, что Г — обобщенное симметрическое расширение графа Г посредством графа Д, реализуемое СГ а, р.
Симметрические расширения графов представляют интерес в силу целого ряда причин (см. ниже). При этом часто бывает важно, чтобы (в приводимом выше определении симметрического расширения Г посредством Д) при изоморфизме Г/сг на Г индуцируемая Є группа СУ автоморфизмов графа Г/сг переходила в некоторую заданную группу автоморфизмов (? графа Г. В связи с этим вводится следующее определение (см. [1]). Для графов Г, Д и вершинно-транзитивной группы автоморфизмов С графа Г связный граф Г называется С-симметрическим расширением графа Г посредством графа Д, если граф Г является симметрическим расширением графа Г посред-

Глава
АиЬ о(Л) -симметрические 2-расширения решеток
Как было отмечено во введении, значительный интерес представляет задача нахождения всех А«£о(Лй)-симметрических -расширений решетки Ай. Настоящая глава посвящена описанию Аго(Лй)-симметрических 2-расширений решетки Аа для любого целого положительного числа (I (см. теорему 3.2.1). Это позволяет, в частности, указать для любого целого положительного числа (1 число АЫо(Аа)-симметрических 2-расширений решетки (см.
следствие 3.2.1).
3.1 Ло(Лб?)-симметрические 2-расширения решеток для с1=1 и (1
В настоящем параграфе получен список всех обобщенных АгДЛ-симмет-рических 2-расширений решетки Аа для с1 = 1 и с1 = 2.
Напомним (см. введение), что для произвольных целых положительных чисел с1 и q, если Г — Амо(Лсг)-симметрическое д-расширение решетки Аа, реализуемое (?, сг, у?, то ст однозначно определяется графом Г и называется соответствующей Г (как А«£о(Лй)-симметрическому д-расширению решетки Аа) системой блоков.
Легко видеть, что обобщенные А-ио(А1)-симметрические 2-расширения решетки Л1 исчерпываются следующими графами Г*’2, 1 < п < 4 (верхние индексы 1, 2 означают, что Г*’2 являются обобщенными Агло (Л-симметрическими 2-расширениями 1-мерной решетки Л1).