Введение к работе
Актуальность темы. Одним из важнейших объектов исследования алгебраической теории графов являются сильно регулярные графы, которые были введены в 1963 г. Р. К. Боузом в связи с исследованиями схем отношений с двумя классами [3] и, позднее, Д. Г. Хигманом при исследовании групп подстановок ранга 3 [11].
В дальнейшем сильно регулярные графы рассматривались как самостоятельный объект исследований. Наиболее важный вопрос теории — "существует ли сильно регулярный граф с заданным набором параметров?" Другими словами, исследуются условия существования таких графов. Если ответ на предыдущий вопрос положительный, то возникает вопрос о количестве неизоморфных сильно регулярных графов с одинаковыми параметрами, т.е. вопрос харак-теризации графа по параметрам (возможно, с привлечением некоторых дополнительных ограничений). К решению этих задач привлекаются алгебраические (методы линейной алгебры, в частности, изучение спектров матриц смежности) и комбинаторные методы. Так, в работах 1959-60 годов Л. С. Чанг [5] и А. Дж. Хоффман [13,14] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п (за исключением п = 8). Реберный граф полного двудольного графа с долями порядка п (т.е. решетчатый граф L(n)) является сильно регулярным графом с параметрами (п2, 2(п — 1),п — 2,4). С.С. Шрикханде в [17] показал, что при п^4 граф L(n) определяется этими параметрами. Это первые результаты по характеризации сильно регулярных графов, которые стали классическими. Также изучаются различные способы представления (построения) графов из блок-схем, конечных геометрий, действий некоторых конечных групп на множествах.
Параллельно с изучением собственно сильно регулярных графов идет изучение графов, получаемых из сильно регулярных ослаблением некоторых условий: дистанционно регулярные (и дистанционно транзитивные) графы, вполне регулярные графы, реберно и коре-берно регулярные графы.
В 1994 г. в работе [7] М. Деза, изучая некоторые геометрические объекты, рассмотрел класс регулярных графов, в которых число общих соседей любой пары различных вершин принимает одно из двух возможных значений, но не определяется смежностью этих вершин. Такие графы естественно рассматривать как обобщения сильно регулярных графов.
Базовые свойства таких графов изучены в работе [8] в 1998 г., кроме того, в этой же работе предложены некоторые конструкции графов Деза: из сильно регулярных графов с помощью инволюции (автоморфизма порядка 2), переставляющей только несмежные вершины, с помощью разностных множеств в группе, склеиванием классов в схемах отношений. Также перечислены все неизоморфные графы Деза не более чем на 13 вершинах.
Так же в работах Ермаковой и Кабанова 2006-2009 гг. [19] - [23] изучались графы Деза без 3-коклик. В работе Гуо, Ванга и Ли 2010 г. [18] построение графов Деза из симплектических пространств.
В настоящей диссертационной работе решается задача характе-ризации некоторых классов графов Деза по параметрам и строению окрестностей. Кроме того, пополняется список известных примеров графов Деза.
Основные обозначения Далее мы рассматриваем конечные, неориентированые графы без петель и кратных ребер. Граф называется регулярным степени к: если каждая его вершина смежна с одним и тем же числом к вершин. Под подграфом графа G будем понимать порожденный подграф, то есть вершины подграфа смежны тогда и только тогда, когда они смежны в графе G. Если и — вершина графа G, то окрестностью а будем называть подграф индуцированный на множестве вершин смежных с а в графе G. Множество вершин графа G будем также обозначать G, если из контекста понятно о чем именно идет речь. Сильно регулярным графом с параметрами (г>, к, А, /і) называется граф на v вершинах, регулярный степени к: любая пара смежных вершин имеет точно А общих соседей, а любая пара несмежных вершин имеет точно /і общих соседей.
Пусть F — некоторое множество графов. Будем называть G локально F'-графом, если окрестность каждой его вершины изоморфна некоторому графу из множества F, причем для каждого графа Н из F существует вершина графа G, окрестность которой изоморфна Я.
Графом Деза с параметрами (n, к} 6, а), где Ь > а называется граф на п вершинах, регулярный степени /с, и любая пара вершин имеет а или Ъ общих соседей (независимо от смежности вершин). В зависимости от параметров графы Деза можно разделить на несколько классов: если число общих соседей двух вершин в графе Деза определяется их смежностью, то данный граф Деза является сильно регулярным. Если параметр а графа Деза равен 0, то граф Деза может иметь диаметр больше 2. Графы Деза диаметра 2, не являющиеся сильно регулярными, называют точными графами Деза. Графы Деза при а = 0 называются (О, Л) графами. Для этих графов известны некоторые конструкции и структурные свойства (см. Кэмерона и Дрейка [4], Хигмана [12] и Мельдера [16]). Графы Деза диаметра больше 2 эквивалентны вполне регулярным графам с Л = /і (см. Брауэр, Коэн и Неймаер [2], Параграф 1.1, 1.9, и Теорема 1.13.2).
Далее приведем некоторые известные свойства графов Деза [8].
Утверждение 1. Пусть G = (V, Е) — граф Деза с параметрами
(п, /с, 6, а), где а ф Ь, для вершины и определим
a = \{w Є V : \[w] П [и}\ = а}|, /3 = \{w Є G : \[w] П [u}\ = b}\.
Тогда а и /3 не зависят от выбора вершины и, a = bZa ~ и
о а{п—1)—к{к—1)
Р — ^-ь
Следствие 2. Для графа Деза с параметрами (п,к,Ь,а), где афЬ, выполняются следующие ограничения.
Ъ — а делит Ь(п — 1) — к (к — 1),
Если а, [5 ф 0, то а(п - 1) < к (к - 1) < Ь{п - 1),
Если а Ф 0, то п > 2к — а.
Можно определить графы Деза в терминах матриц. Пусть G — граф с матрицей смежности М. G — граф Деза с параметрами
(n, к, 6, а) тогда и только тогда, когда
М2 = аА + ЪВ + к!
для некоторых (0,1)-матриц А и В, таких что А + В + I = J (матрица из единиц). Заметим, что G — сильно регулярный граф тогда и только тогда, когда одна из матриц А, В равна М.
Наконец, заметим, что графы Деза могут быть ассоциированы с естесвенным обобщением (п, к, А)-симметричных блок схем. Действительно, матрица смежности М графа Деза может рассматриваться, как матрица инцидентности схемы, с точками соответствующими строкам М и блоками соответствующими столбцам М. Простейшей интерпретацией графов Деза является схема с п точками и п блоками, каждому блоку (точке) инцидетно точно к точек (блоков) и каждая пара различных блоков (точек) имеет а или Ъ общих точек (блоков). Это дает пример частично симметричных схем (см. Хьюгес [15] и Цигич [6]). Они также связаны с Л-конфигурациями (см. Гропп [9]).
Некоторые конструкции графов Деза
В работе [8] приводится несколько конструкций графов Деза.
Пусть Г — конечная группа и для непустого множества элементов D С Г определим D~l = {d~l : d Є D} и, кроме того, определим DD~l как мультимножество {dd'~l : d,d' Є D} (т.е. в DD~l могут быть повторяющиеся элементы). Для подмножеств А и В множества элементов Г и натуральных чисел а, Ъ и к будем писать DD~l = аА + ЬВ + к{е}, если DD~l состоит из а копий каждого элемента из А: Ъ копий каждого элемента из В и к копий единицы е группы Г.
Утверждение 3. Пусть D — подмножество элементов группы Г такое, что:
(і) |Г| =пи \D\ = к\
(п) единица е группы Г не содержится в D;
(iii) D~l = D;
(iv) 3 такие натуральные а, 6 и к, что DD 1 = аА + ЬВ + ке, где множества А, В и {е} образуют разбиение Г.
Пусть G — граф, вершинами которого являются все элементы группы Г, и вершины и и v смежны тогда и только тогда, когда v~lu Є D. Тогда G — граф Деза с параметрами (п, к, Ь, а), где Ъ > а.
Рассмотрим симметричную матрицу М': которая может быть получена из матрицы смежности М графа Деза G перестановкой строк. Тогда М2 = МТМ = М'ТМ' = М'2. Следовательно М' также представляет граф Деза имеющий те же параметры и тех же детей Деза, что и граф G. Используя эту идею, можно получать точные графы Деза из сильно регулярных графов.
Утверждение 4. Пусть G — сильно регулярный граф с параметрами (п, к, Л, /і) с к = /і, Л т^ М и с матрицей смежности М. Пусть Р — перестановочная матрица размера v х -и, тогда РМ — матрица смежности графа Деза G' с параметрами (п, к, тах{Л, /і}, тіп{А, /і}) тогда и только тогда, когда Р задает инволютивный автоморфизм графа G, переставляющий только несмежные вершины. Кроме того G' — точный граф Деза в том и только том случае, если Р ф I, А^Ои/і^О.
Также приводятся конструкции композиции и произведения графов, и конструкция склеивания классов в схемах отношений.
Цель диссертации. Целью данной работы является решение следующих задач.
Найти все инволюции треугольных, решетчатых и дополнительных к ним графов переставляющие только несмежные вершины.
Доказать, что точные графы Деза, полученные из треугольных, решетчатых и дополнительных к ним графов с помощью этих инволюций, однозначно определяются своими параметрами и строением окрестностей.
Найти и все неизоморфные точные графы Деза на 14, 15 и 16 вершинах.
Методы исследования. Основными методами исследования являются методы линейной алгебры, теории групп, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.
Найдены все автоморфизмы треугольных и решетчатых графов, графов Чанга и Шрикханда, и дополнительных графов для каждого из них, удовлетворяющие условию теоремы 0.3.9. [24]- [27], [29].
Доказано, что точные графы Деза, полученные из треугольных графов и дополнительных к ним графов, с помощью этих автоморфизмов, однозначно определяются по своим параметрам и строению окрестностей [25], [27], [29].
Доказано, что точные графы Деза, полученные из решетчатых графов с помощью симметрии относительно главной диагонали, однозначно определяются по своим параметрам и строению окрестностей [26].
Доказано, что точные графы Деза, полученные из дополнения к решетке с помощью автоморфизма, перестановляющего пару строк, однозначно определяются по своим параметрам и строению окрестностей [27].
Найдены все неизоморфные точные графы Деза на 14, 15 и 16 вершинах. Для каждого графа найдена конструкция [28], [30].
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжают изучение комбинаторно симметричных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения алгебраических структур подобного типа.
Апробация работы. Основные результаты диссертации докладывались на 40-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики», 41-й Всероссийской молодежной школе-конференции «Проблемы теоретической и прикладной математики», 42-й Всероссийской молодежной школе-
конференции «Современные проблемы математики»ИММ УрО РАН (Екатеринбург, 2009—2011 гг.), на алгебраическом семинаре ИММ УрО РАН, на алгебраическом семинаре ЮУрГУ
Публикации. Основные результаты диссертации опубликованы в работах [24]— [30]. Работа [26] выполнена в нераздельном соавторстве с В.В.Кабановым. Работы [28] и [30] выполнены в нераздельном соавторстве с СВ. Горяиновым. Во всех работах основными являлись исследования диссертанта.
Структура и объем работы. Диссертация состоит из введения, четырех глав и списка цитируемой литературы, содержащего 34 наименований.
