Введение к работе
Актуальность темы.
Пусть G — транзитивная группа подстановок на конечном множестве X. Если порядок группы четен, то стабилизатор в G точки х Є X имеет симметричную орбиту А (ж) на X отличную от {х}. Тогда по группе G можно построить граф Г с множеством вершин X, и две вершины х, у смежны в Г тогда и только тогда, когда у Є А(х).
Изучение графов, полученных таким образом, является важной задачей алгебраической теории графов. Если в качестве группы G рассмотреть симметрическую группу подстановок Sn на п символах, а в качестве множества X — множество всех транспозиций из Sn и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф Т(п). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами (п{-п~ >; 2(п — 2),п — 2,4). Кроме того, он не содержит порожденных Х13-подграфов. В работах 1959-60 гг. Л. Чанг [8] и А. Хоффман [11], [12] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [7].
Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберный граф L(Kmn) полного двудольного графа Ктп с долями порядка тип является кореберно регулярным графом с параметрами (тп,т + п — 2, 2). Граф L(Km,n) называют т х п-решеткой, и при т = п этот граф является сильно регулярным графом с параметрами (п2, 2п — 2, п — 2, 2). С. Шрикханде [15] и А. Хоффман [13] показали, что граф, имеющий параметры т х гг-решетки, является либо т х гг-решеткой, либо графом Шрикханде, при п = 4. Все вышеперечисленные графы имеют наименьшее собственное значение —2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж. Зейделем [14], который определил все сильно регулярные графы с наименьшим собственным значением —2. В частности, Дж. Зейдель показал, что кроме треугольных графов Т(п) и пх гг-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Полное описание графов без 3-лап с несвязными /х-подграфами было получено А. Брауэром и М. Нуматой [6]. Они показали, что если граф связный конечный и содержит 3-коклику, то он является m х гг-решеткой. Этот результат был обобщен В.В. Кабановым в [4]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его /х-подграф имеет радиус больше 1, тогда и только тогда, когда он является либо треугольным графом Т(п) сп > 6, либо m х гг-решеткой с п > Зит> 3, либо графом Шлефли. Граф Шлефли — это единственный сильно регулярный граф с параметрами (27,16,10,8). В работах И.А. Вакулы и В.В. Кабанова [1], [2] описаны
связные графы без 3-лап с некликовыми /л-подграфами.
А. Деза и М. Деза рассматривали химические графы полициклических сопряженных углеводородов и полицикличеких ароматических углеводородов. В связи с этим исследованием возникла необходимость изучения графов, которые впоследствии были названы графами Деза.
В 1994 г. А. Деза и М. Деза [9] привели пример точного графа Деза с параметрами (40,15, 6, 4).
М. Эриксон, С. Фернандо, У.Х. Хаймерс, В. Харди и Дж. Хемметр [10] описали все точные графы Деза с числом вершин не более 13. А.А. Махневым [5] рассматривались графы Деза, которые являются кликовыми или кокликовыми расширениями сильно регулярных графов.
В диссертации рассматриваются только конечные неориентированные графы без петель и кратных ребер. Далее всюду подграф графа Г будет означать индуцированный подграф графа Г. Для вершины а графа Г через [а] обозначим подграф на множестве всех вершин, смежных с а. Этот подграф называется окрестностью вершины а в графе Г. Через ка обозначим валентность вершины а в Г, т. е. число вершин в [а]. Граф Г называется регулярным валентности к, если ка = к для любой вершины а из Г. Для ребра ас графа Г через \ас обозначим число вершин в подграфе [а] П [с]. Граф Г называется реберно регулярным с параметрами (г>, к, А), если Г — регулярный граф на v вершинах валентности к, в котором каждое ребро лежит в Л треугольниках, т. е. Хас = А для любого ребра ас графа Г. Подграф [а] П [Ь] назовем fi-подграфом, если вершины a, b находятся на расстоянии 2 друг от друга в графе Г и будем обозначать его через М(а, Ъ). Граф Г на v вершинах валентности к называется /л-регулярным с параметрами (г>, fc,/j), если все его /j-подграфы имеют /л вершин. Если такой граф имеет диаметр 2, то он называется кореберно регулярным. Если реберно регулярный граф с параметрами (г>, к, А) является /j-регулярным графом, то он называется вполне регулярным графом с параметрами (v, к, А,/і). Вполне регулярный граф диаметра 2 называется сильно регулярным.
Полный граф назовем кликой, а вполне несвязный граф — кокликой. Клика (коклика) порядка п называется п-кликой (п-кокликой).
Пусть п — натуральное число. Под п-расширением графа Г будем понимать граф Г', полученный заменой каждой вершины а из Г на гг-клику (а), причем вершины из (а) и (6) смежны в Г' тогда и только тогда, когда а и b смежны в Г.
Граф Г на v вершинах назовем графом Деза с параметрами (v, k, Ь, а), если для любых вершин и и w из Г
и- -і ^ г -и \ а или 6, если ифіи,
у к, если и = w,
где v, к,Ь,а — целые числа такие, что 0
Очевидно, класс графов Деза содержит класс сильно регулярных графов.
Графы Деза, не являющиеся сильно регулярными и имеющие диаметр 2, называются точными графами Деза.
Рассмотрим графы Г і = (Vi,Ei) и Г2 = (V2,E2), где V\ и V2 — непересекающиеся множества вершин, а Е\ и Е2 — множества ребер графов Г і и Г2 соответственно.
Объединением таких графов Г і и Г2 назовем граф Г і U Г2 = ( U V2, Е\ U Е2).
Суммой графов Гі и Г2 назовем граф Г і + Г2 = (Vi U V2, Е\ U Е2 U Е3), где Е3 = {{х,у} | xeVlyye V2}.
Дополнение Г графа Г имеет в качестве множества вершин множество вершин графа Г и две вершины в Г смежны тогда и только тогда, когда они не смежны в Г.
Цель диссертации. Целью данной работы является решение следующих задач.
Изучить связные графы без порожденных Х13-подграфов, содержащих 3-коклику, в которых для любой пары вершин и и г>, находящихся на расстоянии 2 друг от друга, подграф M(u,v) = [и] П [v] содержит ц вершин, если он не является кликой, и содержит v вершин в противном случае.
Исследовать точные графы Деза без 3-коклик с /i = Ъ.
Методы исследования. Основными методами исследования являются методы алгебраической теории графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следующие.
Классифицированы связные графы без порожденных Х^з-подграфов, содержащих 3-коклику, в которых для любой пары вершин и и г>, находящихся на расстоянии 2 друг от друга, подграф M(u,v) = [и] П [v] содержит ц вершин, если он не является кликой, и содержит v вершин в противном случае.
Найдено соотношение для параметров а и b точного графа Деза без 3-коклик с ц = Ь.
Описаны некоторые свойства и в отдельных случаях получено полное описание точных графов Деза без 3-коклик с [i = b.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты могут быть использованы для характеризации графов, возникающих из алгебраических структур, в частности, графов Джонсона и Грассмана, а также в химии кристаллических соединений.
Апробация работы. Основные результаты работы докладывались на 35-й, 37-40-ой Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004, 2006-2009 гг.), Международной школе-конференции по теории групп (Нальчик, 2007 г.).
Результаты работы докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.
Публикации. Основные результаты диссертации опубликованы в работах [16]—[21]. Работы [16]—[19] и [21] выполнены в нераздельном соавторстве с В.В. Кабановым.
Структура и объем работы. Работа состоит из введения, двух глав и списка цитированной литературы, содержащего 24 наименования.
