Две задачи алгебраической теории графов

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

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

1 Графы без 3-лап

1.1 Предварительные результаты

1.2 Сильные тройки в графах без 3-ла.п

1.3 Графы без 3-лап с ограничениями на их д-подграфы

1.4 Исключительные тройки в графах без 3-лап с ограничениями

на их д-подгра.фы

1.5 Особые тройки в графах без 3-ла.п с ограничениями на их д-подграфы

2 Точные графы Деза без 3-коклик с ц = Ь

2.1 Предварительные результаты
2.2 Некоторые свойства точных графов Деза без 3 - коклик е д = Ь
2.3 Точные графы Деза, которые являются соединениями сильно
регулярных графов или точных графов Деза
2.4 Графы Деза, которые являются кликовыми расширениями сильно регулярных графов
Список литературы

Введение
Пусть (? — транзитивная группа подстановок на конечном множестве X. Если порядок группы четен, то стабилизатор в С? точки х £ X имеет симметричную орбиту Д(ж) на X отличную от {х}. Тогда по группе С можно построить граф Г с множеством вершин X, и две вершины х,у смежны в Г тогда и только тогда, когда у £ Д(х).
Изучение графов, полученных .таким образом, является важной задачей алгебраической теории графов. Если в качестве группы С? рассмотреть симметрическую группу подстановок Бп на п символах, а в качестве множества X — множество всех транспозиций из £п и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф Т(п). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами ("("т.1.),2(п ~ 2),п — 2,4). Кроме того, он не содержит порожденных АДз-подграфов В работах 1959-60 гг. Л. Чанг [10] и А. Хоффман [13], [14] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п — 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [9].
Класс графов без 3-лап содержит такой важный класс графов, как реберные графы,- Реберный граф Ь[Кт<п) полного двудольного графа Кт<п с долями порядка т и п является кореберно регулярным графом с параметрами (тп,т + п — 2,2). Граф Ь(Кт<п) называют т х п-решеткой, и при т = п этот граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Щрикханде [18] и А. Хоффман [15] показали, что граф, имеющий параметры т х п-решетки, является либо т х п-решеткой, либо графом Шрикханде, при п — 4. Все вышеперечисленные графы имеют наименьшее собственное значение —2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж Зсйделсм [17], который определил

все сильно регулярные графы с наименьшим собственным значением —2. В частности, Дж. Зейдель показал, что кроме треугольных графов Т(п) и п х п-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
Полное описание графов без 3-лап с несвязными /і-подграфами было получено А. Брауэром и М. Нуматой [8]. Они показали, что если граф связный конечный и содержит 3-коклику, то он является тп х п-решеткой Этот результат был обобщен В.В. Кабановым в [5]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его д-подграф имеет радиус больше 1, тогда и только тогда, когда он является либо треугольным графом Т(п) с 71 > 6, либо m х n-решеткой о п > 3 и 7тг > 3, либо графом Шлефли. Граф Шлефли — это единственный сильно регулярный граф с параметрами (27,16,10,8) В работах И.А. Вакулы и В.В. Кабанова [1], [2] описаны связные графы без 3-лап с неклнковымп д-подграфами.
А. Деза и М. Деза рассматривали химические графы полициклнчеекпх сопряженных углеводородов и полицикличеких ароматических углеводородов. В связи с этим исследованием возникла необходимость изучения графов, которые впоследствии были названы графами Деза.
В 1994 г. А. Деза и М Деза [11) привели пример точного графа Деза с параметрами (40,15,6,4).
М. Эриксон, С. Фернандо, У.Х. Хаймерс, В. Харди и Дж. Хемметр [12] описали все точные графы Деза с числом вершин не более 13. A.A. Мах-невым [7] рассматривались графы Деза, которые являются кликовыми или кокликовыми расширениями сильно регулярных графов.
В диссертации рассматриваются только конечные неориентированные графы без петель и кратных ребер. Далее всюду подграф графа Г будет означать индуцированный подграф графа Г. Для вершины а графа Г через

Случай 1: Отсюда 5 Случай 2: Значит 21 Случай 3 Отсюда /.I Случай 4: Отсюда д Случай 5: Следовате Случай 6: Тогда д > Случай 7: Получаем Случай 8: Отсюда н Случай 9 Отсюда 5 Случай 10: Значит 5 = Случай
Пусть вершина и не смежна с ги. Обозначим |[гг] П М(у,г) | = а, |[ад] П М(х, г) — /3 и |М(х, у) П М(и, гс)|' = у. Тогда М(и, го)| = а + /3 + 7 + 5, где 5 = М(и, гг) — (жиу1)! и 5 > 1. Рассмотрим возможные варианты мощностей вышеупомянутых д-подграфов и подсчитаем число вершин в подграфах
М(х,у) и М(и, и)).
М(х,у) = д > (д - а) + (д-/3) -7 М(и, ш)| = д = а + /3 + 7 + 5 Отсюда (5 = 0. Противоречие.
М(х,у) = д > {и - а) + (и-Р) -7 М(и,'ш) = д — а + /3 + 7 + 8 Значит 2д > 2г/ + 8. Противоречие с условием м > д.
Осу)! = Д > - «) + ~ Р)
|М(гд ш)| = и — а + (3 + 7 + 5 Отсюда д > м + Противоречие с условием I/ > д.
|М(ж,у)! = д > (/у - а) + (д -/3) -7 ] ЛУ (гг, го) | = д = а + (3 + 7 + 5 Отсюда /4 > У + 5, что противоречит условию и > д.
|М(ж,у)[ = д > (м - а) + (д - /3) - 7 |М(и, ш)| = м = а + /3 + 7 + 5 Следовательно, 5 = 0. Противоречие.
М(х,у) = д > (д - а) + {и- /3) - 7 | М(гг, ш) | = д — а + /3 + 7 + 5 Тогда д > гг + 5. Противоречие с условием м > д.
|М(ж,у)| = д> (д-а) + (м-/3)-7 |М(гг, ш)| = г/ = а: + (3 + 7 + 8 Получаем 5 = 0. Противоречие.
М{х,у) = д > (д.- а) + (д -/3)
|М(г4, га) | = V = а: + /3 + 7 + 5 Отсюда находим д > а + /3 + 7, м = д + 5.
|М(ж,у)| = г/ > (м - а) + (д -/3) -7 [М(г4, ш)| = д = а + /3 + 7 + 5 Отсюда 5 = 0. Противоречие.
М{х,у)[= и > (м — а) + (д — /3) — 7 |М(г4,ш)| = д = а + /3 + 7 + 5 Значит 5 = 0. Противоречие.
.|М(ж, д)| = м > (м - а) + (г/ - /3) - 7 |М(гд гг)| = д = а + /3 + 7 + 5 Получаем д > м + 5. Это противоречит условию м > д.