НЕКОТОРЫЕ АЛГЕБРАИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ КОНЕЧНЫХ ГРАФОВ

КАБАНОВ Владислав Владимирович

Научный доклад по
диссертации на соискание ученой степени
доктора физико-математических наук

Работа выполнена в отделе алгебры и топологии Института математики и механики УрО РАН.

		Научный консультант:

   доктор физ.-мат. наук, профессор МАХНЕВ А.А.

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

Пусть $G$ группа подстановок на конечном множестве $\Omega$ и $\Gamma$ связный граф с множеством вершин $\Omega$. Все графы, которые мы будем рассматривать, являются неориентированными графами без петель и кратных ребер, а в качестве подграфов мы рассматриваем только порожденные подграфы. Говорят, что $G$ дистанционно-транзитивна на графе $\Gamma$, если для любого $i = 0,\dots , \mbox{\rm diam}(\Gamma)$ группа $G$ действует транзитивно на множестве упорядоченных пар вершин находящихся в графе $\Gamma$ на расстоянии $i$ друг от друга. Граф $\Gamma$ называется дистанционно-транзитивным, если его группа автоморфизмов $\mbox{\rm Aut}(\Gamma)$ действует дистанционно-транзитивно на $\Gamma$. Точное подстановочное представление группы $X$

$$\rho : X \rightarrow \mbox{\rm Sym}(\Omega)$$

называется дистанционно-транзитивным представлением, если $\rho (X)$ действует дистанционно-транзитивно на некотором связном графе с множеством вершин $\Omega$. Хорошо известно, что в этом случае представление $\rho$ должно быть без кратностей, то есть является суммой различных комплексных неприводимых представлений для $X$. В настоящее время важной задачей является описание всех дистанционно-транзитивных представлений конечных простых групп и более обще всех представлений конечных простых групп, не содержащих кратностей.

С другой стороны, как отмечают в своей монографии Э. Баннаи и Т. Ито, дистанционно-транзитивные графы можно рассматривать как "намного более общие структуры, чем конечные группы". Более того, некоторые теоретико-групповые построения допускают обобщение на дистанционно-транзитивные графы.

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

Первые результаты о графах с условиями комбинаторной симметрии были получены в пятидесятых годах. Пусть $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$ с набором параметров, как у треугольных или решетчатых $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$.

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

Если $x,y$ пара вершин графа $\Gamma$, которые находятся на расстоянии 2 друг от друга, то подграф на множестве общих смежных с ними вершин называется $\mu$-подграфом графа $\Gamma$.

Графы без 3-лап с несвязными $\mu$-подграфами были изучены в 1994 году А.Е. Брауэром и М. Нуматой [7]. В графе с несвязными $\mu$-подграфами любой подграф, изоморфный $K_{1,2}$, содержится в подграфе, изоморфном $K_{2,2}$, то есть в $C_4$. Такие графы мы будем называть $(K_{1,2}, K_{2,2})$-однородными графами. Таким образом, граф, у которого все $\mu$-подграфы несвязны, является $(K_{1,2}, K_{2,2})$-однородным графом.

Следующая теорема, которая обобщает теорему А.Е. Брауэра и М. Нуматы в том случае, когда граф содержит $3$-коклику, доказывается в первой главе диссертации [45]. Для того, чтобы сформулировать теорему, нам понадобится понятие кликового расширения графа. Кликовым расширением графа $\Gamma$ называется граф, полученный заменой каждой вершины $a$ из $\Gamma$ на полный подграф $C(a)$, содержащий не менее одной вершины, причем вершины из различных клик $C(a)$ и $C(b)$ смежны тогда и только тогда, когда вершины $a$ и $b$ смежны в $\Gamma$. Кликовое расширение графа $\Gamma$ называется $\alpha$-расширением $\Gamma$, если для любой вершины $a\in \Gamma$ подграф $C(a)$ содержит $\alpha$ вершин для некоторого фиксированного $\alpha >0$. Заметим, что если граф $\Gamma$ не содержит 3-лап, то и любое его кликовое расширение не содержит 3-лап.

ТЕОРЕМА 1.
Пусть связный граф $\Gamma$ содержит $3$-коклику и не содержит $3$-лап. Если любой подграф из $\Gamma$, изоморфный $K_{1,2}$, содержится в подграфе, изоморфном $K_{2,2}$, то $\Gamma$ является кликовым расширением одного из следующих графов:
$(1)$ решетчатый $m\times n$-граф при $m\ge 3$, $n\ge 3$;
$(2)$ треугольный граф $T(n)$ при $n\ge 6$;
$(3)$ граф Шлефли.

В работе [29] М. Нуматой была получена классификация реберно-регулярных графов, которые не содержат 3-лап и содержат $3$-коклику.

Следующая теорема является аналогом этого результата для кореберно-регулярных графов без 3-лап и также доказывается в первой главе диссертации [55].

ТЕОРЕМА 2.
Пусть $\Gamma$ -- кореберно-регулярный граф без $3$-лап. Тогда $\Gamma$ является либо дополнительным графом к регулярному графу без треугольников, либо $\alpha$-расширением $(\alpha \ge 1)$ одного из следующих графов:
$(1)$ вполне несвязный граф с числом вершин $m$ $(m \neq 2)$;
$(2)$ решетчатый $m\times n$-граф при $m\ge 3, n\ge 3$;
$(3)$ треугольный граф $T(m)$ при $m\ge 6$;
$(4)$ граф Шлефли.

В той же работе [29] М. Нуматой получена классификация реберно-регулярных графов диаметра не менее 3, которые не содержат 3-лап и содержат $3$-коклику.

Полученные выше результаты служат основой для исследования графов без 3-лап с более слабыми условиями регулярности во второй главе диссертации.

Пусть $x,y$ пара вершин графа $\Gamma$, которые находятся на расстоянии 2 друг от друга. Обозначим число вершин $\mu$-подграфа для $x,y$ через $\mu (x,y)$. Если все $\mu$-подграфы графа $\Gamma$ имеют одинаковое число вершин, то есть $\mu (x,y)=\mu$, то это число называется параметром $\mu$ графа $\Gamma$. Понятно, что если граф имеет параметр $\mu$, то $\mu$ не меньше 1. Если граф $\Gamma$ имеет параметр $\mu$, но его значение неизвестно, то мы говорим, что $\Gamma$ имеет равномощные $\mu$-подграфы. По определению сильного графа, любая пара несмежных вершин в нем имеет одно и то же число общих соседей. Это условие автоматически приводит к тому, что либо диаметр сильного графа равен 2 и он имеет равномощные $\mu$-подграфы, либо число общих соседей любой пары несмежных вершин в нем равно 0. Таким образом, условие равномощности $\mu$-подграфов значительно ослабляет соответствующее условие в определении сильного графа.

Вторая глава диссертации посвящена классификации графов без 3-лап с равномощными $\mu$-подграфами без ограничения на диаметр графа. Изучение класса графов без 3-лап с равномощными $\mu$-подграфами самая трудная и большая по объему часть работы. Оказалось, что сильное влияние на строение графа оказывает наличие или отсутствие в графе порожденных 4-циклов. Графы без 4-циклов с равномощными $\mu$-подграфами изучал П. Тервиллигер в [38]. Он доказал реберную регулярность таких графов при некоторых дополнительных условиях, в частности, для регулярных графов диаметра 2. Графы без порожденных 4-циклов с равномощными $\mu$-подграфами мы будем называть графами Тервиллигера.

Следующая теорема классифицирует регулярные графы Тервиллигера без 3-лап [56].

ТЕОРЕМА 3.
Связный регулярный граф Тервиллигера без 3-лап является $\alpha$-расширением одного из следующих графов:
$(1)$ граф без $3$-лап с $\mu = 1$,
$(2)$ граф икосаэдра.

В следующей теореме классифицированы связные $\mu$-регулярные графы без 3-лап [56].

ТЕОРЕМА 4.
Связный $\mu$-регулярный граф $\Gamma$ без $3$-лап либо является графом Тервиллигера, либо имеет диаметр $2$.

Теперь строение связных $\mu$-регулярных графов определяют теоремы теорема 2 и теорема 3, поскольку в них определены графы Тервиллигера без $3$-лап и кореберно-регулярные графы без 3-лап.

В следующей теореме мы не предполагаем регулярности графа, и, таким образом, она завершает классификацию графов Тервиллигера без 3-лап [57]. Эта теорема расширяет теорему Тэйлора-Левингстона [37]. Через $a^\bot$ обозначим порожденный подграф, состоящий из вершины $a$ и всех смежных с ней вершин. Через $\Gamma^\bot$ обозначим подграф $$\bigcap _{a\in\Gamma} a^\bot$$.

ТЕОРЕМА 5.
Пусть $\Gamma$ -- связный граф Тервиллигера без $3$-лап. Тогда либо граф $\Gamma$ является $\alpha$-расширением графа икосаэдра, либо подграф на множестве всех вершин с некликовыми окрестностями из $\Gamma -\Gamma^\bot$ является пустым, кликой или $\alpha$-расширением связного графа с $\mu = 1$.

При условии, что граф содержит 3-коклику, удается получить полную классификацию не только графов Тервиллигера без 3-лап, но и всех графов без 3-лап с равномощными $\mu$-подграфами [57].

ТЕОРЕМА 6.Пусть $\Gamma$ -- связный граф без $3$-лап, содержащий $3$-коклику. Пусть также все $\mu$-подграфы из $\Gamma$ имеют одинаковое число вершин. Тогда либо $\Gamma$ имеет диаметр больше двух и является графом из заключения теоремы 5, либо граф $\Gamma$ является регулярным графом и его строение определяют пункты (2), (3), (4) теоремы 2.

Следующая теорема посвящена описанию графов без 3-лап с регулярными $\mu$-подграфами одинаковой ненулевой валентности. Регулярный граф называется редуцированным, если для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$. В статье [27] А.А. Махнев перенес это понятие на класс всех графов. Произвольный граф $\Gamma$ называется редуцированным, если для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot \subseteq x^\bot \}$ состоит из единственной вершины $a$. Легко видеть, что в классе регулярных графов оба определения эквивалентны.

В [27] А.А. Махнев классифицировал редуцированные графы без 3-лап с регулярными $\mu$-подграфами валентности $\alpha$, где $\alpha >0$. Мы докажем, что если $\Gamma$ является графом без 3-лап с регулярными $\mu$-подграфами одинаковой валентности $\alpha$, где $\alpha >0$, и для любой вершины $a$ из $\Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ совпадает с $\{a\}$, то и множество $\{x\in \Gamma \vert a^\bot \subseteq x^\bot \}$ состоит из единственной вершины $a$. Следующая теорема [43,44] усиливает основной результат из [27].

ТЕОРЕМА 7.
Пусть $\Gamma$ -- связный граф, который не содержит $3$-лап и содержит $3$-коклику и выполнены следующие условия:
$(a)$ все $\mu$-подграфы из $\Gamma$ являются регулярными графами одинаковой валентности $\alpha$ для некоторого числа $\alpha >0$;
$(b)$ для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$.
Тогда граф $\Gamma$ является треугольным графом $T(n)$ при $n\geq 6$, графом икосаэдра или графом Шлефли.

В работе [19] М.Д. Хестенс и Д.Г. Хигман отметили другой момент, касающийся связи между теорией графов и теорией транзитивных групп подстановок. Пусть $G$ -- транзитивная группа подстановок на множестве $\Omega$. Тогда орбиты группы $G$ на множестве $\Omega\times\Omega$ называются орбиталами, а их число -- рангом группы $G$. Каждый орбитал $\Delta$ является либо симметричным, либо строго антисимметричным. В первом случае он определяет обыкновенный граф с множеством вершин $\Omega$ и множеством ребер $\Delta$. Во втором случае орбитал имеет симметричную ему пару $\Delta'=\{(y,x)\vert (x,y)\in \Delta\}$ и определяет ориентированный граф. Известно, что группа $G$ обладает симметричным орбиталом тогда и только тогда, когда ее порядок является четным числом [40].

Если группа $G$ имеет ранг 3, то оба орбитала, отличные от диагонали $\{(x,x)\vert x\in \Omega\}$, являются симметричными и определяют пару дополнительных сильно регулярных графов. Такой сильно регулярный граф называется графом ранга 3. В настоящее время с использованием классификации конечных простых групп получено полное описание групп и графов ранга 3 ([9], [25], [2], [26], [24]).

Много работ посвящено изучению транзитивных групп подстановок без ограничений на их ранг и графов, которые определяются их орбиталами. В программном комплексе GAP [32] имеется специальная инструкция EdgeOrbitGraph, которая позволяет строить граф по орбиталу заданной транзитивной группы подстановок. При помощи этой инструкции автором найден пример дистанционно-транзитивного локально без 3-лап графа с несвязными окрестностями вершин. Этот граф является локально $4L(K_{4,2})$-графом, то есть графом, любая окрестность вершины которого является объединением четырех решетчатых $4\times 2$-графов. Он получается из наименьшего орбитала группы Хигмена-Симса при представлении ее как транзитивной группы подстановок, действующей на классе центральных инволюций.

С другой стороны, интересен следующий, связанный с данным, вопрос. А именно, какими свойствами должен обладать граф, чтобы множество его ребер оказалось орбиталом для группы подстановок, действующей транзитивно на его вершинах (граф, изоморфный такому графу, мы назовем орбитальным)? Этот вопрос тесно связан с вопросом изучения групп автоморфизмов графов. В работах [14], [15] Х. Еномото получил характеризацию графов Хэмминга как орбитальных графов для транзитивных групп подстановок с определенными ограничениями на их подстепени. Первая теорема третьей главы диссертации, опубликованная в [56], усиливает результат Х. Еномото. Для ее формулировки нам понадобится определение отделимого графа. Граф $\Gamma$ назовем отделимым, если для любой вершины $a$ из $\Gamma$ подграф $\Gamma_{2}(a)$ содержит вершины $b,c$ на расстоянии 2 в $\Gamma_{2}(a)$ и $\mu$-подграф $[b]\cap [c]$ для любой такой пары не пересекает $[a]$.

ТЕОРЕМА 8.
Пусть $\Gamma$ -- связный вполне регулярный граф с параметрами $(v,k,\lambda,\mu)$, $\mu >1$. Граф $\Gamma$ отделим тогда и только тогда, когда он является одним из следующих графов:
$(1)$ граф Хемминга $H(n,m)$ при $m\ge 3, n\ge 2$;
$(2)$ треугольный граф $T(m)$ при $m\ge 6$;
$(3)$ граф Шлефли;
$(4)$ граф икосаэдра.

Используя классификацию реберно-регулярных графов без 3-лап [29], М. Нумата в работе [30] получил характеризацию графов Грассмана и Джонсона как графов локально без 3-лап, в которых все $\mu$-подграфы являются изоморфными реберно-регулярными графами диаметра 2. Заметим, что если граф $\Gamma$ удовлетворяет условию теоремы М. Нуматы, то из последнего условия на все $\mu$-подграфы графа $\Gamma$ непосредственно следует реберная регулярность самого $\Gamma$.

Наша следующая цель получить классификацию локально без 3-лап графов с более слабым условием на $\mu$-подграфы, которое не влечет даже регулярности графа. Это стало возможно благодаря классификации графов без 3-лап с равномощными $\mu$-подграфами. С помощью этой классификации мы исследуем класс графов, в которых окрестности вершин не содержат 3-лап и все $\mu$-подграфы являются регулярными графами валентности $\alpha$, где $\alpha >0$. В отличии от [30] мы не требуем даже равномощности всех $\mu$-подграфов. Поскольку наше условие на $\mu$-подграфы не влечет регулярности графа, то мы дополнительно накладываем на граф условие редуцированности.

ТЕОРЕМА 9.
Пусть $\Gamma$ -- связный граф, который удовлетворяет следующим условиям:
$(1)$ окрестность любой вершины из $\Gamma$ не содержит $3$-лап;
$(2)$ $\Gamma$ содержит $3$-лапу;
$(3)$ все $\mu$-подграфы из $\Gamma$ являются регулярными графами одинаковой валентности $\alpha$ для некоторого числа $\alpha >0$;
$(4)$ для любой вершины $a\in \Gamma$ множество $\{x\in \Gamma \vert a^\bot = x^\bot \}$ состоит из единственной вершины $a$. Тогда $\Gamma$ является локально $G$-графом, где $G$ один из следующих графов:
$(a)$ $\beta$-расширение решетчатого $m\times n$-графа при $\beta=\alpha /2$ и $m\geq 3$, $n\geq 3$;
$(b)$ треугольный граф $T(n)$ при $n\geq 6$;
$(c)$ граф Шлефли.

Если граф $G$ является $\beta$-расширением решетчатого $m\times n$-графа, то класс локально $G$-графов довольно широк и труден для изучения. Примерами таких графов являются графы Грассмана, графы Джонсона и их частные.

Пусть $V$ является $n$-мерным векторным пространством над конечным полем $F$. Графом Грассмана для $m$-подпространств из $V$ называется граф $\left[V\atop m\right]$ с множеством вершин, равным множеству всех подпространств размерности $m$ из $V$, причем две вершины $A, B$ смежны тогда и только тогда, когда $dim(A\cap B) = m-1$. Если $X$ -- конечное множество, то графом Джонсона для $m$-подмножеств из $X$ называется граф с множеством вершин, равным множеству $\left(X\atop m\right)$ всех $m$-элементных подмножеств из $X$, причем две вершины $a, b$ смежны тогда и только тогда, когда $\vert a\cap b\vert = m-1$. Если множество $X$ состоит из $n$ элементов, то такой граф обозначим через $J(n,m)$. Заметим, что граф $J(n,2)$ совпадает с треугольным графом $T(n)$. Пусть $\rho$ -- некоторое разбиение множества вершин графа $\Gamma$ на подмножества. Частным $\overline\Gamma = \Gamma/\rho$ для графа $\Gamma$ по разбиению $\rho$ называется граф на фактор-множестве по $\rho$ множества вершин $\Gamma$, в котором две вершины $\overline a, \overline b$ смежны только, если $a\neq b$ и граф $\Gamma$ содержит ребро, которое соединяет некоторую вершину из класса $\overline a$ с некоторой вершиной из класса $\overline b$. Пусть $n=2m$ и $\rho$ является разбиением множества вершин графа Джонсона $J(2m,m)$ на двухэлементные классы, содержащие $m$-элементное подмножество и его дополнение в $X$. Частным графа Джонсона называется граф $J(2m,m)/ \rho$.

Графы Джонсона и частные графов Джонсона дают нам примеры локально $n\times m$-графов. Эти примеры не исчерпывают класс таких графов. В статье [3] построены другие примеры локально $n\times m$-графов и найдены все локально $4\times 4$-графы. Там же получено описание локально $n\times m$-графов, в которых каждый $\mu$-подграф является объединением изолированных четырехугольников. Характеризация локально $n\times m$-графов при $n=3$ получена Дж. Холлом в [17]. Проблема полного описания локально $n\times m$-графов для любых $n, m$ остается открытой. Мало пока известно в общем случае и о локально треугольных графах.

Однако, если все $\mu$-подграфы из $\Gamma$ имеют диаметр 2, можно получить более точный ответ.

ТЕОРЕМА 10.
Пусть $\Gamma$ -- связный граф, который удовлетворяет условиям теоремы 9 и все $\mu$-подграфы из $\Gamma$ имеют диаметр 2. Тогда $\Gamma$ является одним из следующих графов:
$(1)$ граф Грассмана;
$(2)$ граф Джонсона или его частное;
$(3)$ локально $T(n)$-граф при $n\geq 6$;
$(4)$ граф Госсета $E_7 (1)$.

Все графы Грассмана, графы Джонсона и их частные, граф Госсета $E_7 (1)$ являются дистанционно-транзитивными графами.

Заметим также, что граф системы корней $E_8$ (см. [5]) является локально $E_7 (1)$-графом и играет особую роль в теории графов, у которых любое собственное значение не меньше, чем $-2$. По теореме А.Дж. Хоффмана [23] любой такой граф является либо обобщенным реберным графом, либо подграфом $E_8 (1)$.

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

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

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

В заключение хочу выразить свою глубокую благодарность научному консультанту доктору физ.-мат. наук, профессору А.А. Махневу.

АВТОРЕФЕРАТ
Теорема 1
Теорема 2
Теорема 3
Теорема 4
Теорема 5
Теорема 6
Теорема 7
Теорема 8
Теорема 9
Теорема 10