Некоторые алгебраические аспекты теории конечных графов Кабанов, Владислав Владимирович

Введение к работе

"С развитием теории групп и теорьи представлений групп спектр исследований в области симметрии чрезвычайно расширился, затронув самые различные разделы математики, физики, химии, биологии и других научных дисциплин. В этом мощном потоке за последние два десятилетия выделилось принципиально новое направление, связанное с изучением так называелш! дистанционно-транзитивных графов и иг различных обобщений."

Ю.И. Журавлев, А.И. Кострикик Из предисловия редакторов перевода книги Э. Баннаи, Т. Ито "Алгебраическая комбинаторика (схемы отношений)". - Москва, Мир. 1987.

Актуальность темы. В настоящее время в исследования графов с условиями симметрии вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитишшети и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметрия графа влечет его дистанционную транзитивность. В настоящей диссертационной работе развиваются новые методы исследования некоторых условий комбинаторной симметрии, которые дают возможность в ряде случаев получить полную классификацию рассматриваемых объектов.

Первые результаты о графах с условиями комбинаторной симметрии были получены в пятидесятых годах. Пусть L{K_n) — реберный граф полного графа К„ или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами

(^,2(п-2),п-2,4).

В работах 1959-60 годов Л.С. Чанг [11] и А.Дж. Хоффман [20, 21] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п за исключением п = 8. Для случая п — 8 ими было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л.С. Чангом в 1949 году [10].

Реберный граф L(K_m) полного многодольного графа К_т<п (решетчатый m х n-граф) является кореберно-регулярным графом с параметрами (тп, т + п — 2,2). При т = п решетчатый граф является сильно регулярным графом с параметрами (га²,2п — 2, п — 2,2). С.С. Шрик-ханде в [35] показал, что при т = п ф 4 граф L{K_m%n) определяется этими параметрами, а при т = n = 4, кроме Ь(Кц^), существует еще в точпости один граф, который теперь называется графом Шрикханде. Ситуацию без предположения о равенстве параметров тип рассмотрели независимо Дж.В. Мун [31] и А.Дж. Хоффман [22].

Матрица смежности графа Г — это матрица А = (a_i;), строки и столбцы которой перенумерованы вершинами графа Г, причем а^ = 1, если ij является ребром в Г, ay = 0 в противном случае. Матрица смежности сильно регулярного графа Г с параметрами (г>, &, А, /х) кроме собственного значения, равного к, имеет еще два действительных собственных значения разных знаков. Если у сильно регулярного графа Г набор параметров (v,k, Х,ц) такой же, как у треугольных или решетчатых п х n-графов, то отрицательное собственное значение его матрицы смежности равно —2. Более того, из теории действительных симметрических матриц следует, что в этом случае любой порожденный подграф графа Г не может иметь собственных значений, меньших -2. Это свойство дает возможность восстановить строение графа Г с

набором параметров, как у треугольных или решетчатых п х п-графов.

Граф Г называется сильным, если для любой пары х, у его вершин число общих смежных с ними вершин зависит только от того, является х_ьу ребром или пет. Результаты Л.С. Чанга, С.С. Шрикханде и А.Дж. Хоффмана были объединены Дж.Дж. Зейделсм [34], который определил все сильные графы с наименьшим собственным значением -2. Дж.Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х и-графов, сильпыми графами, которые имеют наименьшее собственное значение —2, являются только графы К„х2і три графа Чанга, графы Шрикханде, Шлефли, Клебша и Петерсена.

Применяя метод С.С. Симса [36] перечисления 4-вершинных подграфов, М.Д. Хестенс и Д.Г. Хигман в работе [19] показали, что в сильно регулярных графах число 4-вершинных подграфов любого заданного вида определяет число 4-вершинных подграфов всех других видов. Это свойство позволило М.Д. Хестенсу и Д.Г. Хигману получить более экономное доказательство теоремы Дж.Дж. Зейделя для случая сильно регулярных графов. Среди возможных 4-вершинных подграфов наиболее важную роль играют подграфы, изоморфные &'₄ (полный 4-вершинный граф), К\ — е (полный 4-вершинный граф с удаленным ребром) и К\$ (полпый двудольный граф с долями из одной и трех вершин).

Заметим, что если граф Г с наименьшим собственным значением, равным —2, содержит 3-лалу {р;ді,?2,9з} (4-вершинный подграф, изоморфный іі,з), то любая вершина х{х ф р) из Г, смежная с вершинами q\ и q-i-, смежна с р и не смежна с q₃. В противном случае подграф на {р>

меньшим собственным значением, равным —2, либо не содержит 3-лап, либо содержит 3-лапы, но тогда окрестность любой его вершины не содержит 3-лап.

Цель работы. Исследование класса графов без 3-лан и локально без 3-лап в совокупности с некоторыми условиями комбинаторной симметрии, в том числе и с некоторыми условиями регулярности.

Общая методика исследований. В диссертационной работе развиваются новые методы локального анализа комбинаторно-симметричных графов.

Научная новизна. Все результаты диссертации являются новыми.

Практическая ценность. Диссертация носит теоретический характер. Результаты и методы работы могут быть использованы в алгебраической комбинаторике, теории графов и теории конечных групп.

Апробация работы. Результаты работы докладывались на Международных конференциях по алгебре в 1993 году в Красноярске [42], в 1996 году в Санкт-Петербурге [51] и в 1998 году в Москве [46], на III Краковской международной конференции по теории графов в 1997 году [50], на Пятом чехо-словацком симпозиуме по комбинаторике, теории графов, алгоритмам и приложениям в 1998 году [47], на конференции "Случайные структуры и алгоритмы" в Познани в 1999 году, на международной конференции памяти П. Эрдеша в Будапеште в 1999 году [48], на семинаре кафедры высшей алгебры Московского государственного университета, на семинаре " Экстремальные задачи теории графов" в Институте математики СО РАН, на семинаре отдела алгебры и топологии Института математики и механики УрО РАН, на городском

алгебраическом семинаре в Уральском государственном университете.

Публикации. Основные результаты диссертации опубликованы в работах [41]-[55]. Работы [49]-[55] написаны в нераздельном соавторстве с А.А. Махневым. Из работы [41] в диссертации использованы только результаты, принадлежащие автору.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав и списка литературы (72 наименования), занимает 195 страниц текста, набранного в пакете I&TgX. Нумерация основных теорем во введении одинарная, теорем и лемм в главах тройная (номер главы, номер параграфа, номер утверждения).