WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

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

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

ЕРМАКОВА Галина Михайловна ДВЕ ЗАДАЧИ АЛГЕБРАИЧЕСКОЙ ТЕОРИИ ГРАФОВ 01.01.06 математическая логика, алгебра и теория чисел А в т о р е ф е р а т диссертации на соискание ученой степени кандидата физико-математических наук

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

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

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

Официальные оппоненты: доктор физико-математических наук, доцент АЛЕЕВ Рифхат Жалялович кандидат физико-математических наук РАСИН Олег Вениаминович

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

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

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

Автореферат разослан мая 2009 года И.о. ученого секретаря диссертационного совета, доктор физ.-мат. наук В.И. Зенков

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

.

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

Пусть G транзитивная группа подстановок на конечном множестве X.

Если порядок группы четен, то стабилизатор в G точки x X имеет симметричную орбиту (x) на X отличную от {x}. Тогда по группе G можно построить граф с множеством вершин X, и две вершины x, y смежны в тогда и только тогда, когда y (x).

Изучение графов, полученных таким образом, является важной задачей алгебраической теории графов. Если в качестве группы G рассмотреть симметрическую группу подстановок Sn на n символах, а в качестве множества X множество всех транспозиций из Sn и считать смежными любые две неперестановочные транспозиции, то получим треугольный граф T (n). Нетрудно видеть, что этот граф является сильно регулярным графом с параметрами (n(n-1), 2(n2), n - 2, 4). Кроме того, он не содержит порожденных K1,3-подграфов. В работах 1959-60 гг. Л. Чанг [8] и А. Хоффман [11], [12] независимо показали, что треугольный граф T (n) определяется однозначно своими параметрами для всех n, за исключением n = 8. Для случая n = 8 было показано, что кроме треугольного графа T (8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 г. [7].

Класс графов без 3-лап содержит такой важный класс графов, как реберные графы. Реберный граф L(Km,n) полного двудольного графа Km,n с долями порядка m и n является кореберно регулярным графом с параметрами (mn, m + n - 2, 2). Граф L(Km,n) называют m n-решеткой, и при m = n этот граф является сильно регулярным графом с параметрами (n2, 2n - 2, n - 2, 2).

С. Шрикханде [15] и А. Хоффман [13] показали, что граф, имеющий параметры mn-решетки, является либо mn-решеткой, либо графом Шрикханде, при n = 4. Все вышеперечисленные графы имеют наименьшее собственное значение -2. Результаты Л. Чанга, С. Шрикханде и А. Хоффмана были объединены Дж. Зейделем [14], который определил все сильно регулярные графы с наименьшим собственным значением -2. В частности, Дж. Зейдель показал, что кроме треугольных графов T (n) и nn-решеток, сильно регулярными графами, которые имеют наименьшее собственное значение -2, являются только графы Kn2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.

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

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

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

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

В диссертации рассматриваются только конечные неориентированные графы без петель и кратных ребер. Далее всюду подграф графа будет означать индуцированный подграф графа. Для вершины a графа через [a] обозначим подграф на множестве всех вершин, смежных с a. Этот подграф называется окрестностью вершины a в графе. Через ka обозначим валентность вершины a в, т. е. число вершин в [a]. Граф называется регулярным валентности k, если ka = k для любой вершины a из. Для ребра ac графа через ac обозначим число вершин в подграфе [a][c]. Граф называется реберно регулярным с параметрами (v, k, ), если регулярный граф на v вершинах валентности k, в котором каждое ребро лежит в треугольниках, т. е. ac = для любого ребра ac графа. Подграф [a] [b] назовем µ-подграфом, если вершины a, b находятся на расстоянии 2 друг от друга в графе и будем обозначать его через M(a, b).

Граф на v вершинах валентности k называется µ-регулярным с параметрами (v, k, µ), если все его µ-подграфы имеют µ вершин. Если такой граф имеет диаметр 2, то он называется кореберно регулярным. Если реберно регулярный граф с параметрами (v, k, ) является µ-регулярным графом, то он называется вполне регулярным графом с параметрами (v, k,, µ). Вполне регулярный граф диаметра 2 называется сильно регулярным.

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

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

Граф на v вершинах назовем графом Деза с параметрами (v, k, b, a), если для любых вершин u и w из a или b, если u = w, |[u] [w]| = k, если u = w, где v, k, b, a целые числа такие, что 0 a b k < v.

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

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

Рассмотрим графы 1 = (V1, E1) и 2 = (V2, E2), где V1 и V2 непересекающиеся множества вершин, а E1 и E2 множества ребер графов 1 и соответственно.

Объединением таких графов 1 и 2 назовем граф 1 2 = (V1 V2, E1 E2).

Суммой графов 1 и 2 назовем граф 1 + 2 = (V1 V2, E1 E2 E3), где E3 = {{x, y} | x V1, y V2}.

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

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

1) Изучить связные графы без порожденных K1,3-подграфов, содержащих 3коклику, в которых для любой пары вершин u и v, находящихся на расстоянии 2 друг от друга, подграф M(u, v) = [u] [v] содержит µ вершин, если он не является кликой, и содержит вершин в противном случае.

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

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

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

1. Классифицированы связные графы без порожденных K1,3-подграфов, содержащих 3-коклику, в которых для любой пары вершин u и v, находящихся на расстоянии 2 друг от друга, подграф M(u, v) = [u] [v] содержит µ вершин, если он не является кликой, и содержит вершин в противном случае.

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

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

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

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

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

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

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

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

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

В.В. Кабановым, А.А. Махневым в работе [3] были классифицированы такие графы в предположении, что все µ-подграфы равномощны.

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

Теорема 1 Пусть связный граф без порожденных K1,3-подграфов, содержащий 3-коклику. Пусть также в для любой пары вершин u, v на расстоянии 2 друг от друга подграф M(u, v) = [u] [v] содержит µ вершин, если он не является кликой, и содержит вершин в противном случае. Если µ, то все подграфы M(u, v) в одного типа, т. е. все кликовые или все некликовые.

Из этой теоремы и результата полученного В.В. Кабановым и А.А. Махневым в [3] имеем Следствие. Пусть связный граф без порожденных K1,3-подграфов, содержащий 3-коклику. Пусть также в для любой пары вершин u, v на расстоянии 2 друг от друга подграф M(u, v) = [u] [v] содержит µ вершин, если он не является кликой, и содержит вершин в противном случае, где µ.

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

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

(i) m n-решетки, где m 3 и n 3;

(ii) треугольного графа T (m), m 6;

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

Во второй главе работы рассматриваются точные графы Деза без 3-коклик с µ = b. Описаны точные графы Деза, которые являются суммой сильно регулярных графов или точных графов Деза, и точные графы Деза, которые являются кликовыми расширениями сильно регулярных графов. Пусть точный граф Деза без 3-коклик с µ = b и вершина x произвольная вершина графа. Будем называть вершину u [x] графа вершиной “типа a” для вершины x, если |[x] [u]| = a, а вершину w [x] вершиной “типа b” для вершины x, если |[x] [w]| = b.

Пусть y и z несмежные вершины разных типов из [x] и |[x] [y] [z]| =.

Обозначим через y число всех вершин, не смежных с вершиной z в [x], а через z число всех вершин, не смежных с вершиной y в [x].

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

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

Теорема 2 Пусть точный граф Деза с параметрами (v, k, b, a) без 3-коклик с µ = b. Тогда (b - a) {1, 2}.

Теорема 3 Пусть точный граф Деза с параметрами (v, k, b, a) без 3-коклик с µ = b и в есть вершина, окрестность которой содержит две несмежные вершины разных типов. Тогда (1) если y = 1, то либо граф типа I с параметрами (8, 4, 2, 1), либо граф типа II с параметрами (8n, 8n - 4, 8n - 6, 8n - 8), n 1;

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

Теорема 4 Пусть точный граф Деза с параметрами (v, k, b, a) без 3-коклик с µ = b и для некоторой вершины x любая вершина ”типа a” смежна со всеми вершинами ”типа b”, и наоборот. Если все вершины ”типа b” для x смежны между собой, то граф является 2-расширением графа Kn2.

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

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

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

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

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

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

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

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

[7] Chang, L.C. The uniqueness and nonuniqueness of triangular association schemes/ 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, n1 = 12, n0 = 15 and p2 = 4/ L.C. Chang // Sci. Record.n 1950.- Vol. 4.- P. 12–18.

[9] 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 Computational"Dordrecht, Kluwer.1994.- P. 359–372.

Pages:     |
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.