Бесплатно скачать, заказать диплом, курсовую, диссертацию РеБерно регулярные графы и их автоморфизмы

У нас уже 21989 рефератов, курсовых и дипломных работ

Сделать закладку на сайт

Заказать диплом, курсовую, диссертацию

Быстрый переход к готовым работам

Мнение посетителей:

Книга жалоб
и предложений

Название	РеБерно регулярные графы и их автоморфизмы

Количество страниц	69

ВУЗ	МГИУ

Год сдачи	2010

Бесплатно Скачать	23578.doc

Содержание	Содержание Введение 3 1 Хорошие пары в реберно регулярных графах 10 1.1 О реберно регулярных графах с к > 3&i — 2... 11 1.2 О хороших парах в графах с к > ЗЬ\ — 2 ... 25 2 Об автоморфизмах сильно регулярных графов 42 2.1 Введение... 42 2.2 Об автоморфизмах графа с параметрами (99,14,1,2)... 45 2.3 Об автоморфизмах графа с параметрами (243,22,1,2)... 56 3 Об автоморфизмах графа с параметрами (115,18,1,3) 63 Литература 69 Введение Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь — вершины графа Г, то через d(a, b) обозначим расстояние между а и 6, а через Г$(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии i от вершины а. Подграф 14(а) будем называть окрестностью вершины а и обозначать через [а]. Через aL обозначим подграф, индуцированный {a} U [а]. Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Граф Г назовем реберно регулярным с параметрами (v,A;, А), если он содержит v вершин, регулярен степени к, и каждое его ребро ab лежит в Л треугольниках. Граф Г — вполне регулярный граф с параметрами (v, к, A, /z), если он реберно регулярен с соответствующими параметрами и [а] П [6] содержит fi вершин для любых двух вершин а, 6, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивио на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 30, 31]. Например, класс билдингов Титса характеризует группы Лиевского типа [32]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [14]. Пусть G — транзитивная группа подстановок на множестве П. Если подгруппа Gp группы G, состоящая из всех подстановок, фиксирующих точку р G П, имеет г орбит, то говорят, что G является группой ранга г. Пусть г = 3 и соответствующие 3 орбиты — это {р}, А(р), Г(р). Тогда по группе G удается построить сильно регулярный граф Г, множество вершин которого — Пи две вершины р, q смежны в Г, если р Е Д( Д.Хигмэн [21 — 27] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин, так и на множестве ребер. Такие графы являются дистанционно транзитивными графами диаметра 2. Граф Г диаметра d называется дистанционно транзитивным, если для любого i ? {0,..., d} и для любых вершин и, v, х, у, таких что d(u, v) = d(x, у) = г, существует автоморфизм д графа Г : (u,v)3 — (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [28]. Если вершины u,w находятся на расстоянии г в Г, то через bi(u,w) (через Ci(u,w)) обозначим число вершин в пересечении Ti+i(u) (Ff_i(u)) с [w]. Дистанционно регулярным графом называется граф, в котором параметры bi(u,w) и Ci(u,w)) не зависят от вершин и, г>, а зависят только от расстояния на котором эти вершины находятся в графе Г. Поскольку каждый дистанционно регулярный граф является вполне ре-" гулярным графом (в частности, реберно регулярным графом), то некоторые результаты об этих классах графов могут быть использованы в теории ди-станционно регулярных графов. В первой главе монографии [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (г;, &, А), в котором к > З&ь то Г имеет диаметр 2иг;<2А; — 2. Цель работы. В диссертации исследуются строение реберно регулярных графов с к > 3&i — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Аи//. Диссертация состоит из введения, трех глав и списка литературы (33 наименования). В главе 1 рассматриваются реберно регулярные графы. Пусть Г — реберно регулярный граф с параметрами (v,k,\). Тогда (см. лемму 1.1.1) степень вершины в любом /i-подграфе из Г не больше к — 2Ь\. Поэтому для /i* = к — 2Ь\ + 1 и любых вершин и, и?, находящихся на расстоянии 2, выполняется неравенство fi(u,w) > /л. Пару несмежных вершин (u,w) назовем хорошей, если fi(u, w) = /z. В следствии из статьи А. А. Махнева [4] доказано, что если Г - связный реберно регулярный граф с параметрами (v, к,Х), в котором ЗА > 2к — 5, то либо Г - многоугольник или граф икосаэдра, либо к = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2к + 4 вершинами. В параграфе 1.1. данной работы уточняется строение графа, удовлетворяющего условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберно регулярных графах. Следующие результаты являются основными в главе 1. Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра, 2 с параметрами (г>, &,А), в котором ЗА > 2к — 5 и 2к + 1 < v. Тогда Г ¦ пятиугольник, 3x3 решетка или треугольный граф Т(7). Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами (v, /г, А), в котором ЗА > 2к — 5. Тогда либо (к, А) = (4,1) и диаметр Г больше 2, либо Г - многоугольник, граф икосаэдра, 3x3 решетка или треугольный граф Т(7), либо Г - граф диаметра 2 с не более чем 2к вершинами. Теорема 1.2. Пусть Г — связный реберно регулярный граф с параметрами (v,k,\) и d ? Г. Если к > 3&i — 2, то либо к = ЗЬ\ — 1, Г является многоугольником или графом икосаэдра и любые две вершины, находящиеся на расстоянии 2, образуют хорошие пары, либо для любой вершины d из Г пары (d,Wi) являются хорошимщдля/не более чем трех\вершин W{ из T2(d). Случай k > 36i — 1 рассмотрен в работе [6]. Во второй главе работы выясняются возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярных графов с (Л,д) = (1,2). Подграфы неподвижных точек автоморфизмов сильно регулярного графа с малыми значениями параметров Лид имеют жестко заданное строение. Так подграф неподвижного множества автоморфизма графа Мура сам является графом Мура или звездой (см. лемму 1 [10]). Хорошо известно (предложение 1.1.2 [14]), что сильный граф с ц > 2 сильно регулярен. Поэтому подграфы неподвижных точек 2'-автоморфизмов сильно регулярного графа с тах{Л, fi} < 2 сильно регулярны с этими же параметрами или являются кликами. В первом параграфе главы 2 приведены вспомогательные леммы и изложен метод Д.Хигмана работы с автоморфизмами сильно регулярных графов [19]. Во втором параграфе теоретико-графовыми методами выясняются возможные порядки и строение подграфов неподвижных точек автоморфизмов графа с параметрами (99,14,1,2). Затем с помощью теории характеров конечных групп полученные результаты существенно уточняются. В конце параграфа 2.2 работы найдено возможное строение группы G автоморфизмов графа с параметрами (99,14,1,2) при условии, что эта группа содержит инволюцию. В третьем параграфе указанной главы с помощью теории характеров конечных групп выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (243,22,1,2). В третьей главе диссертации с применением аналогичных методов главы 2 выяснены возможные порядки и строение подграфов неподвижных точек автоморфизмов графа Г с параметрами (115,18,1,3), если группа автомор- физмов этого графа содержит элемент порядка 3. Пусть Г является сильно регулярным графом с параметрами (г>, А:,Л, ЛЛ) и G = Aut(F) — группа его автоморфизмов. Для X G G через Fix(X) обозначим индуцированный подграф на множестве вершин графа Г неподвижных относительно любого автоморфизма из X. Отметим далее некоторые утверждения, верные для графов с параметрами (v, к, 1,2). Так как Г — сильно регулярный граф, то к > 4. При к = 4 Г имеет параметры (9,4,1,2). Этим параметрам соответствует единственный граф, а именно, 3 х 3-решетка.[2]. В случае к > 4, используя равенство (Л — fi)2 4- 4(& — /i) = п2, получим n = 2ii+l, к = и2 + и + 2, п — тп = и и —т = — и — 1. По условию целочисленности для сильно регулярных графов [14] имеем /т = 2(2гг+1) делит (m- l)k(k + m) = u(u2 -\-u + 2)(u2 + 2u + 3). Поэтому 2u + 1 делит 63, и и = 1, 3,4,10 или 31. При и = 1 снова возникает 3 х 3-решетка. При и = 3 получается граф с параметрами (99,14,1,2), автоморфизмы которого изучались в работе [9]. При и = 4 получается граф с параметрами (243,22,1,2), автоморфизмы которого изучались в работе [11]. В третьей главе работы рассматривается сильно регулярный граф с параметрами (г;, к, 1,3). Доказательство теорем второй и третьей главы опирается на метод Дональда Хигмена работы с автоморфизмами сильно регулярного графа, изложенный в третьей главе монографии Камерона [19]. При этом сильно регулярный граф Г на v вершинах с собственными значениями &, г, s рассматривается как симметричная схема отношений (X, {До, R\, R2}), где X — множество вершин графа Г, ~ Rq — отношение равенства на вершинах графа Г, R\ — отношение смежности в Г и R Если Р и Q — первая и вторая матрицы собственных значений схемы, то ( 1 1 1 \ Р= к г s , 1 U /V ~~ X / X О X J и PQ = QP = vl. При этом кратности l,f,g собственных значений k,r,s графа Г образуют первый столбец матрицы Q. Подстановочное представление группы G = Aut(T) на вершинах графа Г обычным образом дает матричное представление "ф группы G в GL(v, С). Пространство Cv является ортогональной прямой суммой собственных iJj{G)-инвариантных подпространств Wq ф W\ ф Wi матрицы смежности графа Г. Пусть хг ~ характер представления i\)wv Тогда для любого д G G получим Xi(9) = v-1Y,Qijaj(9), где <У{(д) — число точек х из X таких, что (ж, хв) 6 Ri- Заметим, что значения характеров являются целыми алгебраическими числами, а правая часть данной формулы — число рациональное, поэтому Хг(#) является целым числом. Основными результатами второй главы являются: Теорема 2.1. Пусть Г является сильно регулярным графом, с параметрами (99,14,1,2), G = Aut(F). Если д — элемент простого порядка из G, Д = Fix(g), то выполняется одно из утверждений: (1) А — одновершинный граф и \д\ = 2 или 7; (2) Л — пустой граф гх j^j = 3 или 11; (2) Д — треугольник и \д\ = 3. В частности, порядок группы автоморфизмов сильно регулярного графа с параметрами (99,14,1, 2) делит 2 • З3 • 7 • 11. Следствие 2.1. Пусть Г является сильно регулярным графом с параметрами (99,14,1,2), G = Aut(F). Если G codepoicum инволюцию t, то вы- полняется одно из утверждений: (1) \|Ст\| делится на 7 и делит 42, причем [O(G),t] = 1 и в случае \G\ = 42 подгруппа O{G) неабелева. (2) \|G\| делит 6. Теорема 2.2. Пусть Г является сильно регулярным графом с параметрами (243,22,1,2), G = Aut(F). Если р — элемент простого порядка из G, А = Fix(p), mo выполняется одно из утверждений: (1) \|р\| = 2, \|А\| = 9 и каждая связная компонента графа А является одновершинным графом, треугольником или 3x3 решеткой; (2) \|р\| = 3, Д является пустым графом или 3x3 решеткой; (3) \р\ = 5, А является треугольником; (4) \|р\| = 11, А является одновершинным графом. Основным результатом главы 3 является следующая теорема: Теорема 3.1. Если Г является сильно регулярным графом с параметрами (115,18,1,3), то порядок группы автоморфизмов графа Г делит число 2^5 • 23. Автор выражает глубокую признательность своим научным руководителям профессору А.А. Махневу и д.ф.-м.н В.В. Кабанову за постановку задачи и постоянное внимание. 1 Хорошие пары в реберно регулярных графах Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ь- вершины графа Г, то через d(a, 6) обозначается расстояние между а и Ь, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины а. Подграф Fi(a) называется окрестностью вершины а и обозначается через [а]. Через aL обозначается подграф, являющийся шаром радиуса 1 с центром а. Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г. Граф Г называется реберно регулярным графом с параметрами (v,k,X)t если Г содержит v вершин, является регулярным степени к, и каждое ребро в Г лежит в Л треугольниках. Граф Г называется вполне регулярным графом с параметрами (v, k,X, //), если Г реберно регулярен и подграф [а] П [6] содержит /х вершин в случае d{a, Ъ) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Число вершин в [а]П[6] обозначим через Л(а, 6) (через д(ат6)), если d(a, b) = 1 (если d(a,b) = 2), а соответствующий подграф назовем (/х-) Л-подграфом. Через Kmu...,mn обозначим полный п-дольный граф, с долями порядков т\, ..., тп. Если mi = ••• = тпп = т, то соответствующий граф обозначается через Кпхш. Треугольным графом Т{т) называется граф с множеством неупорядоченных пар из X в качестве вершин, \|Х\| = т и пары {а, 6}, {с, d} смежны тогда и только тогда, когда они имеют единственный общий элемент. Граф на множестве вершин X х Y называется т х п решеткой, если \Х\ = т, \Y\ = п и вершины (xi,2/i), (^2?Уг) смежны тогда и только тогда, когда х\ = Х2 или 2/1 = Уг- Для подграфа Л через \|А\| обозначим число его вершин. Если вершины и, w находятся на расстоянии г в Г, то через 6j(u, w) (q(w, w)) обозначим число вершин в пересечении Т{+\{и) {Ti-\{u)) с [w]. Заметим, что в реберно регулярном графе с параметрами (v, k,X) значение bi(u,w) не за- висит от выбора ребра uw и равно к — Л — 1. В следствии из [2] доказано, что если Г - связный реберно регулярный граф с параметрами (v, &, А), в котором ЗА > 2к — 5, то либо Г - многоугольник или граф икосаэдра, либо к = 4 и каждое ребро в Г лежит в единственном треугольнике, либо Г - граф диаметра 2 с не более чем 2к + 4 вершинами. В лемме 1.4.2 из [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (v, fc,A), в котором А > 2к/3 — 1, (эквивалентно к > 3&i), то Г имеет диаметр 2, v <2к — 2и выполняется неравенство () kbi>(v-k- 1){к + 1 - 26i). Пусть Г — реберно регулярный граф с параметрами (v, к,Х). Тогда (см. лемму 1.1.1) степень вершины в любом /i-подграфе из Г не больше к — 2Ь\. Поэтому для /л = А;—26x4-1 и любых вершин и, w, находящихся на расстоянии 2, выполняется неравенство fi(u,w) > //. Пару несмежных вершин (u,w) назовем хорошей, если /i(u,w) = \х. В параграфе 1.1. данной работы уточняется строение графа, удовлетворяющего условиям следствия, в случае, когда диаметр графа равен 2. В параграфе 1.2. изучено расположение хороших пар в реберио регулярных графах. Во втором параграфе этой главы используется следующее обозначение. Если х,у - различные вершины графа Г, то через ЛХ)У обозначается подграф Г- (a;1 U у1). 1.1 О реберно регулярных графах с к > 3&i — 2 В данном параграфе доказывается следующая теорема и ее следствие: Теорема 1.1. Пусть Г - связный реберно регулярный граф диаметра 2 с параметрами (v,k,X), в котором ЗА > 2к — 5 и 2к + 1 < v. Тогда Г -пятиугольник, 3x3 решетка или треугольный граф Т(7). Следствие 1.1. Пусть Г - связный реберно регулярный граф с параметрами (г;, /г, А), в котором ЗА > 2к — 5. Тогда либо (к, А) = (4,1) и диаметр Г больше 2, либо Г - многоугольник, граф икосаэдра, 3x3 решетка или треугольный граф Т{1), либо Г - граф диаметра 2 с не более чем 2k вершинами. Пусть граф Г удовлетворяет условиям теоремы, v = 2к + 5. Для вершин х, у графа Г положим Л^у = Г — (жх U у1). Через bi обозначим к — А — 1. Из условий теоремы следует, что к > 36i — 2, Л > 2&i — 3, 5 > 1. Лемма 1.1.1. Пусть u,w - несмежные вершины из Г и вершина d имеет степень а в графе [и] П [w]. Тогда [d] содержит к — 2А — 2 + а вершин вне uL U w1-. В частности, степень любой вершины в fi-подграфе из Г не меньше bi-2. ¦ Доказательство. Пусть d(u, w) = 2, х Е [и] П [w] и степень х в этом д-подграфе равна а. Тогда [х] содержит 2А + 2 — а вершин из u^-Uw1: Поэтому 2А + 2 - а < (ЗА + 5)/2 иа>(А- 1)/2 > Ьх — 2. Лемма доказана. Пару несмежных вершин (w,it;) назовем хорошей, если fi(u,w) = b\ — 1. Ввиду леммы 1.1.1 //-подграф, образованный хорошей парой, является кликой. Лемма 1.1.2. Выполняются следующие утверждения: (1) для мЕГ вершина из Г2(гг) смежна в среднем с кЪ\/{у — к — 1) вершинами из [it]; (2) если Г не содержит хороших пар, то Г - пятиугольник, 3x3 решетка или треугольный граф Т(7); (3) если Г содержит хорошую пару (u,w), то k = 3&i — 2, А = 2&i — 3, Ъ\ четно и \AUjW\ = S + 61 — 3; (4) если вершины u, w не смежны, х G [и] П [ги], то [х] Сихи и?1- тогда и только тогда, когда степень вершины х в графе [и] П [w] равна Ь\ — 2. Доказательство. Число ребер между [и] и Г2(и) равно &&ь Далее, \|Г2(и)\| = v — к — 1 > к. Поэтому вершина из Т2(и) смежна в среднем с кЪ\/(у — к — 1) вершинами из [и]. Но указанное число не больше кЪ\/к = Ъ\. Утверждение (1) доказано. Допустим, что Г не содержит хороших пар. Из доказательства утверждения (1) и леммы 1.1.1 следует, что Г - сильно регулярный граф с параметрами [2к 4- 1, к, к — Ъ\ — l,&i). Отсюда либо к = 2&i, Л = Ъ\ — 1 и Ь\ < 2, либо (к — 2Ъ\ — I)2 4- 4(к — bi) является квадратом натурального числа п. В первом случае Г - пятиугольник или 3x3 решетка. В последнем случае п2 = (fc-26i + l)2 + 4&i. Если п = fc-2bi + l + z, то х2+ 2х{к-2Ьх + 1) = 4&ь причем 4&i > х2 + 2ж(&1 — 1). Отсюда х = 2, к = 3&i — 2, п = &1 + 1иГ имеет неглавные собственные значения Ь\ — 1 и -2. По теореме Зейделя (теорема 3.12.4 [14]) сильно регулярный граф с собственным значением -2 является полным многодольным графом КиХ2, решетчатым или треугольным графом, одним из графов Чанга, либо графом Петерсена, Шрикханде, Клебша или Шлефли. Таким образом, Г - пятиугольник, 3x3 решетка или треугольный граф Г(7). Пусть (u,w) - хорошая пара, х 6 [и] П [w]. Ввиду леммы 1.1.1 подграф [и] П [го] является кликой и [х] П [w] содержит Ь\ — 2 вершины из [и] и А — &i + 2 вершин из Т2(и). Отсюда A — &i+2 < &i — 1 и А < 26i —3. Подставив А = 2Ь\ — 3 в неравенство (ЗА + 5)/2 > к, получим к < 36i — 2. Итак, к = 3&i — 2. Если &i нечетно, то нечетны и А:, А. Противоречие с тем, что окрестность вершины содержит АгА/2 ребер. Наконец, lu1- U w1] = 2к + 2 — (&i — 1) и \|Au,u,\| = v + bi — 2к — 3 = 5 + &i — 3. Утверждение (3) доказано. Пусть (u,w) - несмежные вершины, х Е [и] П [w] и степень вершины х в подграфе [и] П [w] равна а. Заметим, что к = 2А + 2 — а тогда и только тогда, когда а = Ъ\ — 2. Это дает утверждение (4). Лемма доказана. До конца работы будем предполагать, что граф Г содержит хорошую пару (u,w). Положим Л = Ащи}. Заметим, что если v > 2к + 2, то для любой вершины х найдется вершина у, образующая с ? хорошую пару. Лемма 1.1.3. Выполняются следующие утверждения: (1) число J3 вершин, образующих хорошую пару с и, не меньше (6 — 1)&ь' (2) если вершина х из Л образует хорошую пару си, то n(x,w) > b\ + 3 — 5; (3) v < 2к 4- 3, \кх,у\ > Ь\ + S — 3 для любых несмежных вершин х,у, я Л не содержит хороших пар. Доказательство. Ввиду леммы 1.1.1 имеем неравенство kb\ > /?(&i — 1) + (v — к — 1 — /?)&i. Отсюда /3 > (г; — 2к — 1)Ъ\ = (5 — l)&i. Утверждение (1) доказано. Пусть вершина х из Л образует хорошую пару с и. Тогда [х] содержит не более (&i — 1) + (v + b\ — 2к — 4) вершин из ^(w). Поэтому /j,(x,w) > 1Ъ\ — l — v = b\ + Z — 5. Утверждение (2) доказано. Число вершин v не больше 2к + 4 (см. доказательство следствия из [4]). Допустим, что v = 2к + 4. Тогда v = 6b\ и для любой вершины х имеем \|Г2С^2^)I = 3^1 + 1, поэтому по утверждению (1) ^(я) содержит единственную вершину х, не образующую хорошую пару с х. Теперь kb\ — ЪЬ\{Ь\ — 1) + ц(х, х) и jj,(x, х) = b\. Покажем, что граф Г не содержит 3-лап. Пусть для некоторой вершины d подграф [d\ содержит 3-коклику x,y,z. Тогда [d] содержит х и Ab\ — A — a вершин из y^-Uz-1, где а: - степень d в [?/]n[z]. Отсюда a = b\ — 1 и /i(y, z) = b\. Симметрично, и.(у,х) = b\. Противоречие с тем, что нашлись две вершины, не образующие хорошую пару с у. Теперь степень любого //-подграфа равна Ь\ — 2. Действительно, в противном случае степень некоторой вершины d в /i-подграфе [х] П [у] равна Ь\ — 1 и у = х. Тогда х1 U у1 содержит точно 36i — 3 из [d\, и [d] содержит 3-коклику. Заметим, что Г содержит 3-коклику, так как \|AU;U\| > 0. Если Ъ\ > 2, то по теореме из [2] Г является треугольным графом или графом Шлефли (диаметр графа икосаэдра равен 3). Противоречие с тем, что указанные графы кореберно регулярны. Значит, Ь\ = 2. Как показано в [29], реберно регуляр- Рис. 1: Граф Р(3) ный граф без 3-лап диаметра 2 либо сильно регулярен, либо изоморфен графу Р(т) для некоторого т (граф Р(3) показан на рис. 1). Так как число вершин v графа Г равно 12, то случай Р{т) не возникает. Противоречие с тем, что Г не является кореберно регулярным графом. Итак, v < 2k + 3, 6 < 3. Пусть х,у - несмежные вершины. Заметим, что \|AXJ/\| минимален, если (х,у) - хорошая пара. Теперь по утверждению (3) леммы 2 \AXjy\ > b\ + 8 — 3. Если х,у - несмежные вершины из Л, то AXjlJ содержит и, w и [и] П [w], поэтому пара (х, у) не является хорошей. Лемма 1.1.4. Выполняются следующие утверждения: (1) граф Г не содержит такой 3-коклики, что любые ее две вершины образуют хорошую пару; (2) найдутся такие несмежные вершины х, у, что степень некоторой вершины d в подграфе [х] П [у] не меньше Ь\ — 1; (3) параметр Ь\ больше 3; (4) если х - вершина из [w] — [и], образующая хорошую пару си, и [х] содержит 7 вершин из [и] П [w], то х смежна с j + 1 вершинами из Л. Доказательство. Пусть {u,w,x} - такая 3-коклика, что любые ее две вершины образуют хорошую пару. Так как г; < 2А; + 3, то \|Л\| < &ь С другой стороны, [х] содержит по Ъ\ — 1 вершин из [и] и из [w] и &i вершин из Л, противоречие. Утверждение (1) доказано. Допустим, что для любых несмежных вершин х, у степень каждой вершины в подграфе [х] П [у] равна &i — 2. Это преположение выполняется, в частности, в случае Ъ\ = 2. Тогда к = 4, Л = 1 и все //-подграфы регулярны степени 0. По утверждению (4) леммы 1.1.2 [d] С xL\JyL для любых несмежных вершин х,у Е [d]. Отсюда Г не содержит 3-лап. Повторив рассуждения из доказательства леммы 1.1.3, получим противоречие. Утверждения (2) и (3) доказаны. Пусть вершина х из [w] — [и], образующая хорошую пару с и, смежна с 7 вершинами из [и] П [w]. Тогда [х] содержит &i — 1 — 7 вершин из [и] — [w] и 7 + 1 из Л. Лемма 1.1.5. Если Ъ\ = 4, 5 = 1, то выполняются следующие утверждения: (1) если [w] — [и] содержит такую вершину х, что (и,х) - хорошая пара, то [х] пересекает [и] П [w]; (2) для любой хорошей пары (u, w) подграф AUtW состоит из двух смежных вершин; (3) для х Е [w] — [и] подграф [х] пересекает [и] П [w]. Доказательство. Пусть Ъ\ = 4, 5 — 1. В этом случае Л = {у, z] , А; = 10, Л = 5 и v = 21. Пусть [w] — [и] содержит такую вершину ж, что (и,х) - хорошая пара и [х] не пересекает [и] П [w]. Тогда можно считать, что [х] П Л = {г/}, и [w] — [и] содержит единственную вершину х, не смежную с х. Заметим сначала, что если некоторая вершина d из [w] — [и] образует хорошую пару с и, то [d\ содержит не более одной вершины из [и] П [w]. В противном случае по утверждению (4) леммы 1.1.4 [d\ содержит не менее 3 вершин из Л и 8 > 2, противоречие. Если (и, z) - хорошая пара, то [z] содержит 6 вершин из [w] и у. В этом случае [и] содержит единственную вершину а, не принадлежащую [w] U [я] U [z]. Теперь АЩ2 = {x,w} и [и] — [z] = {a} U ([и] П ([х] U [w])). Число ребер между [z] и ^(z) равно 40, причем fi(z,x) = fi(z,w) = 6, поэтому z образует хорошую пару по крайней мере с тремя вершинами а\, аг, аз из [и] — [z]. Если <2j смежна с вершиной из [и] Г) [z], то по утверждению (4) леммы 1.1.4 [щ] содержит х, w, противоречие. Значит, щ не смежна с вершинами из [и] П [z] и, без ограничения общности, смежна с w. Но тогда /х(#, z) < 4, противоречие. Итак, fi(u,z) = 4 и [z] П [и] = [и] — ([х] U [w]). Допустим, что [и] — [z] содержит вершину а, образующую хорошую пару с z. Тогда Ла>г пересекает {x,w}, поэтому [и] содержит не менее 4 вершин из [ai] — [z]. Следовательно, [а] П [z] пересекает окрестность вершины из {x,w} — [а], противоречие. Покажем, что [и] — [z] содержит вершину а, образующую хорошую пару с z. Сумма ^i{z,x) + /i(z,w) минимальна, если вершина z смежна с у,х*. Но даже в этом случае /x(z, х) = /j,(z,w) = 5, Au,z = {x,d,w} для некоторой вершины d G [х] П [w] и z образует хорошую пару по крайней мере с двумя вершинами, одна из которых попадает в [и] — [z]. Утверждение (1) доказано. Допустим, что Л состоит из несмежных вершин. Так как Ay,z содержит и, w и [и] П [гу], то fi(y, z) > 6. Далее, ц(у, u) + ii(y, w) = 10, число ребер между [у] и Т2{у) равно 40, то Г2(у) содержит не менее 4 вершин, образующих хорошую пару с у. Можно считать, что (у,д) - хорошая пара для д Е [и] — [w]. Если [д] содержит вершину / из [w] — [и], образующую хорошую пару с у, то вершина из [/] П [д] П [у] не попадает в uL U гу1, противоречие.

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

Цена, в рублях: (при оплате в другой валюте, пересчет по курсу центрального банка на день оплаты)	1425

Скачать бесплатно	23578.doc

Найти готовую работу

ЗАКАЗАТЬ

Обратная связь:

Связаться

Вход для партнеров

Регистрация

Восстановить доступ

Материал для курсовых и дипломных работ

03.11.24 Лексикографический анализ единиц поля

03.11.24 Из истории слова гость и его производных

03.11.24 Семантическое поле гость в русском языке

Архив материала для курсовых и дипломных работ

Ссылки:

Счетчики:

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