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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи УДК 519.17

Шалагинов Леонид Викторович ¡^Л^/Цм—-

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

ДЕЗА

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

АВТОРЕФЕРАТ

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

2 3 ИЮН 2011

Екатеринбург - 2011

4851002

Работа выполнена на кафедре компьютерной безопасности и прикладной алгебры Челябинского государственного университета.

Научный руководитель: доктор физ.-мат. наук, профессор

Кабанов Владислав Владимирович

Официальные оппоненты: доктор физ.-мат. наук

Падучих Дмитрий Викторович

кандидат физ.-мат. наук, доцент Зюляркина Наталья Дмитриевна

Ведущая организация: Уральский государственный

университет им. А.М.Горького

Защита состоится 5 июля 2011 года в 15.30 на заседании специализированного совета Д 004.006,03 в Институте математики и механики УрО РАН по адресу. 620219, г. Екатеринбург, ул. С. Ковалевской, 16.

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

Автореферат разослан £> июня 2011 года

Ученый секретарь диссертационного совета, кандидат физ.-мат. наук

И.Н. Белоусов

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

Актуальность темы. Одним из важнейших объектов исследования алгебраической теории графов являются сильно регулярные графы, которые были введены в 1963г. Р.К.Боузом в связи с исследованиями схем отношений с двумя классами [3] и, позднее, Д.Г.Хигманом при исследовании групп подстановок ранга 3 [И].

В дальнейшем сильно регулярные графы рассматривались как самостоятельный объект исследований. Наиболее важный вопрос теории — "существует ли сильно регулярный граф с заданным набором параметров?" Другими словами, исследуются условия существования таких графов. Если ответ на предыдущий вопрос положительный, то возникает вопрос о количестве неизоморфных сильно регулярных графов с одинаковыми параметрами, т.е. вопрос характеризации графа по параметрам (возможно, с привлечением некоторых дополнительных ограничений). К решению этих задач привлекаются алгебраические (методы линейной алгебры, в частности, изучение спектров матриц смежности) и комбинаторные методы. Так, в работах 1959-60 годов Л.С.Чанг [5] и А.Дж.Хоффман [13,14] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п (за исключением п = 8). Реберный граф полного двудольного графа с долями порядка п (т.е. решетчатый граф Ь{п)) является сильно регулярным графом с параметрами (п2,2(п — 1), п —2,4). С.С.Шрикханде в [17] показал, что при п Ф 4 граф Ь(п) определяется этими параметрами. Это первые результаты по характеризации сильно регулярных графов, которые стали классическими. Также изучаются различные способы представления (построения) графов из блок-схем, конечных геометрий, действий некоторых конечных групп на множествах.

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

В 1994г. в работе [7] М.Деза, изучая некоторые геометрические объекты, рассмотрел класс регулярных графов, в которых число общих соседей любой пары различных вершин принимает одно из двух возможных значений, но не определяется смежностью этих вершин. Такие графы естественно рассматривать как обобщения сильно регулярных графов.

Базовые свойства таких графов изучены в работе [8] в 1998г., кро-

ме того, в этой же работе предложены некоторые конструкции графов Деза: из сильно регулярных графов с помощью инволюции (автоморфизма порядка 2), переставляющей только несмежные вершины, с помощью разностных множеств в группе, склеиванием классов в схемах отношений. Также перечислены все неизоморфные графы Деза не более чем на 13 вершинах.

Так же в работах Г.М.Ермаковой и В.В.Кабанова 2006-2009гг. [19-23] изучались графы Деза без 3-коклик. В работе Гуо, Ванга и Ли 2010г. [18] построение графов Деза из симплектических пространств.

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

Основные обозначения Далее мы рассматриваем конечные, неори-ентированые графы без петель и кратных ребер. Граф называется регулярным степени к, если каждая его вершина смежна с одним и тем же числом к вершин. Под подграфом графа (3 будем понимать порожденный подграф, то есть вершины подграфа смежны тогда и только тогда, когда они смежны в графе б. Если и — вершина графа С, то окрестностью а будем называть подграф индуцированный на множестве вершин смежных с а в графе (3. Множество вершин графа (7 будем также обозначать С7, если из контекста понятно о чем именно идет речь. Сильно регулярным графом с параметрами (и, к, А, /х) называется граф на V вершинах, регулярный степени любая пара смежных вершин имеет точно А общих соседей, а любая пара несмежных вершин имеет точно /х общих соседей.

Пусть Е — некоторое множество графов. Будем называть О локально Е-графом, если окрестность каждой его вершины изоморфна некоторому графу из множества причем для каждого графа Я из ^ существует вершина графа С?, окрестность которой изоморфна Н.

Графом Деза с параметрами (п, к, Ь, а), где Ь > а называется граф на п вершинах, регулярный степени к, и любая пара вершин имеет а или Ь общих соседей (независимо от смежности вершин). В зависимости от параметров графы Деза можно разделить на несколько классов: если число общих соседей двух вершин в графе Деза определяется их смежностью, то данный граф Деза является сильно регулярным. Если параметр а графа Деза равен 0, то граф Деза может иметь диаметр больше 2. Графы Деза диаметра 2, не являющиеся сильно регулярными, называют точными графами Деза. Графы Деза при а = 0 называются (0, А) графами.

Для этих графов известны некоторые конструкции и структурные свойства (см. Кэмерон и Дрейк [4], Хигман [12] и Мельдер [16]). Графы Деза диаметра больше 2 эквивалентны вполне регулярным графам с X — ц (см. Брауэр, Казн и Неймаер [2], Параграф 1.1, 1.9, и Теорема 1.13.2).

Далее приведем некоторые известные свойства графов Деза [8].

Утверждение 1. Пусть G = (V,E) — граф Деза с параметрами (п, к, Ь, а), где а ф Ь, для вершины и определим

a = \{weV : |[ш] П [и]| = а}\, fi = \{w € G : |[ю] П [u]| = Ь}|. Тогда а и Р не зависят от выбора вершины и, а = М"-1^-1) и р - "("-НИ,

Следствие 2. Для графа Деза с параметрами (п, к, 6, а), где а ф Ь, выполняются следующие ограничения.

1. Ъ - а делит b(n — 1) - к(к - 1),

2. Если а, РФ 0, то а(п - 1) < к(к - 1) < b(n - 1),

3. Если а ф 0, то п > 2к - а.

Можно определить графы Деза в терминах матриц. Пусть G — граф с матрицей смежности М. G — граф Деза с параметрами (п, к, Ь, а) тогда и только тогда, когда

М2 = а А + ЬВ + Ы

для некоторых (0,1)-матриц Л и В, таких что А + В + I = J (матрица из единиц). Заметим, что G — сильно регулярный граф тогда и только тогда, когда одна из матриц А, В равна М.

Наконец, заметим, что графы Деза могут быть ассоциированы с естес-венным обобщением (п, к, А)-симметричных блок схем. Действительно, матрица смежности М графа Деза может рассматриваться, как матрица инцидентности схемы, с точками соответствующими строкам М и блоками соответствующими столбцам М. Простейшей интерпретацией графов Деза является схема с п точками и п блоками, каждому блоку (точке) инцидетно точно к точек (блоков) и каждая пара различных блоков (точек) имеет а или Ь общих точек (блоков). Это дает пример частично симметричных схем (см. Хьюгес [15] и Цигич [6]). Они также связаны с А-конфигурациями (см. Гропп [9)).

Некоторые конструкции графов Деза

В работе [8] приводится несколько конструкций графов Деза.

Пусть Г — конечная группа и для непустого множества элементов DC Г определим D"1 — {d-1 : d е D} и, кроме того, определим DD~l

как мультимножество {(16! : б И} (т.е. в ГШ"1"1 могут быть повторяющиеся элементы). Для подмножеств А и В множества элементов Г и натуральных чисел а, Ь и к будем писать — а А + ЬВ + к{е},

если ОВ~х состоит из а копий каждого элемента из А, Ь копий каждого элемента из В и к копий единицы е группы Г.

Утверждение 3. Пусть О — подмножество элементов группы Г такое, что:

(1) |Г| = п и |Г>| = к;

(и) единица е группы Г не содержится в

(ш) И'1 = £>;

(Ь/) 3 такие натуральные о, Ь и к, что ИО'1 = аА 4- ЬВ 4- ке, где множества А, В и {е} образуют разбиение Г.

Пусть й — граф, вершинами которого являются все элементы группы Г, и вершины и и и смежны тогда и только тогда, когда ь~хи € £>. Тогда й — граф Деза с параметрами (п, к, Ь, а), где Ь > а.

Рассмотрим симметричную матрицу М', которая может быть получена из матрицы смежности М графа Деза <3 перестановкой строк. Тогда М2 — МТМ = М^М' = М'2. Следовательно М' также представляет граф Деза имеющий те же параметры и тех же детей Деза, что и граф С. Используя эту идею, можно получать точные графы Деза из сильно регулярных графов.

Утверждение 4. Пусть С — сильно регулярный граф с параметрами

матрицей смежности М. Пусть Р — перестановочная матрица размера V х и, тогда РМ — матрица смежности графа Деза С с параметрами (п, к, тах{А, тт{Л, ¡л}) тогда и только тогда, когда Р задает инволютивный автоморфизм графа £7, переставляющий только несмежные вершины. Кроме того С — точный граф Деза в том и только том случае, если Р ф I, А^Ои/х^О.

Также приводятся конструкции композиции и произведения графов, и конструкция склеивания классов в схемах отношений.

Цель диссертации. Целью данной работы является решение следующих задач.

1) Найти все инволюции треугольных, решетчатых и дополнительных к ним графов переставляющие только несмежные вершины.

2) Доказать, что точные графы Деза, полученные из треугольных, решетчатых и дополнительных к ним графов с помощью этих инволюций, однозначно определяются своими параметрами и строением окрестностей.

3) Найти и все неизоморфные точные графы Деза на 14, 15 и 16 вершинах.

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

Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.

1. Найдены все автоморфизмы треугольных и решетчатых графов, графов Чанга и Шрикханда, и дополнительных графов для каждого из них, удовлетворяющие условию теоремы 0.3.9. [24-27,29].

2. Доказано, что точные графы Деза, полученные из треугольных грат фов и дополнительных к ним графов, с помощью этих автоморфизмов, однозначно определяются по своим параметрам и строению окрестностей [25,27,29].

3. Доказано, что точные графы Деза, полученные из решетчатых графов с помощью симметрии относительно главной диагонали, однозначно определяются по своим параметрам и строению окрестностей [26].

4. Доказано, что точные графы Деза, полученные из дополнения к решетке с помощью автоморфизма, перестановляющего пару строк, однозначно определяются по своим параметрам и строению окрестностей [27].

5. Найдены все неизоморфные точные графы Деза на 14, 15 и 16 вершинах. Для каждого графа найдена конструкция [28,30].

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

Апробация работы. Основные результаты диссертации докладывались на 40-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики», 41-й Всероссийской молодежной школе-конференции «Проблемы теоретической и прикладной математики», 42-й Всероссийской молодежной школе-конференции «Современные проблемы математики»ИММ УрО РАН (Екатеринбург, 2009—2011 гг.),

на алгебраическом семинаре ИММ УрО РАН, на алгебраическом семинаре ЮУрГУ.

Публикации. Основные результаты диссертации опубликованы в работах [24-30]. Работа [26] выполнена в нераздельном соавторстве с В.В.Кабановым. Работы [28] и [30] выполнены в нераздельном соавторстве с С.В.Горяиновым. Во всех работах основными являлись исследования диссертанта.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка цитируемой литературы, содержащего 34 наименований.

РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

Следующие результаты являются основными в первой главе.

Предложение 1. Для решетчатого графа Ь(п) при четном п существует, с точностью до нумерации вершин, ровно два автоморфизма, удовлетворяющих условию утверждения 4. Автоморфизм типа I оставляет на месте п попарно несмежных точек и при подходящей нумерации вершин соответствует симметрии решетки относительно главной диагонали. Автоморфизм типа II не имеет неподвижных точек и при подходящей нумерации вершин соответствует центральной симметрии решетки (суперпозиция симметрий относительно главной и побочной диагоналей решетки). При нечетном п существует только автоморфизм типа I.

Обозначим автоморфизм типа I — Ф^ а автоморфизм типа II — Фг. Соответствующие графы Деза будем обозначать Ф1 (Ь(п)) и ФгЩп)). Понятно, что эти графы не изоморфны.

Лемма 1.1. Ф1 (1(п)) — локально Е-граф Деза с параметрами (п2,2(п — 1 ),п - 2,2), где Р = (рис. 1.). Ги Р2 - графы на

2[тг — 1) вершинах, причем вершины, неподвижные под действием автоморфизма, имеют окрестность изоморфную а все остальные —

Я-

Граф — это полный двудольный граф, с долями порядка п — 1, с удаленным паросочетанием. Граф £2 — это две (п—2)-лапы, причем существует биекция вершин степени 1 одной лапы на вершины степени 1 другой лапы.

Теорема 1. Локально Р-граф Деза с параметрами (п2,2(п— 1), п-2,2), где Р —из леммы 1.1. изоморфен графу Ф1 {Ь(п)).

Fj п = 5

Fz и = 5

Лемма 1.2. Фз(Ь(п)) — локально F-граф Деза с параметрами (п2,2(п — 1),п — 2,2), 0<?е {Р3} (рис. 2.).

F3 п = 6 . 2.

Во второй главе изучаются автоморфизмы треугольных графов и точные графы Деза, полученные из треугольных графов с помощью этих автоморфизмов.

Следующие результаты являются основными во второй главе.

Предложение 2. При четном п существует, с точностью до нумерации вершин, единственный автоморфизм треугольного графа Т(п),

удовлетворяющий условию утверждения 4. Он оставляет на месте п/2 попарно несмежных вершин и переставляет местами каждые два полных подграфа, имеющих своей общей вершиной неподвижную, под действием этого автоморфизма, вершину. Обозначим этот автоморфизм Ф.

При нечетном п подходящих автоморфизмов не существует.

Лемма 2. Ф(Т(п)) — локально Р-граф Деза с параметрами ( 2 ,2(п — 2),п — 2,4), где — {^,/<2} {рис. 3.), причем первому графу изоморфны окрестности неподвижных, под действием автоморфизма, вершин, а второму — сдвигаемых.

п = 8 /2 п = 8

. 3.

Замечание. Граф первого изоморфного типа состоит из двух множеств ребер, каждая вершина первого множества смежна со всеми вершинами второго, кроме одной (противоположной ей на рис.). Граф второго изоморфного типа имеет четыре особые вершины степени п — 2 (два ребра) и также два множества ребер, каждая вершина первого множества смежна с одной вершиной второго (противоположной ей на рисунке) и с двумя особыми вершинами.

Теорема 2. Локально Р-граф Деза с параметрами ( 2 ,2(п — 2),п — 2,4), где Р из леммы 2., изоморфен Ф(Т(п)).

Из леммы 2. и теоремы 2. вытекает необходимое и достаточное условие того, что граф Деза изоморфен графу Ф(Т(п)).

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

Следующие результаты являются основными в третьей главе.

Предложение 3. Для Ь(п) существует, с точностью до нумерации вершин, [п/2] (целая часть) автоморфизмов удовлетворяющих условию утверждения 4. Обозначим Ф* — автоморфизм переставляющий г пар строк(1-ю со 2-й, 3-ю с 4-й, и т.д.)

Лемма 3. Граф Фх(Ь(п)), является графом Деза с параметрами (п2, (п — I)2, (п — 1 ){п — 2), (п — 2)2), и имеет следующие окрестности вершин:

• Окрестности неподвижных вершин изоморфны графу, полученному из Ь(п — 1) вершине заменой двух строк кликами, причем вершины клик несмежны. Эта окрестность является регулярным графом. Обозначим его Р\,

• окрестности сдвигаемых вершин изоморфны графу, полученному из Ь{п — 1) заменой одной строки кликой. Обозначим этот граф

Пусть теперь Р =

Теорема 3. Локально Р-граф Деза с параметрами (п2, (тг— I)2, (п —1)(п—2), (п—2)2), где Р из леммы 3., изоморфен графу, ФГ(£(п)).

Предложение 4. Для графа Т(п) существует единственный, с точностью до нумерации вершин, автоморфизм удовлетворяющий условию утверждения 4. Он переставляет максимальные коклики в антиокрестности одной фиксированной вершины графа.

Лемма 4. Граф Ф(Т(п)), является графом Деза с параметрами ( 2 > "г2 ' "г3 ' "г4 )> и имеет следующие окрестности вершин.

• Окрестность фиксированной вершины изоморфна Т(п — 2). Обозначим этот граф Р\,

• окрестности вершин в антиокрестности фиксированной вершины изоморфны графу, полученному из Т(п — 3) "добавлением" клики Кп-з- Обозначим этот граф

• окрестности остальных вершин изоморфны графу, полученному из Т(п - 4) "добавлением" двух клик Кп-3. Обозначим этот граф Fз.

Пусть теперь Р = Р2, ^з}.

Теорема 4. Локально Р-граф Деза с параметрами ( 2 1 П~г 1 "г3 > )» Р из леммы 4., изоморфен графу Ф(Т(п)).

В четвертой главе находятся все точные графы Деза на 14, 15 и 16 вершинах. Для каждого графа находится конструкция.

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

Таблица. Точные графы Деза на 14, 15 и 16 вершинах

Параметры Количество неизоморфных точных графов Деза Конструкции

(14,9,6,4) 1 с помощью разностных множеств в группе Du

(15,6,3,1) 1 с помощью инволютивного автоморфизма графа Т(6)

(16,5,2,1) 1 с помощью разностных множеств в группе QDi6

(16,7,4,2) 2 с помощью разностных множеств в группе С4 х С4

(16,8,4,2) 1 с помощью разностных множеств в группе Cíe

(16,9,6,4) 2 с помощью инволютивного автоморфизма графа ¿(4)

(16,9,8,2) 1 A^/G], с помощью разностных множеств в группе С16

(16,11,8,6) 1 с помощью разностных множеств в группе С4 х С4

(16,12,10,8) 1 с помощью разностных множеств в группе Cig

(16,13,12,10) 1 Ki [2^2]) с помощью раз-

• ностных множеств в груп-

пе С16

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

Список цитируемой литературы

[1] Bannai, Е. Algebraic combinatorics I: Association schemes / E.Bannai, T.Ito // Benjamin-Cummings Lecture Note Series 58, Benjamin Cum-mings, London, 1984.

[2] Brouwer, A.E. Distance-regular graphs / A.E. Brouwer, A.M. Cohen, A. Neumaier// Berlin etc: Springer-Verlag, 1989.

[3] Bose, R.C. Strongly regular graphs, partial geometries and partially balanced designs // Pacific J. Math., 1963, V.13, P.389-419.

[4] Cameron, P. J. Partial lambda - geometries of small nexus / P.J. Cameron, D.F. Drake // Combinatorial mathematics, optimal designs and their applications, J. Srivastava (Editors), Fort Collins, 1978, Ann Discrete Math 6, NorthHolland, 1980.

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

[6] Cigic, V. Some new partial symmetric designs derived from symmetric designs with 1 > 1 // Glasnik Matematicki, 1996, V.31(51), P.47-51.

[7] Deza, A. The ridge graph of the metric polytope and some relatives / A. Deza, M. Deza // NATO Adv. Sci. Inst. Ser. С Math. Phys. Sci., 440, Kluwer Acad. Publ., Dordrecht, 1994.

[8] Erickson, M. Deza graphs: a generalization of strongly regular graphs / M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter // J. Comb. Designs, 1999, V.7, P.359-405.

[9] Gropp, H. On symmetries patial configurations // Discrete Math, 1994, V.125, P.201-209.

[10] Harary, F. Graph theory // Addison-Wesley, Reading, 1969, P.36-37.

[11] Higman, D. G. Finite permutations group of rank 3 // Math. Z., 1964, V.86, P. 145-156.

[12] Higman, D.G. Strongly regular designs and coherent configurations of type 3 23 // European J. Combin., 1988, V.9, P.411-422.

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

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

[15] Hughes, D. R. On designs // Geometries and designs, Lecture Notes in Math., 1981, V. 893, P.43-67.

[16] Mulder, H. M. The interval function of a graph // PhD Thesis, Free University Amsterdam, 1980, MCTractl32, CWI, Amsterdam, 1980.

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

[18] Guo, J. Deza graphs based on symplectic spaces / J. Guo, K. Wang, F. Li // European Journal of Combinatorics, 2010, V.31, P.1969-1980.

[19] Ермакова, P.M. Две задачи алгебраической теории графов // Автореферат диссертации на соискание ученой стетпени кандидата ф.-м. н., УрО РАН, Екатеринбург, 2009.

[20] Ермакова, Г.М. Графы Деза, которые являются кликовыми расширениями сильно регулярных графов/ Г.М. Ермакова, В.В. Кабанов // Проблемы теоретической и прикладной математики: труды 37-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2006, С.27-29.

[21] Ермакова, Г.М. Точные графы Деза без 3-коклик с большим ц / Г.М. Ермакова, В.В. Кабанов // Проблемы теоретической и прикладной математики: труды 38-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2007, С.31-34.

[22] Ермакова, Г.М. Точные графы Деза, которые являются соединением сильно регулярных графов или точных графов Деза / Г.М. Ермакова, В.В. Кабанов // Проблемы теоретической и прикладной

математики: труды 39-й Всероссийской моложежной конференции, Екатеринбург: УрО РАН, 2008, С.11-15.

[23] Ермакова, Г.М. Некоторые свойства точных графов Деза без 3-коклик с /х = Ь // Проблемы теоретической и прикладной математики: труды 40-й Всероссийской моложежной школы-конференции, Екатеринбург: УрО РАН, 2009, С. 19-27.

Работы автора по теме диссертации

[24] Шалагинов, Л.В. Исследование графов Деза с параметрами решетчатых графов // Труды 40-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики Екатеринбург, УрО РАН, 2009, С.70-71.

[25] Шалагинов, Л.В. О графах Деза с параметрами треугольных графов // Тезисы 41-й Всероссийской молодежной школы-конференции "Проблемы теоретической и прикладной математики Екатеринбург, УрО РАН, 2010, С.92-94.

[26] Шалагинов, Л.В. О графах Деза с параметрами решетчатых графов/ В.В. Кабанов, Л.В. Шалагинов // Труды ИММ УрО РАН, Екатеринбург, 2010, Т.З, С.117-120.

[27] Шалагинов, Л.В. О графах Деза с параметрами графов, дополнительных к решетчатым и треугольным графам // Тезисы 42-й Всероссийской молодежной школы-конференции "Современные проблемы математики Екатеринбург, УрО РАН, 2011, С.250-252.

[28] Шалагинов, Л.В. О графах Деза на 14, 15 и 16 верщинах / С.В. Горяинов, Л.В. Шалагинов // Тезисы 42-й Всероссийской молодежной школы-конференции "Современные проблемы математики Екатеринбург, УрО РАН, 2011, С.250-252.

[29] Шалагинов, Л.В. О графах Деза с параметрами треугольных графов // Труды ИММ УрО РАН, Екатеринбург, 2011, Т.1, С.294-298.

[30] Шалагинов, Л.В. О графах Деза на 14, 15' и 16 верщинах / С.В. Горяинов, Л.В. Шалагинов // Сибирские электронные математические известия, 2011, Т.8, С.105-115.

1С

Шалагинов Леонид Викторович

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

Специальность 01.01.06. — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

на соискание ученой степени кандидата физико-математических наук

Подписано в печать 01.Об.П. Формат 60*84 1/16. Бумага офсетная. Печать офсетная Усл. печ. л. 1,0. Уч.-изд. л. 1,1 Тираж 100 экз. Заказ № 52 Бесплатно

Челябинский государственный университет 454001 Челябинск, ул. Братьев Кашириных, 129

Издательство Челябинского государственного университета _454021 Челябинск ул. Молодогвардейцев, 576_

1. Bannai E. Algebraic combinatorics 1. Association schemes/ Bannai E. Ito T. //Benjamin-Cummings Lecture Note Series 58, Benjamin/Cummings, London, 1984.

2. Brouwer A.E. Distance-regular graphs/ A.E. Brouwer, A.M. Cohen, A. Neu-maier// Berlin etc: Springer-Verlag, 1989, P. 495.

3. Bose R.C. Strongly regular graphs, partial geometries and partially balanced designs// Pacific J. Math., 1963, V.13, P.389-419.

4. Cameron P. J. Partial lambda geometries of small nexus/Cameron P. J. and Drake D. F// Combinatorial mathematics, optimal designs and their applications, J. Srivastava (Editors), Fort Collins, 1978, Ann Discrete Math 6, NorthHolland, 1980.

5. Chang L.C. The uniqueness and nonuniqueness of triangular association schemes// Sci. Record, 1959, Vol.3, P.604-613.

6. Chang L.C. Association schemes of partially balanced block designs with parameters v = 28,72! = 12, no = 15 and Pn = 4// Sci. Record, 1950, Vol.4, P.12-18.

7. Cigic V. Some new partial symmetric designs derived from symmetric designs with 1 > 1// Glasnik Matematicki, 1996, V.31(51), P.47-51.

8. Van Dam E. R. Graphs with few eigenvalues An interplay between combinatorics and algebra// PhDthesis, Tilburg University, Tilburg, 1996.

9. Deza A. The ridge graph of the metric polytope and some relatives / Deza A. and Deza M// NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 440, Kluwer Acad. Publ., Dordrecht, 1994.

10. Erickson M. Deza graphs: a generalization of strongly regular graphs /Er-ickson M., Fernando S., Haemers W.H., Hardy D. and Hemmeter J// J. Comb. Designs, 1999, V.7, P.359-405.

11. Gropp H. On symmetries patial configurations// Discrete Math, 1994, V.125, P.201-209.

12. Harary F. Graph theory// Addison-Wesley, Reading, 1969, P.36—37.

13. Higman D. G. Finite permutations group of rank 3// Math. Z., 1964, V.86, P.145-156.

14. Higman D.G. Strongly regular designs and coherent configurations of type3 2 3European J. Combin., 1988, V.9, P.411-422.

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

16. Hoffman A.J. On the uniqueness of the triangular association scheme// Ann. Math. Stat., 1960, Vol.31, P.492-497.

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

18. Hughes D. R. On designs// Geometries and designs, Lecture Notes in Math., 1981, V. 893, P.43-67.

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

20. Mulder H. M. The interval function of a graph// PhD Thesis, Free University Amsterdam, 1980, MCTYactl32, CWI, Amsterdam, 1980.

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

22. Guo J. Deza graphs based on symplectic spaces/ Guo J., Wang K. and Li F.// European Journal of Combinatorics, 2010, V.31, P.1969-1980.

23. Ермакова Г. M. Две задачи алгебраической теории графов// Автореферат диссертации на соискание ученой стетпени кандидата ф.-м. н., УрО РАН, Екатеринбург, 2009.

24. Ермакова Г. М. Точные графы Деза без 3-ко клик с большим ц,/ Ермакова Г. М., Кабанов В. В// Проблемы теоретической и прикладной математики: труды 38-й региональной моложежной конференции, Екатеринбург: УрО РАН, 2007, С. 31-34.

25. Ермакова Г. М. Некоторые свойства точных графов Деза без 3-коклик с ¡1 = Ь// Проблемы теоретической и прикладной математики: труды 40-й Всероссийской моложежной школы-конференции, Екатеринбург: УрО РАН, 2009, С. 19-27.

26. Шалагинов JI.B. Исследование графов Деза с параметрами решетчатых графов.// Труды 40-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики Екатеринбург, УрО РАН, 2009, стр.70-71.

27. Шалагинов JI.B. О графах Деза с параметрами треугольных графов.// Тезисы 41-й Всероссийской молодежной школы-конференции "Проблемы теоретической и прикладной математики Екатеринбург, УрО РАН,2010, стр.92-94.

28. Кабанов В.В. О графах Деза с параметрами решетчатых графов/В.В.Кабанов, Л.В.Шалагинов// Труды МММ УрО РАН, Екатеринбург, 2010, Т.З, С.117-120.

29. Шалагинов Л.В. О графах Деза с параметрами графов, дополнительных к решетчатым и треугольным графам.// Тезисы 42-й Всероссийской молодежной школы-конференции "Современные проблемы математики Екатеринбург, УрО РАН, 2011, стр.250-252.

30. Шалагинов Л.В. О графах Деза на 14, 15 и 16 верщинах/ Горяинов C.B., Шалагинов Л.В// Тезисы 42-й Всероссийской молодежной школы-конференции "Современные проблемы математики Екатеринбург, УрО РАН, 2011, С.250-252.

31. Шалагинов Л.В. О графах Деза с параметрами треугольных графов// Труды ИММ УрО РАН, Екатеринбург, 2011, Т.1, С.294-298.

32. Шалагинов Л.В. О графах Деза на 14, 15 и 16 верщинах/ Горяинов C.B., Шалагинов Л.В// Сибирские электронные математические известия,2011, Т.8, С.105-115.