Автоморфизмы и локальная структура графов

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

Оглавление
1. Влияние 2-окрестностей на строение графа
2. 2-Локально графы Зейделя
2.1. Редукция к графам диаметра
2.2. 2-локально решетчатые графы
2.3. Треугольные графы и графы Чанга
2.4. Графы Петерсена, Шлефли и Шрикханде
2.5. Граф Клебша
3. Локально Шрикханде графы и их автоморфизмы
3.1. Вспомогательные результаты
3.2. Несвязные д-подграфы
3.3. Связные д-подграфы
4. Классификация локально 0({3,9) графов
4.1. Предварительные результаты
4.2. Гиперовалы в С<3(3,9)
4.3. Локально С(5(3,9) графы
5. Автоморфизмы графов Мура

Введение
Основные определения. Мы рассматриваем неориентированные графы без петель и кратных ребер. Если о, Ъ — вершины графа Г, то через д(а, Ь) обозначим расстояние между а и Ь, а через Г,-(а) — подграф,,индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии г от вершины а. Подграф Гі(о) будем называть окрестностью вершины а и обозначать через [а], если понятно о каком графе идет речь. Через а1 обозначим подграф, индуцированный {а} и [а], а через [а]' — подграф Г — о1.
Валентностью вершины называется число вершин в ее окрестности. Граф Г называется регулярным валентности к если валентность любой вершины а из Г равна к. Граф Г назовем реберно регулярным (кореберно регулярным) с параметрами (у,к,) (с параметрами (у,к,р)), если он содержит V вершин, регулярен валентности к, и каждое его ребро аЬ лежит в Л треугольниках (любые две несмежные вершины а,Ь имеют р общих соседей). Подграф, индуцированный на [а] П [Ь], назовем (Л-) /л-подграфом, если вершины а,Ь (смежны) находятся на расстоянии 2.
Граф Г — вполне регулярный граф с параметрами (г, к, Л, р), если он реберно регулярен с соответствующими параметрами и [а] П [Ь] содержит р вершин для любых двух вершин а,Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Назовем дистанционно регулярным графом с массивом пересечений
{Ьо, Ьи
регулярный связный граф диаметра (1 такой, что для любой пары вершин (ж, у), находящихся на расстоянии у, верны равенства
|Гу-і(у) ҐіГі(х)| = с,-( 1 < і < еО,-|Г,-+1(у) ПГх(ж)| = ф(0 <з<й-1).

Легко понять, что для любого дистанционно регулярного графа верны равенства Ьо = к и с = 1.
Дистанционно регулярный граф диаметра d называется антпипо-дальним, если уравнение d(x,y) — d задает отношение эквивалентности на множестве вершин графа. Графом Тэйлора называется ди- ' станционно регулярный граф с массивом пересечений {к, р,1]1, р,к}. Легко понять, чтограф Тэйлора антиподален с классами эквивалентности порядка 2.
Для подграфа Д графа Г через К,(Д) обозначим множество вершин из Г — Д, смежных с г вершинами из Д, х,-(Д) = |1Гг-(Д)|.
Постановка задачи. Результаты, полученные в данной диссертации, имеют своей целью исследование графов с ограничением на локальную структуру. Постановка задачи описания графов с ограничением на локальную структуру происходит от аналогичной задачи для конечных геометрий. Мы приведем в связи с этим определение геометрии ранга п, принадлежащее Титсу [27].
Определение. Пусть I — конечное множество. Геометрия ранга п над I — это тройка G — (X,*,t), где X — множество объектов; t — типовая функция, отображающая X в I (сопоставляющая объекту из X его тип), такая что |i(X)| = п; и * — рефлексивное симметричное отношение инцидентности на X, причем объекты одного типа а, Ь инцидентны, только если а = Ъ.
Флагом геометрии G называется набор попарно инцидентных объектов. Типом флага F называется множество t{F); рангом флага F — число ]t(T)|-
Вычет Gf флага F геометрии G — это множество объектов Хр — {и € X — F | и * / для всех / € F}, рассмотренное как геометрия над I — t{F). Каждый вычет геометрии сам является геометрией.
Особую роль играют геометрии ранга 2 — каждой геометрии G можно сопоставить семейство геометрий Gij ранга 2 (г, j G I, i ф j), являющихся вычетами флагов типа Обратно, можно поста-
вить задачу описания класса геометрий G при заданном семействе Gij. Исторически подобные исследования появились в работах Титса [26], [27] с целью описания групп Шевалле как групп автоморфизмов геометрий определенного класса (билдингов). В общем случае эта задача была впоследствии сформулирована Бюкенхаутом [14].

Рис. 3.1. Локально Шрикханде граф на 80 вершинах

• : >
Рис. 3.2.
ми V = т2, к = 2т - 2, А = т — 2, ц = 2. Среди графов, имеющих параметры решетчатых графов, имеется один исключительный граф — это локально шестиугольный сильно регулярный граф с параметрами (16,6, 2, 2). Имеется ряд результатов по локально решетчатым графам (см. [6, с. 495]), однако локально Шрикханде графы пока не рассматривались
Теорема 3.1. Пусть Г — связный локально Шрикханде граф. Тогда Г является единственным антиподалъным графом на 80 вершинах, диаметра 4, имеющим диаграмму, изображенную на рис. 3, относительно любой вершины, или частным этого графа на 40 вершинах.