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

003474422

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

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

^ъос&СС/А—

ЕРМАКОВА Галина Михайловна

ДВЕ ЗАДАЧИ АЛГЕБРАИЧЕСКОЙ ТЕОРИИ ГРАФОВ

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

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

Екатеринбург — 2009

003474422

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

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

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

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

АЛЕЕВ Рифхат Жалялович

Ведущая организация: Институт математики СО РАН

Защита состоится 30 июня 2009 года в 15 час. 30 мин. на заседании специализированного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620219, г. Екатеринбург, ул. С. Ковалевской. 16.

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

Автореферат разослан А.9 мая 2009 года

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

кандидат физико-математических наук РАСИН Олег Вениаминович

доктор физ.-мат. наук

В.И. Зенков

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

Актуальность темы.

Пусть G — транзитивная группа подстановок на конечном множестве X. Если порядок группы четен, то стабилизатор в G точки хбХ имеет симметричную орбиту Д (х) на X отличную от {я}. Тогда по группе G можно построить граф Г с множеством вершин X, и две вершины х, у смежны в Г тогда и только тогда, когда у g A(i).

Изучение графов, полученных таким образом, является важной задачей алгебраической теории графов. Если в качестве группы G рассмотреть симметрическую группу подстановок Sn на п символах, а в качестве множества X — множество всех транспозиций пз Sn и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф Т{п). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами ("^''^,2(71— 2), п — 2,4). Кроме того, он не содержит порожденных /¡^¿-подграфов. В работах 1959-60 гг. Л. Чанг [8] и А. Хоффман [11], [12] независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [7].

Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберный граф Ь(Кт-п) полного двудольного графа ifm,„ с долями порядка man является кореберно регулярным графом с параметрами (тп,т + п — 2,2). Граф Ь(А"т,п) называют m х га-решеткой, и при m = п этот граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2,2). С. Шрикханде |15| и А. Хоффман |13| показали, что граф, имеющий параметры mxn-решетки, является либо шхп-решеткой, либо графом Шрикханде, при п = 4. Все вышеперечисленные графы имеют наименьшее собственное значение —2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж. Зейделем [14], который определил все сильно регулярные графы с наименьшим собственным значением —2. В частности, Дж. Зейдель показал, что кроме треугольных графов Т(п) и п х n-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

Полное описание графов без 3-лап с несвязными д-подграфами было полу-чепо А. Брауэром и М. Нуматой [6]. Они показали, что если граф связный конечный и содержит 3-коклику, то он является тп х n-решеткой. Этот результат был обобщен В.В. Кабановым в [4]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его д-подграф имеет радиус: больше 1, тогда и только тогда, когда он является либо треугольным графом Т(п) с п > б, либо m. х га-решеткой с л > 3 и m > 3, либо графом Шлефли. Граф Шлефли — это единственный сильно регулярный граф с параметрами (27,16,10,8). В работах И.А. Вакулы и В.В. Кабанова [1], [2] описаны

связные графы без 3-лап с некликовыми /i-подграфами.

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

В 1994 г. А. Деза и М. Деза [9] привели пример точного графа Деза с параметрами (40,15, б, 4).

М. Эриксон, С. Фернандо, У.Х. Хаймсрс, В. Харди и Дж. Хсмметр [10] описали все точные графы Доза с числом вершин не более 13. A.A. Махневым [5] рассматривались графы Деза, которые являются кликовыми или кокликовыми расширениями сильно регулярных графов.

В диссертации рассматриваются только конечные неориентированные графы без петель и кратных, ребер. Далее всюду подграф графа Г будет означать индуцированный подграф графа Г. Для вершины а графа Г через [а] обозначим подграф на множестве всех вершин, смежных с а. Этот подграф называется окрестностью вершины а в графе Г. Через fc„ обозначим валентность вершины а в Г, т. е. число вершин в [а]. Граф Г называется регулярным валентности к, если ка = к для любой вершины а из Г. Для ребра ас графа Г через Хас обозначим число вершин в подграфе [а]п[с]. Граф Г называется реберно регулярным с параметрами (V, к, А), если Г — регулярный граф на v вершинах валентности к, в котором каждое ребро лежит в А треугольниках, т. е. Хас = А для любого ребра ас графа Г. Подграф [а] П [6] назовем /i-подграфом, если вершины а, Ь находятся на расстоянии 2 друг от друга в графе Г и будем обозначать его через М[а,Ь). Граф Г на v вершинах валентности к называется [i-регулярным с параметрами (v,k,ß), если все его д-подграфы имеют ß вершин. Если такой граф имеет диаметр 2, то он называется кореберно регулярным. Если реберно регулярный граф с параметрами (v,k, А) является /¿-регулярным графом, то он называется вполне регулярным графом с параметрами (v,k,X,ß). Вполне регулярный граф диаметра 2 называется сильно регулярным.

Полный граф назовем кликой, а вполне несвязный граф — кокликой. Клика (коклика) порядка п называется п-кликой (п-кокликой).

Пусть п — натуральное число. Под п-расширением графа Г будем понимать граф Г', полученный заменой каждой вершины о из Г на п-клику (а), причем вершины из (а) и (6) смежны в Г' тогда и только тогда, когда а и 6 смежны в Г.

Граф Г на v вершинах назовем графом Деза с параметрами (v, k, Ь, а), если для любых вершин « и ш из Г

I г 1 _ г ,, (а или Ь, если u^w.

МПЬ =< , г

1 к, если и — tu,

где v, к,Ь,а — целые числа такие, что 0 < а <b <к < v.

Очевидно, класс графов Деза содержит класс сильно регулярных графов.

Графы Деза, но являющиеся сильно регулярными и имеющие диаметр 2, называются точными графами Деза.

Рассмотрим графы = (У\,Е\) и Гз = (^,£2), где У\ и Уг — непересекающиеся множества вершин, а и Е2 — множества ребер графов Г1 и Гг соответственно.

Обпгс/иисиисм тяких графов Г! и Гг назовем грас|) ПиГг = (Ци^г.^иВг)-

Суммой графов Г^ и Г2 назовем граф Г[ + Г2 = (Ц и Е1 и Е2 и £3), где Е3 = {{х,у) \хеУиУеУ2].

Дополнение Г графа Г имеет в качестве множества вершин множество вершин графа Г и две вершины в Г смежны тогда и только тогда, когда они не смежны в Г.

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

1) Изучить связные графы без порожденных Л^з-подграфов, содержащих 3-коклику, в которых для любой пары вершин и и I1, находящихся на расстоянии 2 друг от друга, подграф М(и, с) = [и] П [г>] содержит ц вершин, если он не является кликой, н содержит V вершин в противном случае.

2) Исследовать точные графы Деза без 3-коклик с ¡1 = Ь.

Методы исследования. Основными методами исследования являются методы алгебраической теории графов.

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

1. Классифицированы связные графы без порожденных /(¡.з-подграфов, содержащих З-коклнку, в которых для любой пары вершин и и и, находящихся на расстоянии 2 друг от друга, подграф М(и, у) = [и] П [и] содержит ц вершин, если он не является кликой, и содержит и вершин в противном случае.

2. Найдено соотношение для параметров а и Ь точного графа Деза без 3-коклик с 1-1 = Ь.

3. Описаны некоторые свойства и в отдельных случаях получено полное описание точных графов Деза без З-коклнк с /х = Ь.

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

Апробация работы. Основные результаты работы докладывались па 35-й, 37-40-ой Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004, 2006-2009 гг.), Международной школе-конференции по теории групп (Нальчик, 2007 г.).

Результаты работы докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [16]-[21]. Работы [16]-[19] и [21] выполнены в нераздельном соавторстве с В.В. Кабановым.

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

Результаты диссертации. Во введении обсуждается история вопроса, даются определения и формулируются основные результаты.

В главе I рассматриваются связные графы без порожденных А^з-подграфов. В.В. Кабановым, A.A. Махиевым в работе [3] были классифицированы такие графы в предположении, что все /i-подграфы равномощны.

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

Теорема 1 Пусть Г свя.чиый граф без порожденных К\$-подграфоа, содержащий Ъ-коклику. Пусть т.акже в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф М(и, v) = [и] П [г;] содержит, /t вершин, если он не является кликой, и содержит и вершин в противном случае. Если и > то все подграфы М(и, v) в Г одного типа, т. е. все кликовые или все неклико-вые.

Из этой теоремы и результата полученного В.В. Кабановым и A.A. Махневым в [3] имеем

Следствие. Пусть Г — связный граф без порожденных К13-подграфов, содержащий 3-коклику. Пусть также в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф М(и, v) = [и] П [у] содержит fj. вершин, если он не является кликой, и содержит. i> вершин в противном случае, где v > fi. Тогда

(1) либо граф Г является а-расширением графа икосаэдра, либо в Г - Г1 подграф) на множестве всех вершин с, некликовыми окрестностями является пустым графом, кликой или а-расширением связного графа с ¡.i = 1;

(2) граф Г является а-расширением одного из следующих графов:

(г) т х п-решет.ки. где т>3ип>3: (п) треугольного графа Т(т),т > 6; (ш) грхфа Шлефли.

Во второй главе работы рассматриваются точные графы Деза без 3-коклик с fi = Ь. Описаны точные графы Деза, которые являются суммой сильно регулярных графов или точных графов Деза, и точные графы Деза, которые являются кликовымн расширениями сильно регулярных графов. Пусть Г — точный граф Деза без 3-коклик с ß = Ь и вершина ,т — произвольная вершина графа Г. Будем называть вершину и е [j] графа Г вершиной "типа о" для вершины х, если |[х] П [и]| = а, а вершину w е [,т] — вершиной "типа Ь" для вершины .г, если

IM n HI = 6.

Пусть yaz — несмежные вершины разных типов из [х] и |[х] П [у] П [г]| = се. Обозначим через 5У число всех вершин, не смежных с вершиной г в [г], а через 5г — число всех вершин, не смежных с вершиной у в [.т].

Если 0г = Sy + 1, то будем назвать граф Г графом типа I. Если 5г = 5У + 2, то будем назвать граф Г графом типа II.

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

Теорема 2 Пусть Г — точный граф Деза с параметрами (и, к, Ь, а) без 3-коклик с ц = Ъ. Тогда (Ь — а) 6 {1,2}.

Теорема 3 Пусть Г — точный граф Деза с параметрами {у, k, Ь, а) без 3-коклик с fi = b и в Г есть eepviuna, окрестность которой содержит две несмежные вершины разных типов. Тогда

(1) если 5У = 1, то либо граф Г типа I с параметрами (8,4, 2,1), либо Г — граф типа II с параметрами (8га,8п — 4,8п — 6,8га — 8), п > 1;

(2) если а = Sy и граф Г — граф типа I, то Г имеет параметры (8,4,2,1) или (12,7,4,3).

Теорема 4 Пусть Г — точный граф Деза с параметрами (i>, k, Ь, а) без 3-киклик с /i = b и для некоторой вершины .г 6 Г любая вершина "типа а" смежна со всеми вершинами " типа Ь", и наоборот. Если все вершины " типа Ь" для х смежим между собой, то граф Г является 2-рашщкятем графа КпХ2-

Теорема 5 Пусть Г — точный граф Деза с параметрами (v,k,b,á) без 3-коклик и b = а + 2. Графi Г является точный графом Деза тогда и только тогда, когда Г является, вполне регулярным графом с параметрами (v, v — k — 1,0,2).

Автор выражает глубокую благодарность своему научному руководителю доктору физ.-мат. наук В.В. Кабанову за постановку задачи, внимание и поддержку, а также всем участникам семинара отдела алгебры и топологии ИММ УрО РАН за критические замечания и плодотворное обсуждение результатов диссертации.

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

[1] Вакула, И.А. О графах без 3-лап с некликовыми /i-подграфамн, натягиваемых на 3-коклику/ И.А. Вакула, В.В. Кабанов // Изв. Урал. гос. ун-та.-2005.- Т. 36.-Сер. Математика и механика. Вып.7 - С. 81-92.

|2| Вакула, H.A. О графах без 3-лап с некликовыми /t-подграфами/ И.А. Вакула, В.В. Кабанов // Дискрстн. анализ и исслед. опер,- Серия 1,- 2005.Т. 12,- Л'» 4,- С. 3-22.

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

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

[5] Махнев, А.А. О сильной регулярности некоторых реберно регулярных графов/ А.А. Махнев ,// Изв. РАН. Сер. матем,- Т.68,- № 1,- 2004,- С. 159-182.

[6] Bromver, А.Е. A characterization of some graphs which do not contain 3-claws/A.E. Brouwer, M. Numata // Discrete Math.- 1994,- Vol. 124,- P. 49-54.

[7] Chang, L.C. The uniqueness and nonuniqueness of triangular association schcmcs/ L.C. Chang // Sci. Record.- 1949,- Vol. 3,- P. 604-613.

[8] Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, щ = 12, щ = 15 and p^ = 4/ L.C. Chang // Sci. Record.-1950,- Vol. 4,- P. 12-18.

|9| De/.a, A. The ridge graph of the metric polyt.ope and some relatives/ A. Deza, M. Deza // in T. Bisztriczky. P. McMullen. R. Schneider and A. Ivic Weiss (ctls.), "Polytopcs: Abstract, Convex and Computational "Dordrecht, Kluwer.-1994,- P. 359-372.

[10J Erickson, M. Deza Graphs: A Generalization of Strongly Regular Graphs/ M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter // J. Combin. Designs.- 1999.- Vol. 7,- P. 395-405.

[11] Hoffman, A.J. On the uniqueness of the triangular association scheme/ A.J. Hoffman // Ann. Math. Stat.- I960,- Vol. 31.- P. 492-497.

[12] Hoffman, A.J. On the exceptional case in a characterization of the arcs of complete graphs/A. J. Hoffman // IBM J. Res. Develop.- I960,- Vol. 4,- P. 487496.

[13] Hoffman, A. J. On the line-graphs of the complete bipartite graph/ A.J. Hoffman // Ann. Math. Stat.- 1964,- Vol. 35.- P. 883-885.

[14] Seidel, J.J. Strongly regular graphs with (-1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel // Linear Algebra and Appl.- 1968,- Vol.1.- P. 281298.

|15| Slirickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande ,/./ Ann. Math. Stat-.- 1959,- Vol. 30,- P. 781-798.

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

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

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

[18] Ермакова, Г.М. Свойства графов без порожденных подграфов Л*1,з/ Г.М. Ермакова, В.В. Кабанов, Е.Ш. Сабирзянова, Го Вэньбинь // Труды Института математики и механики Уральского отделения РАН.- 2008.Т. 14,- № 4,- С. 43-52.

[19] Ермакова, Г.М. Точные графы Деза, которые являются соединениями сильно регулярных графов или точных графов Деза / Г.М. Ермакова, В.В. Кабанов / Проблемы теорет. и прикл. математики: тр. 39-й всероссийской молодеж. конф. Екатеринбург: УрО РАН, 2008.- С. 11-15.

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

[21] Ермакова, Г.М. Характеризация одного класса графов без порожденных A'i^-подграфов/ Г.М. Ермакова, В.В. Кабанов/ Труды Института математики и механики Уральского отделения РАН.-2009.- Т. 15.- № 2,- С. 98-112.

Введение

1 Графы без 3-лап

1.1 Предварительные результаты.

1.2 Сильные тройки в графах без 3-ла,п.

1.3 Графы без 3-лап с ограничениями на их /^-подграфы.

1.4 Исключительные тройки в графах без 3-лап с ограничениями на их /¿-подграфы.

1.5 Особые тройки в графах без 3-лап с ограничениями на их /¿-подграфы.

2 Точные графы Деза без 3-коклик с \± = Ь

2.1 Предварительные результаты.

2.2 Некоторые свойства точных графов Деза без 3 - коклик с ¡1 = Ь

2.3 Точные графы Деза, которые являются соединениями сильно

• регулярных графов или точных графов Деза.

2.4 Графы Деза, которые являются кликовыми расширениями сильно регулярных графов.

Пусть (7 — транзитивная группа подстановок на конечном множестве X. Если порядок группы четен, то стабилизатор в С точки х Е X имеет симметричную орбиту Д(я) на X отличную от {ж}. Тогда по группе С можно построить граф Г с множеством вершин X, и две вершины х,у смежны в Г тогда и только тогда, когда у £ Д(ж).

Изучение графов, полученных .таким образом, является важной задачей алгебраической теории графов. Если в качестве группы С рассмотреть симметрическую группу подстановок 5га на п символах, а в качестве множества X — множество всех транспозиций из 5"п и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф Т{п). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами (П^1~1\2(п — 2),п — 2,4). Кроме того, он ие содержит порожденных подграфов В работах 1959-60 гг. Л. Чанг [10] и А. Хоффман [13], [14] независимо показали, что треугольный граф Т{п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [9].

Класс графов без 3-лап содержит такой важный класс графов, как реберные графы,- Реберный граф Ь(Кт^п) полного двудольного графа Кт<п с долями порядка тип является кореберно регулярным графом с параметрами (тп,т + п — 2,2). Граф Ь{Кт^п) называют т х п-решеткой, п при т — п этот граф является сильно регулярным графом с параметрами (п2,2п — 2,п — 2,2). С. Щрикханде [18] и А. Хоффман [15] показали, что граф, имеющий параметры т х гг-решетки, является либо т х п-решеткой, либо графом Шрикханде, при п — 4. Все вышеперечисленные графы имеют наименьшее собственное значение —2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж Зсйделсм [17], который определил все сильно регулярные графы с наименьшим собственным значением —2. В частности, Дж. Зейдель показал, что кроме треугольных графов Т{п) и п х n-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

Полное описание графов без 3-лап с несвязными /¿-подграфами было получено А. Брауэром и М. Нуматой [8]. Они показали, что если граф связный конечный и содержит 3-коклику, то он является m х n-решеткой Этот результат был обобщен В.В. Кабановым в [5]. Им было доказано, что связный редуцированный граф без 3-лап содержит 3-коклику, а любой его /¿-подграф имеет радиус больше 1, тогда и только тогда, когда он является либо треугольным графом Т(п) с п > 6, либо m х n-решеткой с п > 3 и m > 3, либо графом Шлефли. Граф Шлефли — это единственный сильно регулярный граф с параметрами (27,16,10,8) В работах И.А. Вакулы и В.В. Кабанова [1], [2] описаны связные графы без 3-лап с неклнковыми /¿-подграфами.

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

В 1994 г. А. Деза и М Деза [11] привели пример точного графа Деза с параметрами (40,15, 6,4).

М. Эриксон, С. Фернандо, У.Х. Хаймерс, В. Харди и Дж. Хемметр [12] описали все точные графы Деза с числом вершин не более 13. A.A. Мах-невым [7] рассматривались графы Деза, которые являются кликовыми или кокликовыми расширениями сильно регулярных графов.

В диссертации рассматриваются только конечные неориентированные графы без петель и кратных ребер. Далее всюду подграф графа Г будет означать индуцированный подграф графа Г. Для вершины а графа Г через а] ([а]') обозначим подграф на множестве всех вершин, смежных(несмежных) с а. Этот подграф называется окрестностью вершины а в графе Г. Через ка обозначим валентность вершины а в Г, т. е. число вершин в [а]. Граф Г называется регулярным валентности к, если ка = к для любой вершины а из Г. Для ребра ас графа Г через Аас обозначим число вершин в подграфе [а] П [с]. Граф Г называется реберно регулярным с параметрами (г>, к, Л), если Г — регулярный граф на V вершинах валентности к, в котором каждое ребро лежит в Л треугольниках, т. е. Хас — А для любого ребра ас графа Г. Подграф [а]П[Ь] назовем ц-подграфом, ссли вершины а, Ъ находятся на расстоянии 2 друг от друга в графе Г и будем обозначать его через М(а, Ь). Граф Г на г> вершинах валентности к называется [1-регулярным с параметрами (у, к, /л), если все его д-подграфы имеют /л вершин. Если такой граф имеет диаметр 2, то он называется кореберно регулярным. Если реберно регулярный граф с параметрами (г;, к, А) является //-регулярным графом, то он называется вполне регулярным графом с параметрами (у, к, А, ¡л). Вполне регулярный граф диаметра 2 называется сильно регулярным.

Полный граф назовем кликой, а вполне несвязный граф — кокликой. Кли-ка(коклика) порядка п называется п-кликой(кокликой).

Пусть п — натуральное число. Под п-расширением графа Г будем понимать граф Г', полученный заменой каждой вершины а из Г на п-клику (а), причем вершины из (а) и (Ь) смежны в Г' тогда и только тогда, когда а и Ь смежны в Г.

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

Граф Г на у вершинах назовем графом Деза с параметрами (у, к, Ь, а), если для любых вершин и и ги из Г

N п N1 = { а или 6, если и ^ ги, к, если и — ги, если и — ги где V, к,Ъ,а — целые числа такие, что 0 < а <Ь < к < V.

Очевидно, класс графов Деза содержит класс сильно регулярных графов. Графы Деза, не являющиеся сильно регулярными и имеющие диаметр 2, называются точными графами Деза.

Рассмотрим графы Гх = (У^Ех) и Г2 = (Т^,^), где У\ и У2 — непересекающиеся множества вершин, а Е\ и Е2 — множества ребер графов Гх и Г2 соответственно.

Объединением таких графов Гх и Г2 назовем граф Гх и Г2 = (Ух и Уч, Е\ и Е2).

Суммой графов Гх и Г2 назовем граф Гх + Г2 = {У\ и У2, Е\ и Е2 и Ез), где Е3 = {{х,у} | х е Уъу € У2}.

Дополнение Г графа Г имеет в качестве множества вершин множество вершин графа Г и две вершины в Г смежны тогда и только тогда, когда они не смежны в Г.

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

1) Изучить связные графы без порожденных .К^з-подграфов, содержащих 3-коклпку, в которых для любой пары вершин и, V, находящихся на расстоянии 2 друг от друга, подграф М(и, у) — [и] П [г»] содержит /л вершин, если он не является кликой, и содержит и вершин в противном случае.

2) Исследовать точные графы Деза без'З-коклик с ¡л = Ъ.

Методы исследования. Основными методами исследования являются методы алгебраической теории графов.

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

1. Классифицированы связные графы без порожденных /^-подграфов, содержащих 3-коклику, в которых для любой пары вершин и, v, находящихся щ, расстоянии 2 друг от друга, подграф М(и, v) = [w]n[t>] содержит ß вершин, если он'не является кликой, и содержит v вершин в противном случае.

2. Найдено соотношение для параметров а и 6 точного графа Деза без 3-коклик с il = Ъ.

3. Описаны некоторые свойства и в отдельных случаях получено полное описание точных графов Деза без 3-коклик с ß = b.

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

Апробация работы. Основные результаты работы докладывались на 35-й, 37-40-ой Региональных молодежных конференциях ИММ УрО РАН (Екатеринбург, 2004, 2006-2009 гг.), Международной школе-конференции по теории групп (Нальчик, 2007 г.).

Результаты работы докладывались и обсуждались на алгебраическом семинаре ИММ УрО РАН.

Публикации. Основные результаты диссертации опубликованы в работах [19]—[24]. Работы [19]—[22] и [24] выполнены в нераздельном соавторстве с В.В. Кабановым.

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

Результаты диссертации. Во введении обсуждается история вопроса, даются определения и формулируются основные результаты.

В главе I рассматриваются связные графы без порожденных А^з-подграфов. В.В. Кабановым, A.A. Махневым в работе [4] были классифицированы такие графы в предположении, что все /i-подграфы равномощны.

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

Теорема 1 Пусть Г — связный граф без порожденных К\^-подграфов, содержащий 3-коклику. Пусть также в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф A4 (и, v) — [и] П [г>] содержит ц вершин, если он не является кликой, и codepoicum и вершин в противном случае. Если ь> > [1, то все подграфы М(и, v) в Г одного типа, т. е. все кликовые или все неклико вые.

Из этой теоремы и результата полученного В.В. Кабановым и A.A. Мах-невым в [4] имеем

Следствие 1 Пусть Г — связный граф без порожденных К\^-подграфов, содержащий 3-коклику. Пусть таклсе в Г для любой пары вершин и, v на расстоянии 2 друг от друга подграф М{и, v) = [гг] П [г>] содержит ¡1 вершин, если он не является кликой и содержит v вершин в противном случае, где и > ¡1. Тогда

1) либо граф Г является а-расширением, графа икосаэдра, либо в Г — Гх подграф на множестве всех вершин с некликовыми окрестностями является пустым графом, кликой или а-расширепием связного графа с ß = 1;

2) граф Г является а-расширепием одного из следующих графов: г) т х птрешелпки, где m > 3 и п > 3; (гг) треугольного графа Т(т),т > 6; (ггг) графа Шлефли.

Во второй главе работы рассматриваются точные графы Деза без 3-коклик с ¡1 = Ь. Описаны точные графы Деза, которые являются суммой сильно регулярных графов или точных графов Деза, и точные графы Деза, которые являются кликовыми расширениями сильно регулярных графов. Пусть Г — точный граф Деза без 3-коклик с ц = b и вершина х — произвольная вершина графа Г. Будем называть вершину и € [ж] графа Г вершиной "типа о" для вершины х, если \[х] П |/и]| = а, а вершину ги £ [ж] — вершиной "типа 6" для вершины х, если | [я] П [го] | = Ь.

Пусть у иг — несмежные вершины разных типов из [ж] и | [х] П [у] П [г] | = а. Обозначим через 5У число всех вершин, не смежных с вершиной г; в [ж], а через 62 — число всех вершин, не смежных с вершиной у в [¿с].

Если 52 = 5У + 1, то будем назвать граф Г графом типа I. Если 62 = 5У + 2, то будем назвать граф Г графом типа II.

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

Теорема 2 Пусть Г — точный граф Деза с параметрами ("У, к, Ь, а) без 3-коклик с ¡1 — Ъ. Тогда (6 — а) £ {1, 2}.

Теорема 3 Пусть Г - точный граф Деза с параметрами (1;, /г, 6, а) без 3-коклик с — Ъ и в Т есть вершина, окрестность которой содероюит две песмеэюиые вершины разных типов. Тогда

1) если 5У = 1, то либо граф Г типа I с параметрами (8,4, 2,1); либо Г — граф'типа II с параметрами (8 п, 8 п — 4, 8 п — 6, 8 п — 8). п > 1;

2) если а — 5У и граф Г — граф типа I, то Г имеет параметры (8,4, 2,1) шш (12,7,4,3).

Теорема 4 Пусть Г — точный граф Деза с параметрами (и,к,Ь,а) без 3-коклик с рь = Ъ и для некоторой вершины х £ Г любая вершина "типа а" смежна со всеми вершинами " типа 6", и наоборот. Если все вершины " типа 6" для х смежны между собой, то граф Г является 2-расширением графа Кп

Теорема 5 Пусть Г — точный граф Деза с параметрами (у,к,Ь,а) без 3-коклик и Ь = а + 2. Граф Г является точный графом Деза тогда и только тогда, когда Г является вполне регулярным графом с параметрами — к -1,0, 2).

1 Графы без 3-лап

1. Вакула, И.А. О графах без 3-лап с некликовыми /i-подграфами, натягиваемых на 3-коклику/ И.А. Вакула, В.В. Кабанов // Изв. Урал. гос. ун-та.- 2005.- Т. 36.- Сер. Математика и механика. Вып. 7.- С. 81-92.

2. Вакула, И.А. О графах без 3-лап с некликовыми /¿-подграфами/ И.А. Вакула, В.В. Кабанов // Дискретн. анализ и исслед. опер,- Серия 1 2005.Т. 12, № 4,- С. 3-22.

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

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

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

6. Кабанов, В.В. О графах без корон с регулярными /¿-подграфами, II/ В.В. Кабанов, A.A. Махнев, Д.В. Падучих // Математические заметки,-2003,- Т. 74 С .396-406.

7. Махнев, A.A. О сильной регулярности некоторых реберно регулярных графов/ A.A. Махнев // Изв. РАН. Сер. матем,- Т. 68, № 1.- 2004.- С. 159182.

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

9. Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ L.C. Chang // Sei. Record.- 1949,- Vol. 3,- P. 604-613.

10. Chang, L.C. Association schemes of partially balanced block designs with parameters v = 28, n\ = 12,no = 15 and — 4/ L.C. Chang // Sci. Record.- 1950,- Vol. 4,- P. 12-18.

11. Deza, A. The ridge graph of the metric polytope and some relatives/ A. Deza, M. Deza // in T. Bisztriczky, P. McMullen, R. Schneider and A. Ivic Weiss (eds.), "Polytopes: Abstract, Convex and Computational11 Dordrecht, Kluwer.- 1994,- P. 359-372.

12. Erickson, M. Deza Graphs: A Generalization of Strongly Regular Graphs/ M. Erickson, S. Fernando, W.H. Haemers, D. Hardy, J. Hemmeter //J. Combin. Designs.- 1999,- Vol. 7,- P. 395-405.

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

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

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

16. Hubaut Xavier L. Strongly regular graphs / L. Hubaut Xavier // Discret, Mathematics.- 1964.- Vol. 13,- P. 357-381.

17. Seidel, J.J. Strongly regular graphs with (—1,1,0) adjacency matrix having eigenvalue 3/ J.J. Seidel // Linear Algebra and Appl.- 1968.- Vol.1.- P. 281298.

18. Shrickhande, S.S. The uniqueness of the association scheme/ S.S. Shrickhande // Ann. Math. Stat.- 1959,- Vol. 30,- P. 781-798.Работы автора по теме диссертации

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

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

21. Ермакова, Г.М. Свойства графов без порожденных подграфов з/ Г.М. Ермакова, В.В. Кабанов, Е.Ш. Сабирзянова, Го Вэньбинь // Труды Института математики и механики Уральского отделения РАН,- 2008.Т. 14,- № 4.- С. 43-52.

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

23. Ермакова, Г.М. Характеризация одного класса графов без порожденных .ЙТ^з-подграфов/ Г.М. Ермакова, В.В. Кабанов/ Труды Института математики и механики Уральского отделения РАН.- 2009.- Т. 15.- № 2.C. 98-112.