1 Общая характеристика работы

$\parbox{12.5cm}{\small\it ''С развитием теории групп и теории предст... ...Ито ''Алгебраическая комбинаторика (схемы отношений)''. - Москва, Мир. 1987.}}$

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

Первые результаты о графах с условиями комбинаторной симметрии были получены в пятидесятых годах. Пусть $L(K_n)$ -- реберный граф полного графа $K_n$ или в других обозначениях треугольный граф $T(n)$. Этот граф является сильно регулярным графом с параметрами

$$\left(\frac{n(n-1)}{2},2(n-2),n-2,4\right).$$

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

Реберный граф $L(K_{m,n})$ полного многодольного графа $K_{m,n}$ (решетчатый $m\times n$-граф) является кореберно-регулярным графом с параметрами $\left(mn,m+n-2,2\right).$ При $m=n$ решетчатый граф является сильно регулярным графом с параметрами $\left(n^2,2n-2,n-2,2\right).$ С.С. Шрикханде в [35] показал, что при $m=n\neq 4$ граф $L(K_{m,n})$ определяется этими параметрами, а при $m=n=4$, кроме $L(K_{4,4})$, существует еще в точности один граф, который теперь называется графом Шрикханде. Ситуацию без предположения о равенстве параметров $m$ и $n$ рассмотрели независимо Дж.В. Мун [31] и А.Дж. Хоффман [22].

Матрица смежности графа $\Gamma$ -- это матрица $A=(a_{ij})$, строки и столбцы которой перенумерованы вершинами графа $\Gamma$, причем $a_{ij}=1$, если $ij$ является ребром в $\Gamma$, $a_{ij}=0$ в противном случае. Матрица смежности сильно регулярного графа $\Gamma$ с параметрами $\left(v,k,\lambda , \mu \right)$ кроме собственного значения, равного $k$, имеет еще два действительных собственных значения разных знаков. Если у сильно регулярного графа $\Gamma$ набор параметров $\left(v,k,\lambda , \mu \right)$ такой же, как у треугольных или решетчатых $n\times n$-графов, то отрицательное собственное значение его матрицы смежности равно $-2$. Более того, из теории действительных симметрических матриц следует, что в этом случае любой порожденный подграф графа $\Gamma$ не может иметь собственных значений, меньших $-2$. Это свойство дает возможность восстановить строение графа $\Gamma$ с набором параметров, как у треугольных или решетчатых $n\times n$-графов.

Граф $\Gamma$ называется сильным, если для любой пары $x,y$ его вершин число общих смежных с ними вершин зависит только от того, является $x,y$ ребром или нет. Результаты Л.С. Чанга, С.С. Шрикханде и А.Дж. Хоффмана были объединены Дж.Дж. Зейделем [34], который определил все сильные графы с наименьшим собственным значением $-2$. Дж.Дж. Зейдель показал, что кроме треугольных графов $T(n)$ и решетчатых $n\times n$-графов, сильными графами, которые имеют наименьшее собственное значение $-2$, являются только графы $K_{n\times 2}$, три графа Чанга, графы Шрикханде, Шлефли, Клебша и Петерсена.

Применяя метод С.С. Симса [36] перечисления 4-вершинных подграфов, М.Д. Хестенс и Д.Г. Хигман в работе [19] показали, что в сильно регулярных графах число 4-вершинных подграфов любого заданного вида определяет число 4-вершинных подграфов всех других видов. Это свойство позволило М.Д. Хестенсу и Д.Г. Хигману получить более экономное доказательство теоремы Дж.Дж. Зейделя для случая сильно регулярных графов. Среди возможных 4-вершинных подграфов наиболее важную роль играют подграфы, изоморфные $K_4$ (полный 4-вершинный граф), $K_4-e$ (полный 4-вершинный граф с удаленным ребром) и $K_{1,3}$ (полный двудольный граф с долями из одной и трех вершин).

Заметим, что если граф $\Gamma$ с наименьшим собственным значением, равным $-2$, содержит 3-лапу $\{p; q_1, q_2, q_3\}$ (4-вершинный подграф, изоморфный $K_{1,3}$), то любая вершина $x (x\neq p)$ из $\Gamma$, смежная с вершинами $q_1$ и $q_2$, смежна с $p$ и не смежна с $q_3$. В противном случае подграф на $\{p, q_1, q_2, q_3, x\}$ имеет собственное значение, которое строго меньше $-2$. Как уже было отмечено, это невозможно. Таким образом, граф с наименьшим собственным значением, равным $-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 страниц текста, набранного в пакете L^ATEX. Нумерация основных теорем во введении одинарная, теорем и лемм в главах тройная (номер главы, номер параграфа, номер утверждения).