Алгебраические и локальные характеризации некоторых классов графов Деза

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

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

Графы Деза с параметрами графа Ь(п)

Графы Деза с параметрами графа Т{п)

Графы Деза с параметрами графов Т(п) и Ь(п)

Точные графы Деза на 14, 15 и 16 вершинах

Список литературы

Введение

§ 0.1. История вопроса

Одним из важнейших объектов исследования алгебраической теории графов являются сильно регулярные графы, которые были введены в 1963 г. Боузом в связи с исследованиями схем отношений с двумя классами [3] и, позднее, Хигманом при исследовании групп подстановок ранга 3 [13].
В дальнейшем сильно регулярные графы рассматривались как самостоятельный объект исследований. Наиболее важный вопрос теории — "существует ли сильно регулярный граф с заданным набором параметров?"Другими словами, исследуются условия существования таких графов. Если ответ на предыдущий вопрос положительный, то возникает вопрос о количестве неизоморфных сильно регулярных графов с одинаковыми параметрами, т.е. вопрос характеризации графа по параметрам (возможно, с привлечением некоторых дополнительных ограничений). К решению этих задач привлекаются алгебраические (методы линейной алгебры, в частности, изучение спектров матриц смежности) и комбинаторные методы. Так, в работах 1959-60 годов JT.C. Чанг [5] и А.Дж. Хоффман [16,17] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п (за исключением п — 8). Реберный граф полного двудольного графа с долями порядка п (т.е. решетчатый граф L(n)) является сильно регулярным графом с параметрами (гг2,2(ге — 1), п — 2,4). С.С. Шрикханде в [21] показал, что при п ф 4 граф Ь{п) определяется этими параметрами. Это первые результаты по характеризации сильно регулярных графов, которые стали классическими. Также изучаются различные способы представления (построения) графов из блок-схем, конечных геометрий, действий некоторых конечных групп на множествах.

Параллельно с изучением собственно сильно регулярных графов идет изучение графов, получаемых из сильно регулярных ослаблением некоторых условий: дистанционно регулярные (и дистанционно транзитивные) графы, вполне регулярные графы, реберио и кореберно регулярные графы.
В 1994 г. в работе [9] М. Деза, изучая некоторые геометрические объекты, рассмотрел класс регулярных графов, в которых число общих соседей любой пары различных вершин принимает одно из двух возможных значений, но не определяется смежностью этих вершин. Такие графы естественно рассматривать как обобщения сильно регулярных графов.
Базовые свойства таких графов изучены в работе [10] в 1998 г., кроме того, в этой же работе предложены некоторые конструкции графов Деза: из сильно регулярных графов с помощью инволюции (автоморфизма порядка 2), переставляющей только несмежные вершины, с помощью разностных множеств в группе, склеиванием классов в схемах отношений. Также перечислены все неизоморфные графы Деза не более чем па 13 вершинах.
Так же в работах Ермаковой и Кабанова 2006-2009 гг. [23] - [27] изучались графы Деза без 3-коклик. В работе Гуо, Ванга и Ли 2010 г. [22] построение графов Деза из симплектических пространств.
В настоящей диссертационной работе решается задача характеризации некоторых классов графов Деза по параметрам и строению окрестностей. Кроме того, пополняется список известных примеров графов Деза.
§ 0.2. Предварительные сведения
Все рассматриваемые здесь графы конечны, неориентированы, без петель и кратных ребер. Граф называется регулярным степени к, если каждая его вершина смежна с одним и тем же числом к вершин. Под подграфом графа (7 будем понимать порожденный подграф, то есть вершины подграфа смежны тогда и только тогда, когда они смежны в графе (7. Если и — вершина

3. Графы Деза с параметрами графов Т(п) и Ь(п)
§ 3.1. Предварительные результаты
Очевидно, что дополнительный граф к сильно регулярному графу с параметрами
(у, к, А, ц), так же будет сильно регулярным с параметрами (у,у — к — 1, V — 2к+/і — 2, г — 2к + Х). То есть, граф Ь{п) сильно регулярный с параметрами (гг2, (гг — I)2, (п — 1) (п — 2), (гг — 2)2), такие же параметры имеет граф дополнительный к графу Шрикханда, и граф Т(п) сильно регулярный с параметрами ((2), ("г3)’ ("г4))’ такие же параметры имеют графы
Щ8), Т"(8), Т'"{8).
Будем считать вершины в этих графах занумерованными так же как и в графах Ь{п) и Т(п).
§ 3.2. Автоморфизмы графов с параметрами графов Ь[п) и Т(п)
К таким графам относятся сами графы Ь(п) и дополнение к графу Шрикханда.
Лемма 3.2.1. Не существует автоморфтзмов дополнения к графу Шрикханда, удовлетворяющих условию теоремы 0.3.9.
Доказателььство. Автоморфизм дополнения к графу Шрикханда, переставляющий несмежные вершины в самом графе Шрикханда переставляет смежные вершины. Пусть смежные вершины а и Ъ переходят друг в друга по действием искомого автоморфизма. Так как окрестностью вершины в графе Шрикханда является шестиугольник, то общие соседи вершин а и Ь (пара несмежных вершин) остаются неподвижны. Рассморим окрестность одной из них. Вершины а и Ъ переходят друг в друга, следовательно, смежные с ними вершины переходят друг в друга, но они несмежны. Значит такого автомор-