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

РОССИЙСКАЯ АКАДЕМИЯ НАУК фд

УРАЛЬСКОЕ ОТДЕЛЕНИЕ

1 9 т 2000

ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

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

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

(01.01.06 — математическая логика, алгебра и теория чисел)

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

ЕКАТЕРИНБУРГ — 2000

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

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

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

Официальные оппоненты:

доктор физ.-мат. наук, доцент ИЛЬИНЫХ А.П. доктор физ.-мат. наук, профессор КАЗАРИН J1.C. доктор физ.-мат. наук, профессор РОЖКОВ A.B.

Ведущая организация:

Институт математики СО РАН.

Защита состоится 18 апреля 2000 г. в 16 ч. 00 м. на заседании диссертационного совета Д.002.07.03 но защите диссертаций на соискание ученой степени доктора наук при Институте математики и механики УрО РАН по адресу: г. Екатеринбург, ул. С.Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 16 марта 2000 г.

И. о. ученого секретаря диссертационного совета

доктор физ.-мат. наук \Co^J КОНДРАТЬЕВ A.C.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

Заметим, что если граф Г с наименьшим собственным значением, равным —2, содержит 3-лалу {р;91,92,9з} (4-вершинный подграф, изоморфный то любая вершина х(х ф р) из Г, смежная с вершинами <71 и 92, смежна с р и не смежна с 93. В противном случае подграф на {р>91,92,9з, имеет собственное значение, которое строго меньше —2. Как уже было отмечено, это невозможно. Таким образом, граф с наи-

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

Если х, у пара вершин графа Г, которые находятся на расстоянии 2 друг от друга, то подграф на множестве общих смежных с ними вершин называется ц-подграфом графа Г.

Графы без 3-лап с несвязными /i-подграфами были изучены в 1994 году А.Е. Брауэром и М. Нуматой [7]. Теорема А.Е. Брауэра и М. Ну-маты [7] утверждает, что конечными графами без 3-лап, у которых все ^-подграфы несвязны, являются решетчатые т х n-графы и Nm~ графы. Пусть {0,1,...,3ш} множество вершин Агт-графа. Тогда вершины i,j, где i < j, смежны в Агт-графе тогда и только тогда, когда j 2(mod 3). Понятно, что 7Ут-графы не содержат 3-коклик.

В графе с несвязными /г-подграфами любой подграф, изоморфный 7^1,2, содержится в подграфе, изоморфном Ä'2,2, то есть в Сц. Такие графы мы будем называть (Äi,2> ^^-однородными графами.

Следовательно, граф, у которого все ¿¿-подграфы несвязны, является {K\t%, ^2,2)-оДНородным графом.

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

Теорема 1 Пусть связный граф Г содержит 3-коклику и не содержит 3-лап. Если любой подграф из Г, изоморфный Kip, содержится в подграфе, изоморфном К^^, то Г является кликовым расширением одного из следующих графов:

(1) решетчатый т х п-граф при т > 3, п > 3;

(2) треугольный граф Т(п) при п > 6;

(3) граф Шлефли.

Для удобства обозначим через Е класс графов, который состоит из тп х п-графов при m > 3, п > 3, треугольных графов Т(п) при п > 6 и графа Шлефли. В теореме 1 из работы [29] М. Нуматой была получена классификация реберно-регулярных графов, которые не содержат 3-лап и содержат 3-коклику. Оказалось, что если такой граф имеет

диаметр 2, то он является или графом из класса 5 или графом Рп при п > 2, который имеет 5п2 вершин.

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

Теорема 2 Пусть Г — кореберно-регулярный граф без 3-лап. Тогда Г является либо дополнительным графом к регулярному графу без треугольников, либо а-расширением (а > 1) одного из следующих графов:

(1) вполне несвязный граф с числом вершин тп {тф 2);

(2) решетчатый т х п-граф при тп > 3, п > 3;

(3) треугольный граф Т(т) при т > 6;

(4) граф Шлефли.

В теореме 2 работы [29] М. Нуматой получена классификация ре-берно-регулярных графов диаметра не мепее 3, которые пе содержат 3-лап и содержат 3-коклику. Он показал, что либо все /j-подграфы такого графа имеют не более 2 вершин, либо граф изоморфен графу икосаэдра.

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

Пусть х,у пара вершин графа Г, которые находятся на расстоянии 2 друг от друга. Обозначим число вершин ¿¿-подграфа для х, у через ц(х, у). Если все /i-подграфы графа Г имеют одинаковое число вершин, то есть р(х, у) = fi, то это число называется параметром ц графа Г. Понятно, что если граф имеет параметр ц, то /х не меньше 1. Если граф Г имеет параметр р., но его значение неизвестно, то мы говорим,

что Г имеет равномощные ¿¿-подграфы. Но определению сильного графа, любая пара несмежных вершин в нем имеет одно и то же число общих соседей. Это условие автоматически приводит к тому, что либо диаметр сильного графа равен 2 и он имеет равномощные /¿-подграфы, либо число общих соседей любой пары несмежных вершин в нем равно 0. Таким образом, условие равномощности /¿-подграфов значительно ослабляет соответствующее условие в определении сильного графа.

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

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

Теорема 3 Связный регулярный граф Тервиллигера без 3-лап является а-расширением одного из следующих графов:

(1) граф без 3-лап с ¡1 = 1,

(2) граф икосаэдра.

Примеры регулярных графов без 3-лап с ¡л — 1 имеются среди графов вершин и ребер полуправильных многогранников. Граф усеченного тетраэдра является ^-регулярным с р. — 1, но не реберно-регулярным графом. Граф кубооктаэдра, наоборот, является реберпо-регулярным графом без 3-лап, по не является ¿«-регулярным графом. В следующей теореме классифицированы связные ¿¡-регулярные графы без 3-лап [54].

Теорема 4 Связный ^-регулярный граф Г без '¿-лап либо является графом Тервиллигера, либо имеет диаметр 2.

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

В следующей теореме мы не предполагаем регулярности графа, и, таким образом, она завершает классификацию графов Тервиллигера без 3-лап [55]. Эта теорема расширяет теорему Тэйлора-Левингстона [37]. Через а-1 обозначим порожденный подграф, состоящий из вершины а и всех смежных с ней вершин. Через Гх обозначим подграф (~) о1.

аег

Теорема 5 Пусть Г — связный граф Тервиллигера без 3-лап. Тогда либо граф Г является а-расширением графа икосаэдра, либо подграф на множестве всех вершин с некликовыми окрестностями из Г — Г1 является пустым, кликой или а-расширением связного графа с ¡л = 1.

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

Теорема 6 Пусть Г — связный граф без 3-лап, содержащий 3-кокли-ку. Пусть также все ¡л-подграфы из Г имеют одинаковое число вершин. Тогда либо Г имеет диаметр больше двух и является графом из заключения теоремы 5, либо граф Г является а-расширением одного из следующих графов:

(1) решетчатый гп X п-граф при т > 3, п > 3;

(2) треугольный граф Т(т) при тп > 6;

(3) граф Шлефли.

Следующая теорема посвящена описанию графов без 3-лап с регулярными /i-подграфами одинаковой ненулевой валентности. Регулярный граф называется редуцированным, если для любой вершины а 6 Г множество {х 6 Г | а1 = з;1} состоит из единственной вершины а. В статье [27] A.A. Махнев перенес это понятие на класс всех графов. Произвольный граф Г называется редуцированным, если для любой вершины а € Г множество {х € Г | а1 С х1} состоит из единственной вершины а. Легко видеть, что в классе регулярных графов оба определения эквивалентны.

В [27] A.A. Махнев классифицировал редуцированные графы без 3-лап с регулярными р-подграфами валентности а, где а > 0. Мы докажем, что если Г является графом без 3-лап с регулярными р-иодграфами одинаковой валентности а, где а > 0, и для любой вершины а из Г множество {ж € Г | ах = хх} совпадает с {о}, то и множество {а; 6 Г | а1 С х1} состоит из единственной вершины о. Следующая теорема [43, 44] усиливает основной результат из [27].

Теорема 7 Пусть Г — связный граф, который не содержит 3-лап и содержит 3-коклику и выполнены следующие условия:

(а) все ц-подграфи из Г являются регулярными графами одинаковой валентности а для некоторого числа а > 0;

(б) для любой вершины а 6 Г множество {х € Г | а1 = состоит из единственной вершины а.

Тогда граф Г является треугольным графом Т{п) при п > б, графом икосаэдра или графом Шлефли.

В работе [19] М.Д. Хестенс и Д.Г. Хигман отметили другой момент, касающийся связи между теорией графов и теорией транзитивных групп подстановок. Пусть G — транзитивная группа подстановок на множестве Q. Тогда орбиты группы G на множестве Г2 х П называются орбиталами, а их число — рангом группы G. Каждый орбитал Д является либо симметричным, либо строго антисимметричным. В первом случае он определяет обыкновенный граф с множеством вершин П и множеством ребер Д. Во втором случае орбитал имеет симметричную ему пару Д' = (х, у) € А} и определяет ориентированный граф.

Известно, что группа G обладает симметричным орбиталом тогда и только тогда, когда ее порядок является четным числом [40].

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

Много работ посвящено изучению транзитивных групп подстановок без ограничений на их ранг и графов, которые определяются их орбиталами. В программном комплексе GAP [32] имеется специальная

инструкция Ес^еОгЬНСгарЬ, которая позволяет строить граф по орби-талу заданной транзитивной группы подстановок. При помощи этой инструкции автором найден пример дистанционно-транзитивного локально без 3-лап графа с несвязными окрестностями вершин. Этот граф является локально 4Х(/^12)-графом, то есть графом, любая окрестность вершины которого является объединением четырех решетчатых 4 х2-графов. Он получается из наименьшего орбитала группы Хигмена-Симса при представлении ее как транзитивной группы подстановок, действующей на классе центральных инволюций.

С другой стороны, интересен следующий, связанный с данным, вопрос. А именно, какими свойствами должен обладать граф, чтобы множество его ребер оказалось орбиталом для группы подстановок, действующей транзитивно на его вершинах (граф, изоморфный такому графу, мы назовем орбитальным)? Этот вопрос тесно связан с вопросом изучения групп автоморфизмов графов. В работах [14], [15] X. Ено-мото получил характеризацию графов Хэмминга как орбитальных графов для транзитивных групп подстановок с определенными ограничениями на их подстепени. Первая теорема третьей главы диссертации, опубликованная в [54], усиливает результат X. Еномого. Для ее формулировки нам понадобится определение отделимого графа. Граф Г назовем отделимым, если для любой вершины а из Г подграф Гг(а) содержит вершины Ь, с на расстоянии 2 в Гз(а) и ¿¿-подграф [Ь] П [с] для любой такой пары не пересекает [а].

Теорема 8 Пусть Г — связный вполне регулярный граф с параметрами (у,к,\,ц), ц> 1. Граф Г отделим тогда и только тогда, когда он является одним из следующих графов:

(1) граф Хемминга Н(п,тп) при т > 3,п > 2;

(2) треугольный граф Т(т) при т > б/

(3) граф Шлефли;

(4) граф икосаэдра.

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

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

Теорема 9 Пусть Г — связный граф, который удовлетворяет следующим условиям:

(1) окрестность любой вершины из Г не содержит 3-лап;

(2) Г содержит 3-лапу;

(3) все fi-подграфы из Г являются регулярными графами одинаковой валентности а для некоторого числа а > 0;

(4) для любой вершины а € Г множество {х £ Г | а1 = я1} состоит из единственной вершины а.

Тогда Г является локально G-графом, где G один из следующих графов:

(а) /3-расширение решетчатого т х п-графа при /3 = а/2 и т > 3, п > 3;

(б) треугольный граф Т(п) при п > 6; (с) граф Шлефли.

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

Пусть V является га-мерным векторным пространством над конечным полем F. Графом Грассмана для m-подпространств из V называется граф с множеством вершин, равным множеству всех подпространств размерности m из V, причем две вершины А, В смежны тогда и только тогда, когда dim(A П В) = m - 1. Если X — конечное множество, то графом Джонсона для m-подмножеств из X называется граф с множеством вершин, равным множеству (*) всех то-элементных подмножеств из X, причем две вершины а,Ь смежны тогда и только тогда, когда |оПЬ| = m — 1. Если множество X состоит из п элементов, то такой граф обозначим через J(n,m). Заметим, что граф J(n, 2) совпадает с треугольным графом Т(п). Пусть р — некоторое разбиение множества вершин графа Г на подмножества. Частным Г = Т/р для

графа Г по разбиению р называется граф на фактор-множестве по р множества вершин Г, в котором две вершины а, Ь смежны только, если а фЬ и граф Г содержит ребро, которое соединяет некоторую вершину из класса а с некоторой вершиной из класса Ь. Пусть п — 2т и р является разбиением множества вершин графа Джонсона ,7(2т, т) на двухэлементные классы, содержащие ш-элементное подмножество и его дополнение в X. Частным графа Джонсона называется граф J{2m,m)/р.

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

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

Теорема 10 Пусть Г — связный граф, который удовлетворяет условиям теоремы 9 и все /¿-подграфы из Г имеют диаметр 2. Тогда Г является одним из следующих графов:

(1) граф Грассмана;

(2) граф Джонсона или его частное;

(3) локально Т(п)-граф при п > 6;

(4) граф Госсета £7(1)-

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

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

Заканчивается третья глава описанием сильно регулярных графов с расщепляемыми окрестностями вершин. Пусть А, В, С — некоторые множества. Скажем, что А расщепляется В и С, если А содержится в Л и С и пересечение А П В П С пусто. Э. Шульт в работе [33] классифицировал сильно регулярные графы, в которых для любого ребра аЬ найдется такая вершина с из [а], что [а]' расщепляется [Ь] и [с]. Заметим, что в этом случае [а]' П Щ = [а]' П [с]' и [а]' П [с] = [а]' П [Ь]'. В частности, антиокрестность [а]' расщепляется антиокрестностями вершин бис. В следующей теореме [52] это условие накладывается на окрестности вершин, причем снято ограничение на расположение вершины с.

Теорема 11 Пусть Г — сильно регулярный граф, в котором для любого ребра аЬ найдется такая вершина с, что [а] расщепляется [6]' и [с]'. Тогда граф Г изоморфен одному из следующих графов:

(1) объединение п полных подграфов при п > 1;

(2) решетчатый п х п-граф при п > 1;

(3) пятиугольник;

(4) сильно регулярный граф с параметрами (13,6,2,3);

(5) граф Шрикханде.

В последней главе диссертации изучаются некоторых теоретико-

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

Некоторое множество X вершин из графа Г называется доминирующим, если любая вершина, не принадлежащая X, смежна не менее чем с одной вершиной из X. Минимальное число элементов в доминирующем множестве вершин графа Г обозначается через 7 (Г) и называется нижним параметром доминирования графа Г. Множество всех вершин из графа Г, смежных с вершиной х, вместе с {ж} называется замкнутой окрестностью вершины х. Вершина х из X неприводима относительно X в Г, если ее замкнутая окрестность содержит хотя бы одну вершину, не смежную ни с какой другой вершиной из X. Множество вершин X называется неприводимым в Г, если все его вершины неприводимы относительно X в Г. Заметим, что если I) — минимальное доминирующее множество некоторого графа Г, то оно неприводимо в Г. Более того, множество П является максимальным (относительно включения) неприводимым множеством графа Г. Этот факт послужил основой для введения и изучения понятия неприводимости. Среди всех максимальных неприводимых множеств выберем множество X, содержащее наименьшее число вершин. Число вершин в X назовем нижним параметром неприводимости для графа Г и обозначим через гг(Г).

Поскольку каждое минимальное доминирующее множество является максимальным неприводимым, то г'г(Г) < 7(Г) для любого графа Г. Неравенство 7(Г) < 2гг(Г) было получено независимо в [1] и [4]. Изучению параметров доминирования и неприводимости в разных классах графов было посвящено несколько работ (см., например, [1], [4],

7(Г) 3

[12], [16], [39]). В [12] П. Дамашке получил оценку -г™у < - для случая, когда граф Г является деревом. Этот результат был расширен

7(Г) 3

JT. Фолькманом в [39]. Он доказал неравенство . ,_. < - в случае,

гг(Г) 2

когда Г является блок-графом и в случае, когда граф Г содержит не

более двух циклов.

Так как по определению любой блок в блок-графе является кликой,

то точки сочленения внутри любого блока смежны между собой. Граф,

обладающий таким свойством, назовем кликово-сочлененпым графом.

7(Г) 3

В работе [41] показано, что оценка . < - справедлива для клас-

гг(1) 2

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

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

7(Г) 5 „

них справедливо неравенство .■ ■■ < -. Более точно мы доказываем

гг(Г) 3

следующие два утверждения [48].

Теорема 12 Пусть Г — связный кликово-сочлененный граф и X — максимальное неприводимое подмножество вершин из Г.

(1) Если все блоки графа. Г не содержат 3-лап, то существует доминирующее множество D для Г такое, что выполнено неравенство \D\J\X\ < 5/3.

(2) Если все блоки графа Г являются реберными графами графов без треугольников, то существует доминирующее множество D для Г такое, что выполнено неравенство ¡£>|/|Х| < 3/2.

Автор глубоко признателен профессору A.A. Махневу за дружеское участие, постоянное внимание и помощь в работе.

Литература

[1] Allan R. В., Laskar R. On domination and some related concepts in graph theory // Proc. 9th Southeast Conf. on Comb., Graph Theory and Сотр. Utilitas Math., Winnipeg. - 1978. - P. 43-56.

[2] Bannai E. Maximal subgroups of low rank of finite symmetric and alternative groups // J. Fac. Sci. Univ. Tokio. - 1972. - V. 18. - P. 475486.

[3] Blokhuis A., Brouwer A. E. On Locally 4-by-4 Grid Graphs // J. Graph Th. - 1989. - V.13, №2. - P. 229-244.

[4] Bollobas В., Cockayne E. J. Graph-theoretic parameters concerning domination, independence, and irredundance // J. Graph Th. - 1979.

- V. 3, № 3. - P. 241-249.

[5] Бурбаки H. Группы и алгебры Ли. - Москва, "Мир", 1972.

[6] Brouwer А. Е., Cohen А. М., Neumaier A. Distance-Regular Graphs.

- Springer-Verlag, 1989.

[7] Brouwer A. E., Numata M. A characterization of some graphs wich do not contain 3-claws // Discr. Math. - 1994. - V. 124. - P. 49-54.

[8] Buekenhout F., Hubaut X. Locally polar space and related rank 3 groups // J. Agebra. - 1977. - V. 45, № 2. - P. 391-434.

[9] Cameron P. J. Finite permutation groups and finite simple groups // Bull. London Math. Soc. - 1981. - V. 13. - P. 1-22.

[10] Chang L. C. The uniqueness and nonuniqueness of triangular association schemes // Sci. Record. - 1949. - V. 3. - P. 604-613.

[11] Chang L. C. Association schemes of partially balanced block designs with parameters v = 28, n-y = 12, no = 15 and j?n = 4 // Sci. Record.

- 1950. - V. 4. - P. 12-18.

[12] Damaschke P. Irredundance number versus domination number // Discrete Math. - 1991. - V. 89, № 1. - P. 101-104.

[13] Dunbar J. E., Haynes T. W. Domination in inflated graphs // Congr. Numer. - 1996. - V. 118. - P. 143-154.

[14] Enomoto H. Characterization of families of finite permutation groups by the subdegrees. I // J. Fac. Sci. Univ. Tokyo, sect. IA Math. - 1972.

- V.19. - P. 129-135.

[15] Enomoto H. Characterization of families of finite permutation groups by subdegrees. II // J. Fac. Sci. Univ. Tokyo. sect.IA Math. - 1973. -V.20. - P. 1-11.

[16] Favaron O. Irredundance in inflated graphs // J. Graph Theory. - 1998.

- V. 28, № 2. - P. 97-104.

[17] Hall J. I. Classifying copolar spaces and graphs // Quart. J. Math. -1982. - V.33. - P. 421-449.

[18] Hall J. I., Shult E. E. Locally cotriangular graphs // Geom. Dedic. -1985.-V. 18. - P. 113-159.

[19] Hestens M. D., Higman D. G. Hank 3 group and strongly regular graphs // SIAM-AMS Prosidings, Providence. - 1971. - V. 4. - P. 141159.

[20] Hoffman A. J. On the uniqueness of the triangular association scheme // Ann. Math. Stat. - 1960. - V. 31. - P. 492-497.

21] Hoffman A. J. On the exceptioal case in a characterization of the arcs of complete graphs // IBM J. Res. Develop. - 1960. - V. 4. - P. 487-496.

22] Hoffman A. J. On the line-graphs of the complete bipartite graph // Ann. Math. Stat. - 1964. - V. 35. - P. 883-885.

23] Hoffman A. J. On graphs whose least eigenvalue exeeds —1 — \/2 // Linear Algebra and Appl. - 1977. - V. 16. - P. 153-166.

24] Kantor W. M., Liebeck M. W. The rank three representations of the finite classical groups // Trans. Amer. Math. Soc. - 1982. - V. 271. -P. 1-71.

25] Liebeck M. W. Affine permutation groups of rank 3 // Proc. London Math. Soc. - 1987. - V. 54. - P. 477-516.

26] Liebeck M. W., Saxl J. The finite primitive permutation groups of rank three // Proc. London Math. Soc. - 1986. - V. 18. - P. 165-172.

27] Махнев А.А. Об одном классе графов без 3-лап // Матем. заметки. - 1998. - Т. 63, т. - С. 407-413.

28] Neumaier A. Characterization of a class of distance regular graphs // J. reine angew. Math. - 1985. - V. 387. - P. 182-192.

29] Numata M. On a characterization of a class the regular graphs of diameter 2 // Osaca J. Math. - 1974. - V. 11. - P. 389-400.

30] Numata M. A characterization of Grassmann and Johnson graphs // J. Comb. Theory (B). - 1990. - V. 48. - P. 178-190.

31] Moon J. On the line-graph of the complete bigraph // Ann. Math. Stat. - 1963. - V. 34. - P. 664-667.

[32] Schonert M. n jxp. GAP Group, Algorithms and Programming // Lehrstuhl D fr Matematik, RWTH Aachen. - 1995.

[33] Shult E. E. Characterization of Certain Classes of Graphs //J. Comb. Th. Ser. (B). - 1972. - V. 13. - P. 142-168.

[34] Seidel J. J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3 // Linear Algebra and Appl. - 1968. - V. 1. -P. 281-298.

[35] Shrickhande S. S. The uniqueness of the ¿2 association scheme // Ann. Math. Stat. - 1959. - V.30. - P. 781-798.

[36] Sims C. C. On graphs with rank 3 automorphism groups // Preprint. - 1970.

[37] Taylor D. E. Levingston R. Distance-regular graphs // Combinatorial mathematics, Proc. Canberra 1977, Lecture Notes in Math. 686 Springer, Berlin. - 1978. - P. 313-323.

[38] Terwilliger P. Distance-regular graphs with girth 3 or 4,1 // J. Combin. Th. (B). - 1985. - V.39. - P. 265-281.

[39] Volkmann L. The ratio of the irredundance and domination number of a graph // Discrete Math. - 1998. - V. 178, № 1-3. - P. 221-228.

[40] Wielandt H. Finite permutation groups. - Academic Press, 1964.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[41] Favaron О., Kabanov V., Puech J. The ratio of three domination parameters in some classes of claw-free graphs // J. of Comb. Math, and Comb. Сотр. - 1999. - V. 31. - P. 151-159.

[42] Кабанов В. В. Характеризация графа Шрикхапде, решетчатых и треугольных графов // Третья межд. конф. по алгебре памяти М.И. Каргаполова. Тез. докл. - 1993. - С. 138-139.

[43] Кабанов В. В. О локально A'i¿-свободных графах // Межд. конф. по теории групп памяти С.Н. Черникова. Тез. докл. - Пермь. -1997. - С. 29-30.

[44] Kabanov V. V. On graphs locally without 3-claws // III Krakow conf. on graph theory. Abstracts. - Krakow. 1997. - P. 22-23.

[45] Кабанов В. В. Характеризация треугольных и решетчатых графов // Сиб. мат. ж. - 1998. - Т. 39. - С. 1054-1059.

[46] Kabanov V. V. On graph characterization of finite vector spaces, Kurosh Algebraic Conference '98, Abstracts of Talks, МГУ им. M.B. Ломоносова, Москва. - 1998. - С. 63-64.

[47] Kabanov V. V. On graphs without KAM-DIMATA Series Fifth Czech-Slovak International Symposium on Combinatorics, Graphs Theory, Algorithms and Applications (Abstracts), Prague, July 6-11. - 1998. - P. 51.

[48] Kabanov V. V. The ratio of lower domination parameters in graphs with claw-free blocks // В сб. Paul Erdos and his mathematics. Budapest. - 1999. - P. 112-115.

[49] Кабанов В.В., Махнев A.A. Кореберно регулярные графы, в которых антиокрестности вершин кореберно регулярны // Третья межд. конф. по алгебре памяти М.И. Каргаполова. Тез. докл. -1993. - С. 138-139.

[50] Kabanov V.V., Makhnev A.A. On graphs without 3-claws // III Krakow conf. on graph theory. Abstracts. - 1997. - P. 24-25.

[51] Кабанов B.B., Махнев A.A. Графы без 3-лап с равномощными \i-подграфами // Межд. алгебр, конф. памяти Д.К. Фадцеева. Тез. докл. С.-Петербург. - 1997. - С. 208-209.

[52] Кабанов В. В., Махнев А. А. Сильно регулярные графы с расщепляемыми окрестностями // Комбинаторика и оптимизация. Межвузовский сб. научи, трудов. Вып. 1, Свердловск, 1991. - С. 10-15.

[53] Кабанов В. В., Махнев А. А. Кореберно регулярные графы без 3-лап // Мат. заметки. 1996. - Т. 60, № 4. - С. 495-503.

[54] Кабанов В. В., Махнев А. А. Об отделимых графах с некоторыми условиями регулярности // Мат. сборник. - 1996. - Т. 187, № 10. -С. 73-86.

[55] Кабанов В. В., Махнев А. А. Графы без 3-лап с равномощными ^-подграфами // Изв. Урал. гос. ун-та. (Математика и механика. Вып.1.). - 1998. - Т. 10. - С. 44-68.

1. Allan R. В., Laskar R. On domination and some related concepts in graph theory // Proc. 9th Southeast Conf. on Comb., Graph Theory and Сотр. Utilitas Math., Winnipeg. - 1978. - P. 43-56.

2. Bannai E. Maximal subgroups of low rank of finite symmetric and alternative groups //J. Fac. Sci. Univ. Tokio. 1972. -V. 18. - P. 475-486.

3. Blokhuis A., Brouwer A. E. On Locally 4-by-4 Grid Graphs // J. Graph Th. 1989. - Y.13, №2. - P. 229-244.

4. Bollobas В., Cockayne E. J. Graph-theoretic parameters concerning domination, independence, and irredundance //J. Graph Th. 1979. - V. 3, № 3. - P. 241-249.

5. Bose R. C., Dowling T. A. A generalization of Moore graphs of diameter two // J. Comb. Th. (B). 1971. - V. 11. - P. 213-226.

6. Bourbaki N. Groupes et algebres de Lie, Chapitre VI. -Hermann, 1975. Русский перевод: Бурбаки H. Группы и алгебры Ли. Москва, 1976.

7. Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. Springer-Verlag, 1989.

8. Brouwer A. E., Numata M. A characterization of some graphs wich do not contain 3-claws // Discr. Math. 1994. - V. 124. -P. 49-54.

9. Buekenhout F., Hubaut X. Locally polar space and related rank3 groups // J. Agebra. 1977. - V. 45, № 2. - P. 391-434.

10. Cameron P. J. Finite permutation groups and finite simple groups // Bull. London Math. Soc. -1981. V. 13. - P. 1-22.

11. Cameron P. J., Hughes D. R., Passini A. Extended generalized quadrangles // Geom. Dedic. 1990. - V. 35. - P. 193-228.

12. Chang L. C. The uniqueness and nonuniqueness of triangular association schemes // Sci. Record. 1949. - V. 3. - P. 604613.

13. Chang L. C. Association schemes of partially balanced block designs with parameters v = 28, «i = 12, no = 15 and p\x —4 // Sci. Record. 1950. - V. 4. - P. 12-18.

14. Cockayne E. J., Favaron 0., Mynhardt C. M., Puech J. Packing, perfect neighbourhood, irredundant and i?-annihilated sets in graphs // Austral, J. Combin.

15. Damaschke P. Irredundance number versus domination number // Discrete Math. 1991. - V. 89, № 1. - P. 101-104.

16. Dunbar J. E., Haynes T. W. Domination in inflated graphs // Congr. Numer. 1996. - V. 118. - P. 143-154.

17. Enomoto H. Characterization of families of finite permutation groups by the subdegrees. I // J. Fac. Sci. Univ. Tokyo, sect. IA Math. 1972. - V.19. - P. 129-135.

18. Enomoto H. Characterization of families of finite permutation groups by subdegrees. II // J. Fac. Sci. Univ. Tokyo. sect.IA Math. 1973. - V.20. - P. 1-11.

19. Favaron 0. Irredundance in inflated graphs //J. Graph Theory. 1998. - V. 28, № 2. - P. 97-104.

20. Favaron 0., Kabanov V., Puech J. The ratio of three domination parameters in some classes of claw-free graphs // J. of Comb. Math, and Comb. Comp. 1999. - Y. 31. - P. 151-159.

21. Favaron 0., Puech J. Irredundant and perfect neighborhood sets in graphs and claw-free graphs // Discr. Math. 1999.

22. Hall J. I. Classifying copolar spaces and graphs // Quart. J. Math. 1982. - V.33. - P. 421-449.

23. Hall J. I., Shult E. E. Locally cotriangular graphs // Geom. Dedic. 1985. - V.18. - P. 113-159.

24. Haynes T. W., Hedetniemi S. T., Slater P. J. Fundamentals of Domination in Graphs. Marcel Dekker, 1998.

25. Hedetniemi S. Т., Slater P. J. Line graphs of triangleless graphs and iterated clique graphs // Lecture Notes in Mathematics. -1972. V. 303. - P. 139-147.

26. Hestens M. D., Higman D. G. Rank 3 group and strongly regular graphs // SIAM-AMS Prosidings, Providence. 1971. - V. 4. -P. 141-159.

27. Hoffman A. J. On the uniqueness of the triangular association scheme // Ann. Math. Stat. I960. - V. 31. - P. 492-497.

28. Hoffman A. J. On the exceptioal case in a characterization „of the arcs of complete graphs // IBM J. Res. Develop. I960. -V. 4. - P. 487-496.

29. Hoffman A. J. On the line-graphs of the complete bipartite graph // Ann. Math. Stat. 1964. - V. 35. - P. 883-885.

30. Hoffman A. J. On graphs whose least eigenvalue exeeds — 1 — y/2 // Linear Algebra and Appl. 1977. - V. 16. - P. 153-166.

31. Кабанов В. В. Характеризация графа Шрикханде'решетчатых и треугольных графов // Третья межд. конф. по алгебре памяти М.И. Каргаполова. Тезисы докл. 1993. - С. 138139.

32. Кабанов В. В. -свободные графы с ¡л -подграфами неединичного радиуса // Проблемы теоретической и прикладной математики. ИММ УрО РАН. Тез. докл. конф №27. Екатеринбург. 1996. - С. 3-4.

33. Кабанов В. В. О локально -свободных графах // Межд. конф. по теории групп памяти С.Н. Черникова. Тез. докл. -Пермь. 1997. - С. 29-30.

34. Kabanov V. V. On graphs locally without 3-claws // III Krakow conf. on graph theory. Abstracts. Krakow. 1997. - P. 22-23.

35. Кабанов В. В. Характеризадия треугольных и решетчатых графов // Сиб. мат. ж. 1998. - Т. 39. - С. 1054-1059.

36. Кабанов В. В. Характеризация локально треугольных графов, Проблемы теоретической и прикладной математики // ИММ УрО РАН. Тезисы докл. 29-ой Per. мол. конф., 26-30 янв. 1998. С. 5-6.

37. Кабанов В. В. О графах без корон с регулярными р,-подграфами // Мат. заметки. 2000. (принята к печати).

38. Kabanov V. V. On graph characterization of finite vector spaces, Kurosh Algebraic Conference '98, Abstracts of Talks, МГУ им. M.B. Ломоносова, Москва. 1998. - С. 63-64.

39. Kabanov V. V. On graphs without A'M)3, KAM-DIMATA Series Fifth Czech-Slovak International Symposium on Combinatorics, Graphs Theory, Algorithms and Applications (Abstracts), Prague, July 6-11. 1998. - P. 51.

40. Кабанов В. В. Характеризация локально треугольных графов // Проблемы теоретической и прикладной математики.ИММ УрО РАН. Тезисы докл. 29-ой Per. мол. конф. 1998. - С. 5-6.

41. Kabanov V. V. The ratio of lower domination parameters in graphs with claw-free blocks // В сб. Paul Erdos and his mathematics. Budapest. 1999. - P. 112-115.

42. Кабанов В.В., Вакула И.А. Доминирование в раздуваниях графов радиуса 1 // Проблемы теоретической и прикладной математики. ИММ УрО РАН. Тезисы докл. 30-ой Per. мол. конф. 1999. - С. 3-4.

43. Кабанов В.В, Махнев А.А. Кореберно регулярные графы, в которых антиокрестности вершин кореберно регулярны Третья межд. конф. по алгебре памяти М.И. Каргаполова. Тезисы докл. 1993. - С. 138-139.

44. Kabanov V.V., Makhnev A.A. On graphs without 3-claws // III Krakow conf. on graph theory. Abstracts. 1997. - P. 24-25.

45. Кабанов В.В, Махнев А.А. Графы без 3-лап с равно-мощными /i-подграфами // Межд.алгебр.конф. памяти Д.К.Фаддеева. Тез.докл. С.-Петербург. 1997. - С. 208-209.

46. Кабанов В. В., Махнев А. А. Сильно регулярные графы с расщепляемыми окрестностями // Комбинаторика и оптимизация. Межвузовский сб. научн. трудов. Вып. 1, Свердловск, 1991. С. 10-15.

47. Кабанов В. В., Махнев А. А. Кореберно регулярные графы без 3-лап // Мат. заметки. 1996. Т. 60, № 4. - С. 495-503.

48. Кабанов В. В., Махнев А. А. Об отделимых графах с некоторыми условиями регулярности // Мат. сборник. 1996. -Т. 187, № 10. - С. 73-86.

49. Кабанов В. В., Махнев А. А. Графы без 3-лап с равномощ-ными /¿-подграфами // Изв. Урал. гос. ун-та. (Математика и механика. Вып.1.). 1998. - Т. 10. - С. 44-68.

50. Кабанов В.В., Онищенко Д.В. Доминирование в графах с блоками, не содержащими звезд // Проблемы теоретической и прикладной математики. ИММ УрО РАН. Тезисы докл. 30-ой Per. мол. конф. 1999, - С. 5-6.

51. Kantor W. М., Liebeck М. W. The rank three representations of the finite classical groups // Trans. Amer. Math. Soc. 1982.- V. 271. P. 1-71.Tb P

52. Liebeck M. W. Affine permutation groups of rank three // \JРге ft Cti^i'V cK^^nj i

53. Liebeck M. W., Saxl J. The finite primitive permutation groups of rank three / / • j 0&£ ,

54. Махнев А.А., Об одном классе графов без 3-лап // Матем. заметки. 1998. - Т. 63, №. - С. 407-413.

55. Махнев А.А., О некоторых комбинаторно симметричных графах // Акт. пробл. совр. мат. 1996. - Т. 2. - С. 104110.

56. Neumaier A. Characterization of a class of distance regular graphs //J. reine angew. Math. 1985. - V. 387. - P. 182192.

57. Numata M. On a characterization of a class the regular graphs of diameter 2 // Osaca J. Math. 1974. - V. 11. - P. 389-400.

58. Numata M. On the Graphical Characterization of the Projective Spaces over a Finite Field //J. Comb. Theory Ser. B. 1985. -V. 38. - P. 143-155.

59. Numata M. A characterization of Grassmann and Johnson graphs //J. Comb. Theory Ser. B. 1990. - V. 48. - P. 178-190.

60. Moon J. On the line-graph of the complete bigraph // Ann. Math. Stat. 1963. - V. 34. - P. 664-667.

61. Puech J., Lower domination parameters in inflated trees, Research Report 97-57, Math. Depart., Université Paris-Sud. -1999.

62. Ryjâcek Z. On a closure concept in claw-free graphs // J. Combin, Theory B. 1997. - V. 70, № 2. - P. 217-224.

63. Schonert M. together with Besche H. U., Breuer T., Celler F., Felsch V., Hulpke A., Mnich J., Pfeifïer G., Polis U., TheiSenH., Niemeier A. GAP Group, Algorithms and Programming // Lehrstuhl D fr Matematik, RWTH Aachen. 1995.

64. Seidel J. J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3 // Linear Algebra and Appl. 1968. - V. 1. - P. 281-298.

65. Shrickhande S. S. The uniqueness of the L2 association scheme // Ann. Math. Stat. 1959. - V.30. - P.781-798.

66. Shult E. E. Characterization of Certain Classes of Graphs //J. Comb. Th. Ser. (B). 1972. - V. 13. - P. 142-168.

67. Sims C. C. On graphs with rank 3 automorphism groups // Preprint. 1970.

68. Taylor D. E. Levingston R. Distance-regular graphs // Combinatorial mathematics, Proc. Canberra 1977, Lecture Notes in Math. 686 Springer, Berlin. 1978. - P. 313-323.

69. Terwilliger P. Distance-regular graphs with girth 3 or 4, I // J. Combin. Th. (B). 1985. - V.39. - P.265-281.

70. Volkmann L. The ratio of the irredundance and domination number of a graph // Discrete Math. 1998. - V. 178, № 13. - P. 221-228.

71. Wielandt H. Finite permutation groups. Academic Press, 1964.Zverovich V. E. The ratio of the irredimdance number and the domination number for block-cactus graphs, J. Graph Theory. 1998. - V. 29, №3. - P. 139-149.