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

• Просолупов, Евгений Викторович
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Просолупов, Евгений Викторович

Введение

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 Благодарности

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Просолупов, Евгений Викторович, 2004 год

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.