Оглавление
1. Влияние 2-окрестностей на строение графа 13
2. 2-Локально графы Зейделя 18
2.1. Редукция к графам диаметра 2.................................... 20
2.2. 2-локально решетчатые графы...................................... 22
2.3. Треугольные графы и графы Чанга.................................. 25
2.4. Графы Петерсена, Шлефли и Шрикханде...............................27
2.5. Граф Клебша...................................................... 30
3. Локально Шрикханде графы и их автоморфизмы 35
3.1. Вспомогательные результаты ..................................... 37
3.2. Несвязные /^-подграфы........................................... 40
3.3. Связные /л-подграфы.............................................. 46
4. Классификация локально Сф(3,9) графов 53
4.1. Предварительные результаты....................................... 55
4.2. Гиперовалы в 0(^(3,9)............................................ 56
4.3. Локально СС}(3,9) графы.......................................... 69
5. Автоморфизмы графов Мура 71
2
Введение
Основные определения. Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ъ — вершины графа Г, то через <і(а, 6)- обозначим расстояние между а и 6, а через Г,(а) — подграф,, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Гі(а) будем называть окрестностью вершини а и обозначать через [а], если понятно о каком графе идет речь. Через а1 обозначим подграф,' индуцированный {а} и [а], а через [а]' — подграф Г - .
Валентностью вершины называется число вершин в ее окрестности. Граф Г называется регулярным валентности к\ если валентность любой вершины а из Г равна к. Граф Г назовем реберно регулярным (кореберно регулярным) с параметрами (г?, А:, Л) (с параметрами (и,&,аО), если он содержит V вершин, регулярен валентности к, и каждое его ребро аЬ лежит в Л треугольниках (любые две несмежные вершины а, Ь имеют р общих соседей). Подграф, индуцированный па [а] П [Ъ], назовем (Л-) д-подграфом, если вершины а, Ь (смежны) находятся на расстоянии 2.
Граф Г — вполне регулярный граф с параметрами (г;, к. А, р), если он реберпо регулярен с соответствующими параметрами и [а] П [6] содержит р вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Назовем дистанционно регулярным графом с массивом пересечений
{60, сі, с2,..., с^}
регулярный связный граф диаметра сі такой, что для любой пары вершин (х,у), находящихся на расстоянии верны равенства
|Г,-_і(у)ПГі(х)| = с,( 1 < ) < <і), |Г;+і(у) П Гі(х)| = 6,(0 < ) < д- 1).
3
Легко понять, что для любого дистанционно регулярного графа верны равенства Ьо = к и С\ = 1.
Дистанционно регулярный граф диаметра д называется аптпипо-дальпым, если уравнение с1(х,у) = (I задает отношение эквивалентности на множестве вершин графа. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {/с, /д 1; 1, ц, к}. Легко понять, что граф Тэйлора антиподален с классами эквивалентности порядка 2.
Для подграфа Д графа Г через К {(А) обозначим множество вершин из Г — Д, смежных с г вершинами из Д, х,(Д) = |К,(Д)|.
Постановка задачи. Результаты, полученные в данной диссертации, имеют своей целью исследование графов с ограничением на локальную структуру. Постановка задачи описания графов с ограничением на локальную структуру происходит от аналогичной задачи для конечных геометрий. Мы приведем в связи с этим определение геометрии ранга п, принадлежащее Титсу [27].
Определение. Пусть I — конечное множество. Геометрия ранга п над I — это т.ройка б = (X, *,#), где X — множество объектов; £ — типовая функция, отображающая X в I (сопоставляющая объекту из X его тип), такая что |£(Х)| = п; и * — рефлексивное симметричное отношение инцидентности на X, причем объекты одного типа а, Ь инцидентны, только если а = Ь.
Флагом геометрии б называется набор попарно инцидентных объектов. Типом флага Г называется множество t(F); рангом флага Е — число |^(-Р)|.
Вычет флага Е геометрии б — это множество объектов Хр — {д 6 X - Е | и* / для всех / € Е}, рассмотренное как геометр'ия над I — £(.Р). Каждый вычет геометрии сам является геометрией.
Особую роль играют геометрии ранга 2 — каждой геометрии б можно сопоставить семейство геометрий бц ранга 2 € /, г ф 7),
являющихся вычетами флагов типа 1—{г^}. Обратно, можно поставить задачу описания класса геометрий б при заданном семействе бц. Исторически подобные исследования появились в работах Титса [26], [27] с целью описания групп Шевалле как групп автоморфизмов геометрий определенного класса (билдингов). В общем случае эта задача была впоследствии сформулирована Бюкенхаутом [14].
4
Чтобы установить связь между геометриями и графами в этом контексте, следует рассмотреть геометрии ранга 2 более подробно. Говоря о геометриях ранга 2 не вполне удобно пользоваться общим определением геометрии, поэтому обычно формулируется следующий упрощенный его вариант.
Определение. Геометрия 0 ранга 2 — это пара (Р,В), где Р — некоторое множество точек, а В — система его подмножеств, называемых блоками. Множество точек, колинеарных точке х (т. е. лежащих с ней в одном блоке), будем обозначать через х1.
Вычетом геометрии 0 в точке х’ называется геометрия 9Х = (РХ,В£), где Рх = х1 - {х}, Вх = {Ь - {х} | Ь € В,Ь Э х}.
Отметим, что в этом случае имеется точно два типа объектов — “точка” и “блок”, а отношение * — это симметризованное включение. ■ •
Определение. Расширением семейства 5 геометрий ранга 2 называется геометрия С>, такая что вычет (}х принадлежит семейству в для любой точки х Е Р-
Обычно задачу расширения геометрий ранга 2 решают в случае, когда 5 состоит из “хороших” геометрий. Мы введем ряд ограничений, которые понадобятся нам для дальнейшего изложения.
Пусть х£Р,Ь£Вих£Ь (пара (х,Ь) называется антифлагом). Число точек из I/, колинеарных с х, обозначим через а(х,Ь). Геометрия 0 называется (р-однородной, если а(х,Ь) = 0 или р для любого антифлага (т,Ь); 5 называется сильно р-однородной, если а(х, Ь) = р для любого антифлага (х, Ь).
Датее мы будем рассматривать только такие геометрии, в которых любые два блока пересекаются не более чем по одной точке, при этом блоки будем называть прямыми. В этом случае геометрия называется частичным линейным пространством. Геометрия называется а-частичной геометрией порядка (5, £), если каждая прямая содержит 5 + 1 точку, каждая точка лежит на £ +1 прямой и геометрия является сильно а-однородной (обозначение р£а(М))- Двойственная геометрия к рСа($Л) является частичной геометрией р£а(*, 5).
Геометрия рСп(5, £) называется обобщенным четырехугольником порядка ($,£) и обозначается
Любой геометрии £ ранга 2 мы сопоставим её точечный граф
5
Г(С/), вершинами которого ЯВЛЯЮТСЯ ТОЧКИ ИЗ С/, и две точки х,у смежны тогда и только тогда, когда х,у лежат в общем блоке и хфу.
Нетрудно заметить, что полученное соответствие между геометриями ранга 2 и их точечными графами не взаимооднозначно. Достаточно заметить, что точечный граф любой проективной плоскости — клика. Примером противоположной ситуации может служить СС?. Если 0 = 2), то геометрия О однозначно восстанавливает-
ся по своему точечному графу. Не смотря на это, задача расширения естесственным образом переносится с геометрий ранга 2 на графы.
Сформулируем задачу существования расширения на языке графов следующим образом.
Задача о расширениях на языке графов. Пусть задано се-мейство графов Т. Требуется определить существует ли граф Г, окрестность каждой вершины которого принадлежит Т. Гро.ф Г, удовлетворяющий данному условию, называется локально ^-графом
Задача описания локально ^-графов является классической и решена для различных классов Т (см. например [6, с. 495]).
Краткое содержание. В работе описан ряд классов графов, определяемых локальной структурой. Кроме того получены результаты о группах автоморфизмов возникающих графов.
Диссертация состоит из введения, пяти глав и списка литературы (29 наименований). Во введении обсуждается история вопроса, даются основные определения и кратко формулируются результаты работы.
В главе 1 рассматривается задача, двойственная сформулированной выше. Введем в рассмотрение следующее понятие, которое, оказывается, двойственно понятию локально графа. При этом мы будем рассматривать только случай Т — {А} для некоторого графа Д. Назовем граф Г 2-локально А-графом, если для любой вершины а € Г подграф Г2(а) изоморфен графу Д. Заметим, что в случае, когда Д — регулярный граф валентности /с, то связный регулярный 2-локально Д-граф Г диаметра 2 является кореберно регулярным, и //(Г) = к(Г) - к.
Пусть сначала диаметр графа Д равен 2. Тогда справедливо сле-
6
- Київ+380960830922