Исследование хроматического числа и размера максимальной клики графа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

ПРОСОЛУПОВ Евгений Викторович

ИССЛЕДОВАНИЕ ХРОМАТИЧЕСКОГО ЧИСЛА

И РАЗМЕРА МАКСИМАЛЬНОЙ КЛИКИ

ГРАФА

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Санкт-Петербург 2004 г.

Работа выполнена на кафедре Технологии программирования факультета Прикладной математики - процессов управления Санкт - Петербургского Государственного Университета.

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

доцент Сергеев Сергей Львович Официальные оппоненты: доктор технических наук,

профессор Лузин Сергей Юрьевич

кандидат физико-математических наук, доцент Хитров Геннадий Михайлович

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

Институт прикладных математических исследований Карельского научного центра РАН (г. Петрозаводск)

Защита состоится

it

20" 2004 г. в Xi.

час. на заседании

диссертационного совета К-212.232.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт-Петербургском государственном университете по адресу: 190004, Санкт-Петербург, 10-я линия В.О., д.ЗЗ, ауд .

С диссертацией можно ознакомиться в библиотеке СПбГУ им. A.M. Горького по адресу: Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан " ¡4 " СёИТЛдЦ 2004 г.

Ученый секретарь диссертационного совета,

доктор физ.-мат. наук, профессор

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

Актуальность темы. Теория графов взяла свое начало в работах Л. Эйлера, Г. Кирхгофа, А. Кэли, В. Гамильтона, С. Жордана и затем приобрела широкое распространение в математической среде. Хроматическое число и размер максимальной клики графа, а также напрямую с ними связанные число кликового покрытия и число вершинной независимости графа, используются в большом количестве задач теории графов. Как известно, вычисление каждой из этих функций является КР-трудной задачей. Кроме того, как показано в работах С. Ароры, если эти инварианты не могут за полиномиальное время

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

Из работ Дж. Мыцельского и А.А. Зыкова известно, что хроматическое число не может быть оценено сверху никакой функцией от размера максимальной клики графа. Одним из подходов к оценке этих величин является разбиение отрезка между ними другими функциями, между которыми существует более тесная связь. Функции со значениями, зажатыми межу числом вершинной независимости и числом кликового покрытия, изучались в работах Л. Ловаса, Д.Е. Кнута,

B.Ю. Добрынина.

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

C. ван Нуффелен предположил, что хроматическое число непустого графа ограничено сверху рангом матрицы смежности. Это предположение было опровергнуто Н. Алоном и П. Сеймуром. Позже, этот вопрос изучался в работах А. Разборова, Р. Раза, Б. Спикера, Н. Нисана, А. Вигдерсона, Л. Ловаса, А. Котлова, Б. Коденотти, Г. дел Корсо, Г. Манзини.

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

РОС. '1ЛЦИ0НАЛЫМЯ ЛИОТЕКА ' -'¡«терЛгрг

О* 200,

>//*«тв6

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

Также в работе предложены специальные классы универсальных графов для множества ^рагкрашиваемых графов. Изучению универсальных графов посвящены работы Р. Радо, Дж.А. Бонди, Ф.Р.К. Чунг, Л.Р. Грехема, П.С. Фиптборна, Л. Батта, Дж. Фридмана, Н. Пипенжера, Л. Бабаи, Дж. Спенсера, Дж.В. Муна, В.Е. Алексеева, В.В. Лозина.

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

- развитию методов оценки размера максимальной клики и хроматического числа;

- изучению особенностей функций графа, значения которых зажаты между числом вершинной независимости и числом кликового покрытия;

- рассмотрению возможности введения новых функций с целью получения лучших оценок инвариантов графа и раскрытия неизвестных закономерностей;

- нахождению связей с другими известными задачами комбинаторики.

Научная новизна. В диссертационной работе был получен ряд новых

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

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

числа и размера максимальной клики графа.

Основные положения, выносимые на защиту:

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

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

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

Следствием этого результата является тот факт, что число кликового покрытия не может быть ограничено никаким полиномом от значения

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

5. Показано, что равенство а(С?) = »^(С) влечет совпадение чисел вершинной независимости и кликового покрытия графа О.

6. Получены результаты, позволяющие оценить число вершинной независимости и число кликового покрытия графа мипимальпую размерность его ортонормального помечивания.

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

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

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

конференциях «Процессы управления и устойчивость» факультета прикладной математики и процессов управления (г. Санкт-Петербург, 2001-2004 гг.), на Российской конференции «Дискретный анализ и исследование операций» DAOR'04 (г. Новосибирск, 2004 г.), на семинаре «Дискретная математика» Санкт-Петербургского отделения Математического института им. В.А. Стеклова (г. Санкт-Петербург, 2004 г.), а также на семинарах кафедры технологии программирования факультета ПМ-ПУ СПбГУ.

Публикации. По результатам выполненных исследований опубликовано 5 работ.

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

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

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

Первая глава посвящена изучению инвариантов графа, определяемых посредствам ранга связанных с графом матриц, значения которых оказываются зажаты между значениями числа вершинной независимости а((7) и числа кликового покрытия х(С). Эта глава содержит наибольшее количество значимых результатов.

В параграфе 1.1 приводится определения всех рассматриваемых функций отрезка [«((г), и известные результаты относительно этих инвариантов.

Приведем часть из них. Пусть

Л>-о(С) = {Л" : X б X Ъ 0}, Л^в) = {Х :Хе Л{в), X > 0}, С(в) = [X : X 6 -4(6), X = В ■ Вт, В > 0} С Л-о(С) П Л>о(С7).

Определим функции

r(G) — min rank(X), r+(G) = min rank(A'), X€A(G) хеи>о(с)

d(G) = mm rank(X), d+(G) = min rank(X).

Для любого графа G верна следующая система неравенств:

a(G) < r(G) < d(G) < d+(G) = *(G), a(G) < r(G) < r+(G) < x(G).

Рассмотрим множество матриц

A'(G) = {X : X € Rnxn, X„ jt 0, A(G)4 = 0 => Xv = 0,t ф j).

Для любого множества матриц B(G), такого что C(G) С B(G) С A'{G), значение функции g(G) = min^€e(c) rank X оказывается зажато между значениями функций a(G) и x(G).

Теорема 1 Для любого графа. G

a(G) = r+(G) a(G) — x(G)

Теорема 2 Если в графе G нет двух циклов длины 4 без хорд и с общим ребром, то

a (G) = t(G) => a(G) = *(G).

В параграфе 1.2 рассмотрен пример графа, удовлетворяющего a(G) = d(G), a(G) < x(G). Рассмотрим систему векторов

S = {a, bltb2, b3, Ci, c2, c3, di, d2, d3, ei, e2, e3},

где a = (1,1,1)т, Ьг = (0,1, —1)T, b2 = (1,0,-1)T, b3 = (1,-1,0)T, c, = (0,1,1)T, c2 = (1,0,1)T, c3 = (1,1,0)T, di = (1,-1,-1)T, d2 = (1,-1,1)T, d3 = (1,1,-1)T, в! = (1,0,0)T, e2 = (0,1,0)T, e3 = (0,0,1)т. Построим по ней граф Г = Г(5) следующим образом: V(r) = S, {«,f} € Е(Г) -i4> u-v^0.

Лемма. Для графа Г выполнены следующие равенства- а(Г) = ¿(Г) = 3, г+(Г) = х(Г) = 4.

Таким образом, теорема 1 не может быть обобщена на заменой функции r+(G) значениями r(G) или d[G). Согласно теореме 2, если в графе нет двух

циклов длины четыре без хорд и с общим ребром, то о (С) = г(б) влечет <*((7) = х(С). Таким обратом, пообходимой особенностью графов, для которых это не выполняется, является наличие в них указанной структуры. В графе Г это, например, циклы {а, с>г, 63, е2, а} и {а, 02,61, е2, а}. Определим ¿>1 = {(1)} и для любого г = 1, со

Я+1 = {(*, о) I х е 5,} и {(г, 1) I X е 5,} и

и {(х, -1) | X е 5,} и {е,+1 = (0,... ,0,1)}.

В частности 5з = 5. Множество 5, представдяет собой максимальное по включению множество ненулевых, попарно неколлинеарных векторов из К*, компоненты которых принадлежат множеству {—1,0,1}. Так же как раньше был построен граф Г по системе векторов Б, построим по мпожеству векторов граф Г, = Г(5е). Г1 — отдельная вершина. Граф Г2 изоморфен циклу С4. Графы связны и показано, что л(Г4) = й(Гв) =

Лемма. Для любых 4 > 3 выполняется неравенство х(Г() — а(Г() > [|]. Теорема. Для любого к существует такой связный граф <7, что а(в) = (¡(С!) и <*{С) + к<х{С).

Тем не менее, поскольку известно, что число кликового покрытия может быть ограничено через минимальную размерность ортонормального помечиванияй(С), разрыв между и х(С) при условии а(С) = ¿(С) не столь произволен, как в общем случае.

В параграфе 1.3 рассматривается, как проблема оценки хроматического числа через рапг графа связана с оценкой числа кликового покрытия через функцию г+(С).

'Утверждение. Для любого графа С? выполняется следующее неравенство: Х(С) - гапк(С) < х(С) - г, (С) + 1.

Следствие. Для любого графа <7 верно, что г+(С) = х(С*) влечет Х(С?) < гапк(0 + 1.

Следствие. Для любого графа в верно, что а((?) = влечет

Х(С) < гапк(С) + 1.

Таким образом, любая оценка снизу на разницу между рангом графа и его хроматическим числом будет также оценкой снизу на разность между г+(<7) и Х(С). С другой стороны, каждая оценка сверху на разностьх(<5)—г+ (С), которую

удастся получить потенциально даст возможность оценить хроматическое число x(G) через ранг матрицы смежности графа G.

Теорема. Если функция x(G) ограничена сверху значением /(г+(С)) для любого графа G, то для любого графа выполняется неравенство x(G) < /(rank(G) + 1). Следствие. Функция x(G) не может быть ограничена сверху никаким полиномом от r+(G).

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

AZ(G) = {X : X б .4(G), xfJ е Z, i,j = M}, Al0{G) = {X : Л" G A>0{G), xtJ 6 Z, i,j = T^}, ^o(G) = {X : X e Aat(G), x,j e Z, i,j = 1^}, CZ(G) = {X: Xe C(G), xw £ Z, i,j = T^I}, Alo,>o(G) = ^о(С)ПЛ|0(С) Э CZ(G).

Определим функции cF и как минимальные размерности ортонормального помечивания графа соответственно векторами, компоненты которых целые числа, и векторами, компоненты которых целые неотрицательные числа. Утверждение. Для любого графа G выполняются следующие четыре равенства:

dz(G) = d+(G) = min rankX = min rankX = min rank X.

ХеЛ|0(С) xen|0ij0(G) XecHG)

Теорема. Для любого графа G выполняется, что x(G) = d\{G). Следствие. Если у графа G существует неотрицательное ортонормальное помечивание размерности t, то у G существует ортонормальное помечивание, сопоставляющее каждой вершине орт пространства R'.

Определим функцию Iх (G) следующим соотношением: r^G) = ттШ!((;) rank X. Очевидно, r(G) < rz(G) < *(G). Теорема. Для любого графа G a(G) = rz(G) влечет a(G) = x(G)

Эта теорема является аналогом результата 1. Поскольку отношение между функциями r+(G) и Iх неизвестно, остается неясным, является ли какое-то из этих двух утверждений сильнее другого, или они дополняют друг друга.

Далее рассмотрим еще одну новую функцию. Будем считать е е [0, |], <5 - sine.

Определение. Назовем отображение

Л : V{G) R*

е-ортонормалъпым помечиванием графа G размерности к, если 1- \hb>)\ = 1 для всех V е V(G),

2. Угол (/e(i.'t), fc(v})) отличается от | не более чем на е, если {ut) Vj} £ E(G).

Можно показать, что условие 2 в определении выше эквивалентно условию:

2'. !/,(«,) • /„(!>,)| < <5, если К»,} i E(G). Будем называть минимальной размерностью е-ортонормального помечивания графа G такое минимальное целое число dW (G), что существует е-ортонормальное помечивание графа G размерности ¿И (С). Рассмотрим множества п х п матриц.

AC(G) = {Х\Х = ХТ, (1 +0)1 - (1 - 5)A(G) — SJ < X < < (l-5)/ + (l-<5M(G) + <5J}, ^.0(G) = {X I X € ДЕ(С), X ь 0}. Утверждение. Для любого графа G

dH(G) = min{rankJf | X е A%0{G)}.

Лемма. Пусть для графа G выполнено неравенство d'^(G) <2 ив этом графе присутствуют цикл длины fc = 2- i + l,i>0. Тогда £ >

Следствие. В графе G с d'e'(G) <2 не может быть треугольников, если е < f, и могут быть нечетные циклы любой длины, если е > |.

Теорема. Пусть граф G таков, что d'E'(G) = 2. Тогда любой подграф Н графа G с не более чем — 1 вершинами является двудольным.

Следствие. Пусть граф G таков, что (G) = 2. Тогда любой подграф II графа G с не более чем f^] — 1 вершинами удовлетворяет неравенству х(#) < 2.

Пусть М(п, <f) — максимальное число векторов в пространстве R", угол между которыми попарно не меньше <£>.

Теорема. Для любого графа G и любого 0 < е < % eeptw неравенство a(G)<M(d'l(G), f-e).

Следствие. Для любого графа G имеет место неравенство a(G) < t^J)^, где т„ — контактное число пространства IV1

Теперь используя известные оценки сверху для величин M(n,yj) и т„, можно получать оценки для a(G) через <fM(G) и е.

Вторая глава диссертации посвящена изучепию свойств трех определенных в ней операций над графом. В параграфе 2.1 вводятся определения операций и рассматриваются их самые базовые свойства. Пусть G — обыкновенный граф с множеством вершин V(G) и множеством ребер E(G).

Определение. Определим opj(G) как граф с множеством вершин V(opx(G)) = V(G) х {0,1}, и вершины (и, i) и (u,j), смежны тогда и только тогда, когда {и,«} € E(G) ui + j < 1.

Определение. Определим op3(G) как граф с множеством вершин V(op2(G)) = V{G) х {0,1,2}, и вершины (у,i) и (u,j), смежны тогда и только тогда, когда {v, ti} е E{G) и 0 6 {¿, j} или i = j.

Определение. Определим op3(G) как граф с множеством вершин V(op3(G)) = V(G) х {0,1,2,3}, tí вершины (v,¿) и (u,j), смежны тогда и только тогда, когда {»,«} 6 E(G) и {i, j] € {{0,0}, {0,1}, {0,2}, {0,3}, {1,1}, {2,2}}.

Матрица смежности графа op,(G), ¿ = 1,3, определенной нумерацией вершин может быть приведена к виду /4(op,(G)) = Т< ®A(G) или виду j4(op,(G)) = j4(G) ® Т„ 1'де ® обозначает тензорное произведение матриц и

/ \ h 11 Л

(\ (1 1 1 \ 1 М íioo

, „ , Т,= 110, Тз = 10/ 1010 ' V 1 о 1 у

4 ' \ 1 0 0 0 /

В параграфе 2.2 получены оценки значений хроматического числа x(G), размера максимальной клики w(G), числа кликового покрытия x(G) и числа вершинной независимости a(G) графов opj(G), op2(G) и opj(G), а также приведены бсскопсчпыс последовательности графов, па которых оценки достигаются.

Очевидно ИоР1(С))| = 2 • |У(С)|, |£(оР1(С))| = 3 • |£(С}|, |К(ор2(С))| = 3 ■ |К(С)|, |Б(ор2(С))| = 7 • |Е(0)|, 1^(оРз(С))| = 4 • |К(С)|, |Я(ор3(С))| = 9 • |Е(С)|, гапк(оР1(а)) = 2гапк(С), гапк(ор2(С)) = 3гапк(<3) и гапк(ор3(С)) = 4гапк(С). Лемма. Графы ор^С), ор2(С) и ор3(С) удовлетворяют равенствам:

Несмотря на то, что операции оР1(), ор2() и ор3() сохраняют размер максимальной клики и хроматическое число, они не сохраняют свойство графа быть совершенным. Рассмотрим, например, граф С, представляющий собой цикл Съ с одной хордой. Нетрудно убедиться, что С совершенный граф, а графы оР1(С), ор2((7) и орз(С) содержат цикл С$ в качестве подграфа и, следовательно, совершенными не являются. На рисунке 1 приведен вид графа ор1(С), цикл Сд в нем изображен пунктирной линией.

Рисунок 1: Получение несовершенного графа из совершенного с помощью операции ор1().

Пусть «(С) — число изолированных вершин, а Шс(С) — терм ранг графа Д.

Х(0Р ,(С)) = Х(С), „(ор 1(С)) = ы(С); х(ор2(С)) = х(О), Цор2(С)) = ЦС); х(оРз(С)) = Х(С), Цор3(С)) = и(С).

а,

е

Ь,

Теорема, Для любого графа С верна система неравенств

тах{2а(С),п + ¿(С)} < а(оР1(С)) < х(оР1(С)) <2п- Як(С).

Причем каждая из оценок является точной. Теорема. Для любого графа С верна система неравенств

3а(в) = а(ор2(в)) < х(ор2(С)) < тт{ЩС,), 2п - Юс(С) + *(С)}.

Причем каждая из верхних оценок является точной. Теорема. Для любого графа С верна система неравенств

тах{4а(С), п + вф) + 2а(<7)} < а(ор3(С)) < х(ор3(С)) < 2п - Юс(С) + 2х(С).

Причем каждая из оценок является точной.

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

В параграфе 3.1 изучаются свойства матриц {Т®*}, Т = Т1,Т2,Тз, которые затем используются для доказательства универсальности построенных классов графов.

В параграфах 3.2, 3.3, 3.4 строятся классы универсальных графов. Построим последовательность графов следующим образом

Граф является 2-хроматическим для любого г = 1, оо. Матрица смежности

Теорема. Граф Рп_\ является универсальным для класса двудольных графов с п вершинами.

Следствие. Пусть граф С0 — непустой двудольный граф. Тогда граф С„_1 = ор"_1(Со) является универсальныл< для класса двудольных графов с п вершинами.

Коэффициент асимптотической оптимальности последовательности универсальных графов 14 относительно множества графов К показывает во сколько раз длина двоичной записи номеров вершин универсального графа определяющих конкретный граф (7 из класса К, длиннее такой записи

= К2, = орЛД), » = 0, оо.

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

Построим последовательность графов следующим образом: пусть ¿ > 2,

Я^ = Ки Я« = ор2(//«), г = б^о.

Граф Я,(Ч является ¿-хроматическим для любого г = 1,оо. Матрица смежности графа Я,«' имеет вид Л(Я,(0) = (7, - I,) ® Т|". Здесь обозначает * х < матрицу из одних единиц, а /( — единичная txt матрица. Граф Н® имеет порядок 4 • 3*. Теорема. Пусть I € Ъ, 4 > 2. Гра<£ Я^ является универсальным на классе ¿-раскрашиваемых графов с не более чем п вершинами.

Следствие. Пусть { 6 Ъ, £ > 2, и пусть для графа йо выполняется а(Со) = х(Со) = Тогда граф Сп-1 = ор2-1(Со) является 1-хроматическим универсальным графом для класса 1-раскрашиваемых графов с п вершинами.

Коэффициент асимптотической оптимальности семейства {Я,'1'} относительно класса ¿-раскрашиваемых графов равен .

Построим семейство графов следующим образом: пусть ¿ > 2,

4'' = Ки 4?+1=0 Р1(/4?), = 0Рз(4?)> ¿ =

Граф ¿г''' является ¿-хроматическим для любого г = 1,оо. Матрица смежности графа р® приводима к виду = (,/, — /¡) ® при четном гик виду

Л(Ь[1)) = (Л - /() ® {,_1)/2 ® Тх при нечетном. В графе £ - 2' вершин. Утверждение. Дня любого » € 2, г > 0, Ь'2' изоморфен графу Таким образом, семейство графов можно считать обобщением

последовательности {Р,}.

Теорема. Пусть I £ 2, ! > 2. Граф Ь^ ('-'>1 1 явЛяется универсальным на классе ¿ -раскрашиваемых графов с не более чем п вершинами.

Доказано, что коэффициент асимптотической оптимальности семейства относительно класса ¿-раскрашиваемых графов равен четырем, что дополняет картину обобщения последовательности {Р,}.

В заключении описаны исследовательские проблемы вытекающие из результатов диссертационной работы.

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ

РАБОТЫ:

1. Просолупов Е. В. (0,1)-матрицы, содержащие в качестве подматрицы любую (0,1)-матрицу заданного размера // Процессы управления и устойчивость: Труды XXXII научной конференции студентов и аспирантов факультета ПМ-ПУ. — СПб: ООП НИИ Химии СПбГУ, 2001, с. 293-296.

2. Просолупов Е. В. О дублировании вершин графа // Деп. ВИНИТИ, №482-В2004. 36 с.

3. Просолупов Е. В. О дублировании вершин двудольных графов // Процессы управления и устойчивость: Труды XXXIII научной конференции студентов и аспирантов факультета ПМ-ПУ. — СПб: ООП НИИ Химии СПбГУ, 2002, с. 414417.

4. Просолупов Е. В. Функции, определяемые в терминах ранга матриц, связанных с графом // Процессы управления и устойчивость: Труды 35-й научной конференции аспирантов и студентов. СПб.: Изд-во С.-Петерб. ун-та, 2004, с. 490-494.

5. Dobrymn V., Pliskin M., ITosolupov E. On the functions with values from [<*(<?), x(G)] // Electron. J. Combinat. 11 (2004) N5, 5pp.

Подписано к печати 03.09.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 усл.пл. Тираж 100 экз. Заказ 3331. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

1166 46

Введение

0.1 Базовые понятия и обозначения

0.2 Функции из интервала [a(G),x(G)].

0.3 Обзор данной работы

1 О функциях интервала [a(G)&{G)\

1.1 Свойства системы функций интервала \a{G)^x{G)).

1.2 О разрыве между d(G) и x(G).

1.2.1 Введение.

1.2.2 Пример графа, для которого a(G) = d(G) < x(G)

1.2.3 Обобщение примера.

1.3 О разрыве между r+(G) и x(G)

1.4 Новые функции интервала [a(G),x(G0].

1.4.1 О целочисленном ортонормальном помечивании графа.

1.4.2 Об е-ортонормальном помечивании графа.

1.4.3 Оценка числа вершинной независимости через минимальную размерность £-ортонормального помечивания

2 Свойства трех операций над графом

2.1 Определения и основные свойства.

2.1.1 Определения операций.

2.1.2 Матрица смежности ^-хроматического графа

2.2 Оценки значений инвариантов графа при применении операций ор1(), ор2() и ор3()

2.2.1 Размер максимальной клики и хроматическое число

2.2.2 Число вершинной независимости и число кликового покрытия.

3 Об универсальных i-раскрашиваемых графах

3.1 Свойства тензорных степеней матриц Ti, Тг, Тз.

3.1.1 Последовательность {TfA}.

3.1.2 Последовательность {Tffc}.

3.1.3 Последовательность {Tffe}.

3.2 Универсальные графы на классе двудольных графов

3.3 Случай произвольного хроматического числа.

3.4 Обобщение результата об универсальности для операции дублирования вершин графа.

0.1 Базовые понятия и обозначения

Данная работа посвящена изучению графов и связанных с ними матриц. Введем ряд базовых определений, знание которых необходимо для понимания излагаемого материала. Подробнее об основных понятиях теории графов можно посмотреть, например, [30], [10], [3]. По поводу теории матриц можно обратиться к [5], [27], [4].

Под словом граф будем понимать обыкновенный неориентированный граф G = (V,E), где V = V(G) — конечное множество и Е = E(G) — множество неупорядоченных пар различных элементов из V. Число п = \V\ называют порядком графа. Иногда для простоты будем заменять вершины графа их порядковыми номерами, то есть будем считать V(G) = {1,2,., п}.

Вершины и и v графа G называются смежными или соседями, если {и, г;} € E(G). Две вершины графа и и v называют близнецами, если множества их соседей совпадают. Полным называется граф, любые две вершины которого смежны. Полный граф с п вершинами обозначают Кп. Пустым графом Кп называют граф с п вершинами и без ребер.

Дополнением графа G порядка п называют такой граф G, что V(G) = V(G) и E(G) = Е(Кп) \ E{G).

Степенью v вершины графа G называют число ее соседей. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей. Граф G называется ^-регулярным, если степени всех его вершин равны к. Граф называется регулярным, если он ^-регулярный для некоторого к.

Графы G и Н называются изоморфными, если существует биективное отображение ip : V(G) —► V(H), такое что W, v € V(G) {u, v} e E{G) & Mu),<p(v)} e E(H).

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

Граф Н называется подграфом графа G, если V(H) С V(G) и Е(Н) = \ и,v € V(H), € E(G)}. Такой подграф еще называют подграфом, порожденным или индуцированным множеством вершин V(H). Если граф Н изоморфен некоторому подграфу графа G, будем называть Н подграфом G.

Граф F называют остовным подграфом (суграфом) графа G, если V(F) = V{G) и E(F) С E(G). А:-фактором графа G называется его fc-регулярный остовной подграф.

Частью графа G называется такой граф F, что V(F) С V(G), E{F) С | и, v е V(F), {и, г»} б E(G)}. Другими словами, часть графа G — это суграф некоторого подграфа G.

Матрицей смежности графа G порядка п называется такая п х п матрица A{G), i,j-тый элемент которой равен 1, если {i,j} € E(G), и О иначе. Матрицы смежности изоморфных графов совпадают с точностью до одинаковой перестановки строк и столбцов, соответствующей перенумерации вершин графа.

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

Для симметричной матрицы А, будем обозначать G [Л] граф, имеющий ребро между г-той и j-той вершинами, i ф j, тогда и только тогда, когда a^j ф 0. Если А — (ОД)-матрица с нулевой диагональю, G [А] — граф с матрицей смежности А,

Ранг матрицы смежности графа G называют рангом графа G и обозначают rank((7). То есть, rank(G) = гапк(Л(С)).

Будем говорить, что Y главная подматрица матрицы X, если Y такая подматрица матрицы X, которая находится на пересечении строк и столбцов матрицы X с одинаковыми номерами. Нетрудно видеть, что матрица смежности подграфа Н графа G будет главной подматрицей матрицы смежности графа G, если вершины подграфа имеют тот же порядок, что и в графе G.

Множество вершин А 6 V(G) графа G называют независимым, если никакая пара вершин в нем не смежна: Vu,v е А =Ф- {u, v} £ E(G). Число вершинной независимости (неплотность, число внутренней устойчивости) ol{G) определяется как мощность максимального независимого множества вершин графа G.

Раскраской графа называется разбиение множества его вершин на независимые подмножества. Хроматическим числом х(^) графа G называется наименьшее число независимых множеств, в раскраске графа G. Будем называть граф G £-раскрашиваемым (£-дольным), если X(G) < t, и ^-хроматическим, если х(С?) = t. 2-раскрашиваемые графы называют двудольными. Полным двудольным графом KPiQ называют граф порядка р + q с множеством ребер Е = {{гг, г;} | и £ {1,. ,р}, v в (р+ i,.,p + g}}.

Кликой называется полный подграф графа. Размер максимальной клики (плотность) графа G обозначается cj(G). Числом (наименьшим размером) кликового покрытия x{G) графа G называют минимальное число подмножеств в таком разбиении V(G) = V\ U • • • U Vk, что каждое

V{ порождает в G полный подграф, i = I, к.

Нетрудно заметить, что a(G) = cj(G) и x{G) = Также не сложно показать, что a{G) < x(G) и, соответственно, uj(G) < Граф G, для любого подграфа Н которого (включая сам граф) выполняется ui(H) = х(Н) называется совершенным; остальные графы называют несовершенными. Известно, что граф дополнительный к совершенному тоже является совершенным. Таким образом, граф является совершенным тогда и только тогда, когда для любого его подграфа Н (включая сам граф) выполняется ot{H) = х(Ю

Многие матрицы, рассматриваемые в данной работе, являются (ОД)-матрицами. Для упрощения записи нам будут полезны следующие обозначения. Введем множество Е2 = {0,1}. Будем обозначать Е% — множество вектор строк или столбцов размера п, а Е%хт — множество (0,1)-матриц с п строками и т столбцами. Будем обозначать 1п и Jn соответственно единичную матрицу и матрицу, все элементы которой единицы, размерности пхп. Больше о (ОД)-матрицах можно посмотреть в [27].

Пусть А е Е£хт, В е E%xl — (ОД)-матрицы. Знаком ® будем обозначать тензорное произведение матриц. То есть, С = А® В значит, что ahiB аиВ . ahmB ^ 0>2,\В 0,2,2В . . . 0,2,тВ

С = (n-k)x(m-l) 2 &n,iB аП)2-В . аЩТпВ у Известно следующее утверждение относительно тензорного произведения, которое пригодиться нам в будущем.

Утверждение 0.1.1 Пусть А и В — квадратные матрицы. Матрицу А® В перестановкой строк и столбцов можно привести к матрице В ® А. Причем строки и столбцы переставляются одинаково.

Будем обозначать

А®к = А О А ® • • • О А, = (1).

4 V / к

Подробнее о тензорном произведении смотри, например, [4]

Задачу называют задачей в форме распознавания свойств, если ответ на задачу «да» или «нет». Класс задач, сформулированных в форме распознавания свойств, для которых существует алгоритм, дающий ответ на задачу за время полиномиальное от начальных данных, обозначается Р.

Класс задач, сформулированных в форме распознавания свойств, для которых существует недетерминированный алгоритм, дающий ответ на задачу за полиномиальное время, обозначается NP. Задача из класса NP называется iVP-полной, если к ней за полиномиальное время сводится любая задача из класса NP. Задачу называется NP-трудной, если к ней за полиномиальное время сводится какая-нибудь А^Р-полная задача. О классе NP и NP-трудных задачах подробнее можно посмотреть в [6].

Будем использовать обозначения я J = max{n \ п<х,пе Z}, [V| = min{n \п>х,п€ Z}.

0.2 Функции из интервала [a:((2),x(G0]

Хорошо известно, что a{G) < x(G)- В общем случае вычисление обеих этих функций являются NP-трудной задачей (смотри, например, [6]). Более того, известно [37], что в предположении, что P^NP, a(G) и x{G) не могут быть за полиномиальное время оценены с точностью до множителя пе, для наперед заданного е > 0.

Вопрос о равенстве классов Р и NP на сегодняшний день остается открытым. Известны источники, например [32], [29], в которых утверждается, что найдено доказательство равенства P=NP. Тем не менее, пока доказательства этих результатов не получили широкой известности и не будут проверены математическим сообществом, сложно делать какие-либо выводы. Подробнее о NP-трудных задачах смотри [6].

Графы для которых вместе со всеми их подграфами выполняется равенство a(G) = x(G) называются совершенными. Здесь нас больше будут интересовать графы, для которых неравенство является строгим: cn(G) < x(G)- В общем случае разница между значениями этих инвариантов графа может быть сколь угодно велика и значение x(G) не может быть ограничено сверху никакой функцией от a(G) (смотри

П], [71]).

Хорошо известны, например, графы Мыцельского [71]. Рассмотрим произвольный непустой граф G со множеством вершин {ai,.,ara}. Построим граф G\ со множеством вершин {ai, .,an, &ъ .,bn,c}, в котором вершины щ смежны между собой так же как в графе G, вершина Ъ{ смежна со всеми вершинами, с которыми была смежна ai в графе G, и с смежна со всеми вершинами bi, г = l,n. Можно показать, что uj(G\) = cj(G), x(Gi) = x(G) + 1- Таким образом, многократно выполняя такое преобразование мы построим последовательность графов с одним и тем же размером максимальной клики и произвольно большим хроматическим числом. Переходя к дополнительным графам получим, семейство графов с одинаковым числом вершинной независимости и произвольным числом кликового покрытия.

Поскольку разрыв между ol{G) и x{G) может быть так велик, представляет интерес возможность разбиения отрезка \a{G), x{G)) на интервалы меньшего размера посредствам других функций и исследование взаимосвязей между этими функциями.

Назовем ортонормальным помечиванием (ортонормальным представлением) графа G размерности к отображение / : V(G) —» такое что

1. |/(v)| = 1 для всех v € V(G),

2. fM • f(vj) = 0, если {vi,vj} $ E{G).

Здесь точка обозначает точечное произведение, то есть, для x = кь • • •, € rk и у = (771,., ту е rk к х' у = Y1 б7*г=1

Обозначим за d{G) минимальную размерность ортонормального помечивания графа G, то есть такое минимальное число d, для которого существует ортонормальное помечивание графа G размерности d.

Хорошо известной функцией интервала [а(С?), является

-функция Ловаса [68]: $ = min max --\ veV(G) (ei • f(v))2 где минимум берется по всем ортонормальным помечиваниям / графа G, а е\ — орт пространства той же размерности, которую имеет /. Ее замечательной особенностью является то, что она вычислима за полиномиальное время, а значит, в случае c*(G) = x(G), за полиномиальное время вычислимы и границы рассматриваемого интервала. Известно ([68], [64]), что эта функция имеет множество эквивалентных определений, а также имеют место следующие неравенства: a(G) < 0(G) < d(G) < x(G),

Введем ряд функций, определяемых в форме g(G) = min rankX, где B{G) некоторое ассоциированное с графом G множество матриц. Рассмотрим следующие множества матриц.

A{G) = {Х : X е Rnxn,X = XTJ- A(G) < X < I + A(G)},

Ah0(G) = {X : X e A(G),X Ъ 0}, A>0{G) = {X : XeA{G),X> 0}.

Обозначения Х>0и1>:0 значат соответственно, что матрица X состоит из неотрицательных элементов и что матрица X неотрицательно определена. Неравенство X < У для двух матриц X и Y выполняется поэлементно.

Известно, что d(G) = min rank(X).

X€Aho(G)

Для доказательства этого факта достаточно заметить, что любая неотрицательно определенная матрица X размерности n х п и ранга г представима в виде X = ZTZ, где Z — (г х п)-матрица. Столбцы матрицы Z для любой заданной матрицы X 6Е будут, таким образом, определять ортонормальное помечивание графа G. Обратно, из векторов ортонормального помечивания графа G можно составить матрицу Z, для которой ZTZ Е A>-o(G). Введем функцию r(G) = min rank(X),

XeA(G)

Несложно видеть, что a(G) < r(G) < d(G).

Ортонормальное помечивание называется неотрицательным, если все компоненты всех векторов, сопоставленных вершинам графа этим помечиванием, неотрицательны. Минимальную размерность такого помечивания обозначим cf+(C?). Можно также показать, что x(G) = d+(G) и, более того, эта функция тоже может быть выражена в терминах минимума ранга на множестве матриц, ассоциированных с графом (смотри [9]): x(G) = d+(G)= min rankpf),

Л €С(Ст) где и

C(G) = {X : XeA(G),X = B-BT,B>0}

C(G) С A>o,to(G) = A>0(G)nAt0(G).

В параграфе 1.4.1 будет показано, как функция x(G) может быть эквивалентно определена через минимум ранга по конечному числу матриц ассоциированных с графом G. Определим функцию r+(G) = min rank(X). x<E.4>o(g)

Тогда несложно видеть, что a(G) < r(G) < d(G), r+(G)<x(G).

Отношение между функциями d{G) и r+{G) остается неясным. В [52] приведен пример графа Н, для которого а(Н) < г+(Я) < х(Я), и доказаны следующие утверждения

Теорема 0.2.1 Для любого графа G, ct(G) = r+(G) влечет a(G)=x(G).

Следствие 0.2.2 Если x{G) < a{G) + 1, то x(G) = r+(G).

Теорема 0.2.1 не может быть обобщена, заменой функции r+(G) функциями r(G) или d(G), так как в [54] показано, что существует граф Г, для которого а(Г) = cf(F) = 3, а х(Г) = 4. В параграфе 1.2 будет показано, что разность x(G) ~ может быть сколь угодно велика даже в том случае, если a(G) = d(G). В [54] также приведена теорема, позволяющая описать класс графов, для которого обобщение возможно.

Теорема 0.2.3 Пусть в графе G нет двух циклов длины 4 без хорд и с хотя бы одним общим ребром. Тогда a{G) = r(G) влечет a(G) =

Следствие 0.2.4 Пусть в графе G нет двух циклов длины 4 без хорд и с хотя бы одним общим ребром. Тогда cx(G) = d{G) влечет a(G)=x(G).

Интересно изучить, как связь между функциями х и r+(G) влияет на другие задачи связанные с оценками инвариантов графа с помощью ранга связанных с графом матриц. Широко известна задача ограничения хроматического числа через ранг графа. В работе Хоффмана, [61], [62], неявно содержится оценка на хроматическое число: существует фиксированная функция /, такая что x(G) < /(rank(G)). Определение, является ли некоторая функция от rank(G) точной верхней оценкой для x(G), играет важную роль для разрешения гипотезы Ловаса и Сакса [69] из области коммуникационной сложности. О связи ранга с задачами коммуникационной сложности можно посмотреть в работах [72], [51].

Ван Нуффелен [73] в 1976 выдвинул гипотезу

Предположение 0.2.5 Для обыкновенного графа G, отличного от Кп верно x{G) < rank(G); более того, xiP) = rank(G) = к тогда и только тогда, когда все неизолированные вершины порождают полный k-долъный граф.

В пользу этого предположения говорило, что известны классы графов, например, совершенные графы, для которых оно верно [35], [60]. В 1988 оно было переоткрыто компьютерной программой Graffiti [56].

В 1989 эта гипотеза была опровергнута Алоном и Сеймуром [34]. Они привели пример графа с хроматическим числом 32 и рангом 29. Позже Ройле в [81] обобщил пример Алона и Сеймура, рассмотрев семейство графов Gj с 24j+2 вершинами, j > 0, для которых rank(Gj) = 24j+1 - 22j + 1, X(Gj) = 24j+1.

Таким образом, x(Gj) ~ rank(Gj) = 22j — I.

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

Раз и Спикер [79] доказали, что x(G) не может быть ограничено сверху никаким полиномом от rank(G). Нисан и Вигдерсон [72] указали семейство графов, для которых x{G) = (rank(G))5, где 6 = Sl(log rank(G))log32.

В параграфе 1.3 будет доказано, что

X(G) - rank(G) < x{G) - r+(G) + 1.

Это дает возможность оценить разность x(G) — rank(G) через x(G)—r+(G) и наоборот. Очевидно, например, что в случае r+(G) = x(G) x(G) < rank(G) + 1.

Там же будет доказано, что, если функция x(G) ограничена сверху значением f(r+(G)) для любого графа G, то x(G) ^ /(rank(G) 4-1). То есть, любая оценка числа кликового покрытия через значение r+(G) влечет существование оценки хроматического числа через ранг графа того же порядка. Следовательно, функция x(G) не может быть ограничена никаким полиномом от r+(G).

При рассмотрении оценок хроматического числа графа в терминах ранга его матрицы смежности, достаточно рассматривать случай графов не имеющих близнецов, поскольку удаление одной из пары вершин-близнецов не влияет ни на хроматическое число, ни на ранг. В статье [66] Котлов и Ловас показали, что для графа без близнецов G число вершин графа п = 0{2гапк((?)/2). Там же они приводят пример, показывающий, что указанная граница достигается.

Наилучшей известной автору оценкой хроматического числа графа в терминах ранга является оценка указанная Котловым в [65]: x(G) = 0(Дгапк(с)), где А — трансцендентное число чуть меньше, чем

4 3'

В работе [58] хроматическое число ограничено через другую функцию, выраженную через ранг — терм ранг графа Rk(G) [75],[82]. Терм ранг Rk(G) определяется как максимальное число ненулевых элементов в матрице смежности графа G, стоящих в различных строках и столбцах. Эквивалентно терм ранг, можно определить как максимальный ранг достижимый на вещественной пхп матрице имеющей 0 в каждой ячейке, которая имеет нулевое значение в матрице смежности A(G) графа G. Легко видеть, что rank(G) < Rk(Gr) < |V((j)|. Для терм ранга можно привести алгоритмы, вычисляющие его за полиномиальное время [55]. В [58] используется следующее определение.

Определение 0.2.6 2-фактором графа G назовем набор непересекающихся простых циклов, покрывающих все вершины графа G; здесь отдельное ребро считаем циклом длины 2.

Это определение отличается от понятия 2-фактора в смысле определения, приведенного в параграфе 0.1, согласно которому 2-фактор должен состоять только из циклов. Тем не менее, здесь нам будет удобно пользоваться определением 0.2.6. В его рамках сформулировано следующее утверждение [84]:

Утверждение 0.2.7 Для любого графа G с непустым множеством ребер, Rk(G) совпадает с максимальным числом вершин в подграфе Н графа G таком, что у Н есть 2-фактор.

Действительно, если у графа Н существует 2-фактор, то множество V(H) распадается на подмножества ., V&, |V*| > 1, где вершины множества V* образуют цикл, если |V*| > 2, и соединены ребром, если \Vi\ = 2. Тогда в матрице смежности графа Н присутствует диагональ из ненулевых элементов. Таким образом, если подграф Н графа G имеет

2-фактор, то Rk(<?) > \V(H)\.

С другой стороны, так как в матрице смежности графа G существует Rk((7) ненулевых элементов стоящих в разных строках и столбцах, выбрав в качестве V(F) множество вершин, соответствующих позициям этих ненулевых элементов в A{G), получим подграф F с Rk(G) вершинами, матрица смежности которого содержит ненулевую диагональ. Тогда у F существует 2-фактор, состоящий из циклов и ребер соответствующих циклам перестановки ненулевой диагонали A(F). Следовательно Hk(G) < \V(H)\.

Фишкинд и Котлов [58] доказали, что для любого графа с ребрами верна верхняя оценка для хроматического числа x{G) < Rk(Cx), причем равенство достигается тогда и только тогда, когда граф G представляет собой (не считая изолированных вершин) полный граф Кп или звезду

Там же они показали, что для графа без близнецов Rk(G) = 0{у/2rank(G)) (поскольку Rk(G) < n, a n = 0(\/2rank(G)), как показано в [66]); причем эта граница точна. Действительно, для любого положительного целого числа г можно построить граф Gr следующим образом: соединить полный двудольный граф К-гр и пустой граф Кг таким образом, что разные вершины из одной и той же доли К2г,2г имели различное множество соседей в Кг. Тогда матрица смежности такого графа будет иметь вид О J м\

A{Gr)= J О М , кмт Мт О J где М — 2Г х г матрица строки которой представляют все возможные (ОД)-строки длины г, J — 2r х 2Г матрица из одних единиц, О — матрица из нулей нужного размера. Поскольку в A(Gr) нет одинаковых строк, граф Gr не содержит близнецов. rank(C?) <2 + 2г, поскольку 2 + 2г — сумма рангов блоков A(Gr)- И, наконец, Rk(G>) > Rk(/sr2r,2r) = 2-2г, из чего следует, что Rk(Cr) > 2rank^/2 = у/2т&пЦСг).

Этот результат позволяет предположить, что оценка rank(C?) x(Q) < Rk(G) = 0(у/2 ), не поможет улучшить оценку X(G) = 0(Дгаиз [65], где Д < f < у/2.

В параграфе 2.2.2 будет показано, как для введенных в главе 2 операций ор^), ор2(), ор3() с помощью терм ранга графа G может быть оценено число кликового покрытия графа op(G). Доказано, что x(oPl(G))<2n-Rk(C), x(op2(G)) < min{32n - Rk((7) + x(G)}, x(op3(C))<2n-Rk(G) + 2x(G).

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

Утверждение 0.2.8 Если граф G не содержит близнецов, то а (G) < v/2rank(G). Кроме того, существует бесконечное семейство графов без близнецов, для которых равенство достигается.

Действительно, если рассмотреть произвольный граф без близнецов и предположить, что вершины {1,., си((7)} являются независимым множеством, матрица смежности графа примет вид где 0 — ot{G) х a(G) матрица из нулей. Так как в G нет близнецов, все строки М различны. Матрица ранга г не может содержать больше 2Г различных (ОД)-строк. С другой стороны rank(G) > 2-rank(M). Таким образом, a(G) < 2rank<M> < = ^2гапВД.

В качестве примера того, что равенство достигается можно выбрать семейство графов Gr с матрицей смежности где М — 2Г х г матрица, строки которой являются всеми возможными (ОД)-строками длины г. Такой граф получается при соединении пустого графа К у с пустым графом Кг таким образом, чтобы разные вершины К у имели различные множества соседей из Кг. Нетрудно видеть, что в Gr нет близнецов, rank(M) = г и a(Gr) >Т = 2rank<M) = y/2™nk{Gr)

Типичной задачей упаковки в пространстве М. с метрикой t(x,y) является задача нахождения максимальной мощности t(x, у) > s) подмножества в Л4, расстояния между различными элементами которого не менее s (в предположении, что мощность таких подмножеств ограничена).

Пусть 5,п"1 = {х : х 6 Мп, |И| = 1} - сфера в Rn. В качестве метрики выберем D(x,y): D(x,y) = ||rc — у||, ||а:|| = у/(х, х), (х,у) = ЕГ=1 ^iVi- Обозначим М{щв) = M(Sn~\D(x, у) >2 sin(<9/2)) — максимальное число точек в таком множестве А С S'n1, что сферические шапки углового радиуса | описанные вокруг различных точек Л не пересекаются.

Поскольку 1 — ^D2(x, у) = (х,у), несложно убедиться, что условие D(x,y) >2sin(0/2) эквивалентно условию (х,у) < cos 9. Тогда М(п, в) = M(Sn~1, (х, у) < cos в). Другими словами, М(п,в) — максимальное число векторов в пространстве М™, угол между которыми попарно не меньше 9. В параграфе 1.4.2 будет введена функция Se\G) и в 1.4.3 будет показано, что для любого £ G [о, |).

Частным случаем задачи вычисления М(п,9) является задача о контактном числе пространства Rn [13], [28]. Контактным числом пространства Rn называют максимальное число шаров единичного радиуса с непересекающимися внутренностями, касающихся единичного шара пространства; это число обозначается через тп.

Легко показать, что число тп равно максимальному числу единичных векторов, угол между которыми попарно не меньше то есть тп = М (п, . (1)

Таким образом,

G) <тй[Щс) = М (ЖЦС)^) .

В связи с описанным выше для изучения взаимозависимостей между функциями связанными с интервалом [а:(С?), представляет интерес насколько хорошо можно оценить значения М(п, 9) и тп.

Вопросы оценки сверху величин М(п,9) и тп рассматривались в работах [85], [26], [12], [74], [15], [14]. Ранкин [78] нашел значения М(п,9) для 9 G [|>тг]- Для пространств размерности 2, 3, 8 и 24 известны точные значения для тп: т2 = 6, Тз = 12, ts = 240, Т24 = 196560. Совсем недавно Мусин [19] получил точное значение для пространства размерности 4: 74 = 24.

Пусть ро(Х), р+(Х), р-{Х) число нулевых, положительных и отрицательных собственных чисел симметричной матрицы X соответственно. Тогда rank(X) = р+(Х) Л-р-(Х). В [31] Цветкович предложил следующую верхнюю оценку для числа вершинной независимости a(G): a(G) < p0(A(G)) + mm(p+(A(G)),p-(A(G))). (2)

Там же показано, что эта оценка достижима. Например, равенство имеет место для полных графов.

Эта оценка может быть обобщена [8]. Определим множество

G) = {Х\Х е Шпхп, X = Хт, -A{G) <Х< A(G)}.

Так как р+{Х) = р-(—Х) и —X € £ для любого X £ то min(p0(X)+p+(X)) = mm (р0(Х) + mm(p+(X) + Р-(Х))).

А поскольку A{G) G то nun (ро(Х) +Р+(Х)) < po(A(G)) + min(p+(i4(G)),p(A(G))). (3)

Л ££ (G)

Из теории матриц известно следующее утверждение (смотри, например, [18]).

Теорема 0.2.9 Пусть А — симметричная матрица с собственными значениями Ль Хп и В одна из ее главных подматриц с собственными значениями ц\, ., рьт. Тогда справедливы неравенства

Лг > fli > Anm+i, i — 1,772. Улучшим оценку (2).

Теорема 0.2.10 Для любого графа G имеет место неравенство a{G) < тш ШХ) + Р+(Х)). (4)

-Л €c.(G)

Существует бесконечное семейство графов, для которых достигается равенство.

Доказательство. Пусть X С £, Y — главная подматрица матрицы X, стоящая на пересечении строк и столбцов, соответствующих вершинам некоторого наибольшего независимого множества графа G. По теореме 0.2.9, если Ai, ., Ап — собственные значения матрицы X и учитывая, что все собственные значения матрицы Y равны нулю, выполняются следующие неравенства

А* > 0, i = \,a{G).

Следовательно, ol{G) < РоРО +р+(Х).

Достижимость оценки (4) следует согласно (3) из этого свойства оценки (2). ■

По формуле (3) оценка (4) действительно является улучшением оценки Цветковича.

Поскольку при добавлении к любой матрице А единичной матрицы собственные числа увеличиваются на единицу, то min (роРО+р+рО) < min р+(Х). Xe£(G) X€A(G)

Введем функции c(G) = min (рорО +р+Р0),

Л Et((jr) ci (G) = min p+рО.

XeA{G)

Тогда верны следующие неравенства a(G) < c{G) < ci(G) < r(G).

В статье [53] показано что, для любого графа G ct(G) = r(G) влечет a(G) = d(G), а также доказана следующая теорема.

Теорема 0.2.11 r(G) = i & d{G) = г для г < 3.

На данный момент не известны примеры графов, для которых r(G) ф d(G). Можно предположить, что эти функции равны и в общем случае, но доказательства этого на сегодняшний день не получено.

Следствие 0.2.12 r(G) <3 x(G) <

Следствие 0.2.13 d(G) = 4 r(G) = 4.

Следствие 0.2.14 r+(G) = 3 d{G) = 3.

Последнее утверждение не может быть обращено, поскольку [54] приведен пример графа Г, для которого а(Г) = d{Г) = 3, а х(Г) = 4. Следовательно по теореме 0.2.1 г+(Г) = 4.

В статье [53] приведен следующий результат А. Котлова.

Теорема 0.2.15 Пусть щ, .,un — ортогональное помечивание графа G размерности d и пусть — ортогональный базис некоторого линейного пространства L С такой что щ ■ bj > 0 для любых i = I7n и j = TJc. Тогда x{G) <k + 2d~k.

Следствие 0.2.16 Пусть m ш векторов ui,.,un лежат в L. Тогда x{G) < min{A;, т] + min{n — m, 2d~k}.

В частности для любого графа с ребрами можно выбрать ортонормальное помечивание графа таким образом, чтобы k = 1 и т = 0. Следовательно х ^ 2d^~1. Легко показать, что последнее неравенство верно и в случае графа без ребер.

В статье [7] представлен обзор результатов, касающихся функций графа, значения которых лежат в отрезке х(С)], а также предлагается следующая классификация графов с использованием этих функций. Обозначим через G{x} множество графов, удовлетворяющих условию х. Тогда

• Класс G{r(G) = 1} = = G{ полный граф };

• Класс G{r(G) = 2} = G{ дополнительный к двудольному графу };

• Класс G{r(G) = 3} = = G{d(G) = 3} С CG{a(G)<3,x(G)<4};

• Класс G{d(G) = 4} С С G{r(G) = 4};

• Класс G{r(G) = a(G)} = = G{d(G) = a(G)} С

С G{x(G) < 2аЮ~1У,

• Класс (2{г(С?) = ct(G), нет 2-х циклов без хорд с общим ребром} С С G{a(G) = x(G)};

• Класс G{r+(G) = a(G)} = = G{a(G) = x(G)h

В параграфе 1.1 будет приведен наиболее полный список результатов, характеризующих свойства графов в зависимости от значений инвариантов связанных с интервалом [a(C?),x(G9].

Определение 0.2.17 Вершинно универсальным графом для некоторого класса графов К называется такой граф U, что любой элемент К является порожденным подграфом графа U.

Определение 0.2.18 Реберно универсальным графом для некоторого класса графов К называется такой граф U, что любой элемент К является частью графа U.

В области изучения универсальных графов было получено множество результатов. Например, универсальные графы для класса деревьев рассматриваются в [46], [50], [48], [47], [49], [57], для циклов в [42], для графов с п ребрами и планарных графов в [38], для графов ограниченной степени в [40], [41], [59], [33]. В данной работе мы будем говорить только о вершинно универсальных графах и будем называть их просто универсальными графами.

При построении универсальных графов часто рассматриваются универсальные графы с определенными свойствами. Так в [76] рассматриваются сильно симметричные универсальные графы, в [77] представлены универсальные графы, реализуемые конечными группами.

Граф G называется с?)-графом, если G — дольный граф, у которого каждая доля содержит d вершин, fc-дольный граф называется d-универсальным, если среди его подграфов, порожденных какими-нибудь d вершинами из каждой доли, встречается любой (к, с£)-граф. В [2] рассмотрено построение для заданных к и d такого (к, п)-графа, у которого любой подграф, порожденный t вершинами из каждой доли, (/-универсален.

Фундаментальной проблемой является нахождение универсальных графов имеющих минимальное число вершин. В [70] описаны минимальные универсальные графы для класса всех обыкновенных графов. В [63], [45], [36] рассмотрены универсальные графы для планарных графов, деревьев и графов с заданной древестностью. В [39] рассмотрены минимальные универсальные турниры.

В [46] исследована задача оценки наименьшего числа ребер в универсальном графе. В частности рассматриваются графы универсальные для класса всех деревьев с п ребрами.

Класс графов X называется наследственным, если для каждого графа G G X он содержит и все его подграфы. Обозначим за Qn множество всех обыкновенных графов с п вершинами. Рассмотрим некоторый наследственный класс X и обозначим Хп = X П Qn. Граф UXn назовем ^-универсальным для класса X, если любой граф из Хп является подграфом UXn.

Пусть G G Хп. Список номеров вершин графа UXn, порождающих G называют вершинным кодом графа G относительно UXn [16]. Тогда в двоичном представлении вершинный код графа G имеет длину nlog21 UXn |, из чего следует log2 \Xn\<nlog2\UXn\.

Определение 0.2.19 Последовательность универсальных графов UX = {UXn, п = 1,2,.} называется асимптотически оптимальной, если nlog2 \UXn\ lim —----- = 1. n^oo log2 |АП|

В работе [17] рассмотрены асимптотически оптимальные универсальные графы для семейств наследственных графов.

Назовем величину z(X,UX)= lim"'08^"1 n^oo log2 |Xn| коэффициентом асимптотической оптимальности. Она показывает во сколько раз длина вершинного кода графа G относительно последовательности U X больше вершинного кода относительно асимптотически оптимальной последовательности. в [1] показано, что для всякого бесконечного наследственного класса графов X существует энтропия log2 \Хп h(X) = lim п \ п—*оо

5) ' из чего следует, что \Хп\ = 25n2/l(*)+°(n2). Таким образом, для бесконечного наследственного класса графов г(х,их) = lim , = Hm ЭДЩ. (5)

П~*оо ±ПгП[Х) + о(пг) п-юо ПП[Л)

Обозначим через Sij множество всех графов, у которых множество вершин можно разбить на i + j подмножеств таким образом, чтобы i из них порождают полные, a j — пустые подграфы. Наибольшее число к для которого наследственный класс X содержит хотя бы один из классов Sij, г + j = к, называют индексом класса X и обозначают с(Х). В [2] установлено, что для любого наследственного класса X 1~ткГУ с(л)

Определение 0.2.20 Семейство К конечных графов имеет схему k-помечивания смежности, если существует полиномиальная машина Тьюринга Т и функция /, сопоставляющая вершинам каждого графа G G К различные метки длины не более A:logn бит такие, что для любых двух меток вершин графа G G К машина Т определит смежны ли вершины, которым соответствуют метки, не прибегая к глобальной информации.

В [63] исследована связь между схемами помечивания и универсальными графами. Там доказана следующая теорема:

Теорема 0.2.21 Если у семейства графов К есть схема k-помечивания смежности, то для этого семейства существует универсальный граф размера пк, который можно построить за полиномиальное время.

Схемы помечивания смежности, дающие короткие метки были получены для различных видов разряженных графов [44], [86], [83], [67], [87], [43].

В главе 3 будут построены и изучены семейства универсальных графов для класса ^-раскрашиваемых графов с заданным числом вершин. Семейства будут построены с использованием операций над графом определенных и изученных в главе 2. Для каждого заданного числа t будет указана последовательность ^-хроматических графов, каждый из которых является универсальным на классе ^-раскрашиваемых графов с числом вершин ограниченным некоторой величиной от номера универсального графа в последовательности.

0.3 Обзор данной работы

В данной работе рассматриваются некоторые аспекты исследования хроматического числа и размера максимальной клики графа. Работа включает три главы. Глава 1 посвящена изучению различных взаимосвязей между функциями, в определении которых участвует минимум ранга по некоторому связанному с графом множеству матриц, а значения лежат в интервале [a(C?),x(G0]. Построена последовательность графов, иллюстрирующая, что число кликового покрытия может сколь угодно сильно отличаться от числа вершинной независимости даже в том случае, если = d(G). Показано, что x(G) не может быть оценена сверху никаким полиномом от значения r+(G). Более того, для любой функции /, для которой на любом графе выполняется неравенство x{G) f(r+(G)), будет выполнено и

X(G) < /(rank(G) + 1).

Далее доказано, что x{G) = d+(G), где функция d+(G) определяется как минимум ранга по конечному множеству (0,1)-матриц. Получены оценки на число вершинной независимости через функцию которая определена в параграфе 1.4.2.

В главе 2 вводятся три операции над графом ор^), ор2() и ор3() и исследуются их свойства. Показано, что все три операции сохраняют хроматическое число и размер максимальной клики графа. Получены оценки числа вершинной независимости и числа кликового покрытия для графов op1(G), ор2(С?) и ор3(С?) и приведены примеры, позволяющие утверждать, что оценки точны.

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

В заключении перечислен ряд направлений для дальнейшего исследования, интерес к которым вытекает из результатов диссертации.

Результаты, представленные в данной диссертации, ранее опубликованы в [20], [21], [23], [54], [25], [22], [24]. Результаты докладывались на ежегодных конференциях «Процессы управления и устойчивость» факультета ПМ-ПУ СПбГУ в 2001, 2002, 2004 годах; на конференции «Дискретный анализ и исследование операций» (DAOR'04) Новосибирск, 2004; на семинаре «Дискретная математика» Санкт-Петербургского отделения Математического института им.

В.А. Стеклова, 2004; а также на заседаниях кафедры технологии программирования факультета ПМ-ПУ СПбГУ.

Заключение

4.1 Итоги и направления дальнейших исследований

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

В 1.3 показано, что если для графа G выполняется равенство r+(G) = x{G), то Для его дополнения верно, что х(^) < rank(G) + 1. Интересно, можно ли усилить эту утверждение, доказав, что в этом случае x(G) < rank(G). Можно ли показать, что для любого графа G, для которого выполняется гипотеза ван Нуффелена, верно, что r+(G) = x(G).

В связи с теоремой 1.3.9 также важным становится поиск оценок числа кликового покрытия через значение r+(G), поскольку это может помочь в решении проблемы ограничение хроматического числа через ранг графа.

В параграфе 1.1 упомянуты два предположения: Предположение 4.1.1 Для любого графа G r{G) = d{G) и

Предположение 4.1.2 Для любого графа G d(G)<r+(G).

Там же описана их взаимосвязь. Решение о том, являются ли эти предположения верными, дало бы возможность доказать ряд следствий. Например, если окажется, что предположение 4.1.2 верно, пользуясь леммой 1.3.1 и замечанием 1.3.8 по аналогии с теоремой 1.3.9 можно будет доказать следующее

Утверждение 4.1.3 Если для некоторой функции f выполняется, что значение x{G) ограничена сверху величиной f(d(G)) для любого графа G, то x{G) ^ /(rank(C?) + 1).

Другим результатом доказательства предположения 4.1.2 явилось бы то, что число кликового покрытия, в этом случае, было бы ограничено через значение r+(G): x(G) < 2Г+(С?Ь1.

Еще одним вопросом, касающимся функции r+(G), является ее сравнение со значением rz(G). Известно,что r(G) < r+(G) < x(G) и r(G) < rz{G) < x(G).

Согласно утверждению 1.1.8 для любого графа G из a(G) = r+(G) следует a(G) = x(G); по теореме 1.4.6 из a(G) = rz(G) следует a(G) = x{G). Было бы полезно выяснить, являются ли эти функции различными и, если это так, каково соотношение между ними.

Для лучшего понимания взаимосвязи между функциями cn(G), d(G) и х(^) было бы полезно получить точные оценки на число кликового покрытия через число вершинной независимости в случае a(G) = d{G). В параграфе 1.2.3 указана последовательность графов Gi, для которых выполняется a((3j) = d(G{) = Зг и f <*№) < x(Gi).

Оценка снизу на возможную величину разрыва, следующая из этого примера, является линейной. Остается неясным, возможно ли при условии a(G) = d{G) оценить x{G) сверху линейной функцией от a(G).

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

Более подробного изучения заслуживают также вопросы, касающиеся связи значений «(G) и X{G) с функцией <№{G). Результаты, касающиеся этой функции могут позволить получить как новые закономерности, так и более точные оценки на инварианты графа.

Кроме уже определенных можно рассмотреть и другие аналоги функций r(G), d(G), r+(G) и d+(G) определенные через минимум ранга матриц по некоторым множествам. Например можно ослабить условия на матрицы множеств, по которым берется минимум ранга, убрав требование симметричности. Рассмотрим множества

Апз = {X : I- A(G) < X < I + A{G)}, А?0 = {Х.: XeAns,Xh 0}, и функции гпз = min rankX, ХеЛ™ dl13 = min rank X. Тогда несложно получить следующие соотношения: a(G) < rns(G) < r(G) < 2 • rns{G), rn8{G) < dns(G) < d(G) < 2 • dTs{G).

Другие альтернативные функции можно получить усилив ограничения требованием, чтобы нулевые элементы матрицах, по которым берется минимум ранга, за исключением диагонали встречались в тех и только в позициях, где стоят нули в A(G). Можно показать, что такие функции будут отличны от всех рассмотренных ранее и их значения не обязательно будут зажаты между ot{G) и x{G)

Было бы интересно исследовать больше свойств операций орх(), ор2() и орз() и получить лучшие оценки на число вершинной независимости и число кликового покрытия графов op1(Gf), op2(G!) и op3(G).

Не получен ответ на вопрос возможно ли обобщение теоремы 3.2.2 на случай произвольного хроматического числа с использованием графов F® описанных соотношением (37).

4.2 Благодарности

Я хотел бы поблагодарить Сергеева Сергея Львовича, который был моим научным руководителем и помогал мне в том, с чем я к нему обращался;

Добрынина Владимира Юрьевича за поддержку во все время написания диссертации, стимулирующие беседы и содержательные ответы на многочисленные вопросы;

Пономаренко Илью Николаевича за ценные комментарии, которые полностью изменили структуру и сильно повлияли на содержание работы;

Райгородского Андрея Михайловича за большое количество консультаций оказанных мне лично и по электронной почте.

Благодарю Мельникова Леонида Сергеевича за критику стимулировавшую появление примеров более наглядно и просто иллюстрирующих результаты.

Я благодарен факультету прикладной математики и процессов управления Санкт-Петербургского Государственного Университета. Без помощи людей этого факультета я не стал бы тем, кто я есть.

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

1. Алексеев В.Е. Наследственные классы и кодирование графов // Проблемы киберн., 39 (1982), 151-164.

2. Алексеев В.Е. Область значений энтропии наследственных классов графов // Дискретная математика, 4 (1992), вып. 2, 148-157.

3. Берж К. Теория графов и ее применения. М. 1962.

4. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.:Наука. Главная редакция физико-математической литературы, 1984.

5. Гантмахер Ф.Р. Теория Матриц. М.:Наука, 1967.

6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.:Мир, 1982.

7. Добрынин В. Ю. О классификации графов, основанной на минимальном ранге матрицы, ассоциированной с графом // Вестник СПбГУ, принято к опубликованию, 2004.

8. Добрынин В.Ю. Неопубликованное.

9. Добрынин В. Ю. Хроматическое число графа и ранг матрицы // Вестник СПбГУ. Сер. 1. 1995. Вып. 3 (15), стр. 120-122.

10. Зыков А.А. Основы теории графов. М.:Наука. 1987.

11. И. Зыков АЛ. // Мат. сб. 24 (1949), №2, 163 188.

12. Кабатянский Г.А., Левенштейн В.И. О границах для упаковок на сфере и в пространстве // Проблемы передачи информации, т. 14, вып. 1, 1978, с. 3-25.

13. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 1,2. М.: Мир, 1990. 791 с.

14. Левенштейн В. И. Границы для упаковок метрических пространств и некоторые их приложения // Проблемы кибернетики, 40 (1983), с. 44-110.

15. Левенштейн В. И. О границах для упаковок в мерном евклидовом пространстве // ДАН СССР, 245 (1979), с. 1299-1303.

16. Лозин В. В. Вершинное кодирование графов при автоматном декодировании //В кн.: Комбинаторно-алгебраические методы в прикладной математике. Изд-во ГГУ, Горький, 1986, 73-83.

17. Лозин В. В. О минимальных универсальных графах для наследственных классов // Дискретная математика, 9 (1997), вып. 2, 106-115.

18. Маркус М., Минк X. Обзор по теории матриц и матричных неравенств. М.:Наука, 1979.

19. Мусин О.Р. О контактном числе в размерности 4 // Дискретная математика и ее приложения, Москва, 2004.

20. Просолупов Е. В. Методы порождения всех графов с заданными ограничениями на хроматическое число. Дипломная работа. СПбГУ ПМ-ПУ, 2001.

21. Просолупов Е. В. О дублировании вершин графа // Деп. ВИНИТИ, №482-В2004. 36 с.

22. Просолупов Е. В. О дублировании вершин двудольных графов // Процессы управления и устойчивость: Труды XXXIII научной конференции студентов и аспирантов факультета ПМ-ПУ. — СПб: ООП НИИ Химии СПбГУ, 2002, с. 414-417.

23. Просолупов Е. В. О разрыве между минимальной размерностью ортонормального помечивания и размером наименьшего кликового покрытия графа // Вестник СПбГУ, Сер. 1, принято к опубликованию, 2004.

24. Просолупов Е. В. Функции, определяемые в терминах ранга матриц, связанных с графом // Процессы управления и устойчивость: Труды 35-й научной конференции аспирантов и студентов. СПб.: Изд-во С.-Петерб. ун-та, 2004, с. 490-494.

25. Сиделъников В.М. Новые оценки для плотнейшей упаковки шаров в n-мерном эвклидовом пространстве // Матем. сб., 95 (1974), 148-158.

26. Тараканов В.Е. Комбинаторные задачи и (ОД)-матрицы. М.:Наука, 1985.

27. Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. М.: ГИФМЛ, 1958. 363 с.

28. Телъпиз М.И. Личная страница в интернете. http://www.tarusa.ru/ mit.

29. Харари Ф. Теория графов. М.:Мир. 1973.

30. Цветкович Д., Дуб М., Захс X. Спектры графов: теория и применение. Киев: Наука думка, 1984.

31. Шербанов В. А. Полиномиальный алгоритм решения NP-полной задачи поиска наибольшей клики в графе. // Доклады Томского государственного университета систем управления и радиоэлектроники. 2001, 6, с. 121-132.

32. Alon N., Capalbo М., Kohayakawa Y., Rodl V., Rucinski A., Szemeredi E. Universality and tolerance //In 41st Annual Symposium on Foundations of Computer Science (FOCS), 2000, 14-21.

33. Alon N., Seymour P. A counterexample to the rank-coloring conjecture // J. Graph Theory 13 (1989) 523-525.

34. Amin А.Т., Hakimi S.L. Upper bounds for the order of a clique in graph // SIAM J. Appl. Math., 22 (1972), 569-573.

35. Alstrup S., Rauhe T. Small induced-universal graphs and compact implicit graph representations //In 43rd annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, 2002.

36. Approximation Algorithms of NP-hard problems. Edited by Hochbaum D.S., PWS Publishing Company, Boston, MA, 1996.

37. BabaiL., Chung F.R.K., Erdds P., Graham R.L., Spencer J. On graphs which contain all sparse graphs // Ann. discrete Math., 12 (1982), 21-26.

38. Beineke L. W., Wilson R. T. A survey of recent results on tournaments // In: Resent Advances in Graph Theory. Proc. Prague Symp., 1975, 31-48.

39. Bhatt S.N., Chung F.R.K., Leighton F.T., Rosenberg A.L. Optimal simulations of tree machines //In 27th Annual Symposium on Foundations of Computer Science (FOCS), 1986, 274-282.

40. Bhatt S.N., Chung F.R.K., Leighton F.T., Rosenberg A.L. Universal graphs for bounded-degree trees and planar graphs // SI AM Journal on Discrete Mathematics, 2 (1989), 145-155.

41. Bondy J.A. Pancyclic graphs // J. Combinat. theory B, 11 (1971), 80-84.

42. Brodal G.S., Fagerberg R. Dynamic representations of sparse graphs // In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), 1999, 342-351.

43. Chrobak M., Eppstein D. Planar orientations with low out-degree and compaction of adjecency matrices // Theoretical Computer Science, 86 (1991), 243-266.

44. Chung F.R.K. Universal Graphs and induced-universal graphs // J. Graph Theory, 14 (1990), 443-454.

45. Chung F.R.K., Graham R.L. On graphs which contain all small trees // Journal of combinatorial theory, series B, 24 (1978), 14-23.

46. Chung F.R.K., Graham R.L. On universal graphs // Ann. Acad. Sci., 319 (1979), 136-140.

47. Chung F.R.K., Graham R.L. On universal graphs for spanning trees // J. London Math. Soc., 27 (1983) , 203-211.

48. Chung F.R.K., Graham R.L., Coppersmith D. On trees which contain all small trees //In The theory and applications of graphs, John Wiley and Sons, New York, 1981, 265-272.

49. Chung F.R.K., Graham R.L., Pippenger N. On graphs which contain all small trees ii // Colloquia Mathematica, 1976, 213-223.

50. Codenotti В., Del Corso G., Manzini G. Matrix Rank and Communication Complexity // Linear Algebra and its Applications 304 (1-3) (2000), 193-200.

51. Dobrynin V. On the function "sandwiched" between ol{G) and // Electron. J. Combinat. 4 (1997) R19, 3pp.

52. Dobrynin V. On the rank of a matrix associated with graph // Discrete Mathematics, 276 (2004), 169-175.

53. Dobrynin V., Pliskin M., Prosolupov E. On the functions with values from a(G),x(G)] // Electron. J. Combinat. 11 (2004) N5, 5pp.

54. Edmonds J. Systems of distinct representatives and linear algebra // J. Res. Nat. Bur. Standards Sect. В 71B (1976) 241-245.

55. Fajtlowicz S. On conjectures of Graffiti // Discrete Math, 72 (1988) 113-118.

56. Fishburn P. C. Minimum graphs that contain all small trees // Ars Combinat., 25 (1985), 133-165.

57. Fishkind D. E., Kotlov A. Rank, term rank, and chromatic number // Discrete Mathematics, Volume 250 Issue 1-3, May 2002.

58. Friedman J., Pippenger N. Expanding graphs contain all small trees // Combinatories 7 (1987), 71-76.

59. Graph theory and theoretical physics. Academic Press, New York, 1967.

60. Hoffman A.J. On eigenvalues and coloring of graphs // Graph Theory and Applications, (B. Harris editor). Academic Press, New York, 1970, 79-91.

61. Hoffman A.J., Howes L. On eigenvalues and coloring of graphs II // Ann. New York Acad. Sci., 175 (1970), 238-242

62. Kannan S., Naor M., Rudich S. Implicit representation of graphs // SIAM J. Disc. Math., 1992.

63. Knuth D.E. The Sandwich Theorem // Electron. J. Combinat. 1 (1994) Al, 48pp.

64. Kotlov A. Rank and chromatic number of a graph // J. Graph Theory 26 (1997) 1-8.

65. Kotlov A., Lovasz L. The rank and size of graphs // J. Graph Theory 23 (1996) 185-189.

66. Kaplan H., Milo T. Short and simple labels for small distances and other functions // In 7nd Work, on Algo. and Data Struc. (WADS), 2001, 32-40.

67. Lovasz L. On the Shannon capacity of graphs // IEEE Trans. Inform. Theory, 25 (1979) 1-7.

68. Lovasz L., Saks M. Communication complexity and combinatorial lattice theory // J. Comput. System Sci. 47 (1993) 322-349.

69. Moon J. W. On minimal n-universal graphs // Proc. Glasgow Math. Soc., 7 (1965), 32-33.

70. Mycielski F. // Collog. Math. 3 (1953), №2, 161 162.

71. Nisan N., Wigderson A. On rank vs. communication complexity // Proceedings of the 35th FOCS, 1994, pp. 831-836.

72. Van Nuffelen C. A bound for the chromatic number of a graph // Amer. Math. Monthly 83 (1976) 265-266.

73. Odlyzko A.M., Sloane N.J. A. New bounds on the number of unit spheres that can touch a unit sphere in dimensions // J. of Combinatorial Theory, Series A 26, 1979. p. 210-214.

74. Ore О. U Theory of Graphs (Chapter 7), Amer. Math. Soc. Colloq. Pubis, 38 (1962).

75. Parsons T.D., Pisanski T. Exotic n-universal graphs //J. Graph Theory, 12 (1988), 155-158.

76. Pisanski T. Universal commutator graphs // Discrete Math., 78 (1989), 155-156.

77. Rankin R.A. The closest packing of spherical caps in n-dimensions // Proc. Glasgow Math. Assoc., 2 (1955), 139-144.

78. Raz R., Spieker B. On the log-rank conjecture in communication complexity // Proceedings of the 34th FOCS, 1993, pp. 168-176.

79. Razborov A. The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear // Discrete Math., 108 (1992) 393-396.

80. Royle G. F., Roy A. Notes on Kasami graphs // Submitted to Discrete Math., 2004.

81. Ryser H.J. // Combinatorial Mathematics (Chapters 5 and 6), Carus Mathematical Monographs, №14, Math. Assoc. Amer. (1963).

82. Scheinerman E.R. Local representations using very short labels // Discrete Mathematics, 203 (1999), 287-290.

83. Scheinerman E.R., Ulman D.H. Fractional Graph Theory. A Rational Approach to the Theory of Graphs, Wiley, New York, 1997.

84. Shannon C. Probability of error for optimal codes in Gaussian channel // Bell System Techn. J., 38 (1959), 3, 611-656.

85. Talamo M., Vocca P. Compact implicit representation of graphs //In Graph-Theoretic concepts in Computer Science, 24th international workshop (WG), 1998, 164-176.

86. Zaroliagis C.D., Arikati S.R., Maheshwari A. Efficient computation of implicit representations of sparse graphs // Discrete Applied Mathematics, 78 (1997), 1-16.