Оценки числа независимых множеств в графах из некоторых классов

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

История вопроса.

Задача перечисления независимых множеств в графах рассматривается с середины прошлого века и успела стать одним из классических разделов теории графов. Эта задача находит приложения не только непосредственно в математике (комбинаторная теория чисел [17, 21], теория кодирования [14], теоретическая информатика [26]), но и в других областях. Так, например, в теоретической химии параметр i (G), равный числу независимых множеств графа G, называется индексом Мэррифилда-Симмонса [34], а параметр i'(G), равный числу независимых множеств в рёберном графе графа G, упоминается как индекс Хойозы [29]. Ниже приводится краткий обзор работ по перечислению независимых множеств.

Используемая далее терминология в целом согласуется с книгой [13]. Далее рассматриваются только простые неориентированные графы. Подмножество попарно не смежных вершин графа называется независимым. Под максимальными независимыми множествами (м.н. м.) будем понимать максимальные по включению независимые множества. Максимальный размер независимого множества в графе называется числом независимости графа. Будем обозначать через a (G) число независимости графа G, а через n (G) — число вершин в G. Через i (G) и Im{G) будем обозначать число независимых множеств и число м. н. м. в G соответственно. Запись G' ~ G" означает, что графы G' и G" изоморфны.

Одними из первых работ в области перечисления независимых множеств являются статьи [35] и [36], в которых независимо был доказан следующий факт.

Теорема 1 (Р.Е. Миллер, Д. Е. Маллер [35] и Дж.У. Мун, J1. Мозер [36]). Пусть G — граф на п вершинах, имеющий максимальное число м. н. м. среди всех п-вершинных графов. Тогда G является объединением п/3 копий графа Кз при п = 0 (mod3) — объединением графа Кч и (п — 2)/3 копий при п = 2 (mod 3), объединением (п—4) копий графа и либо графа К4, либо двух графов Кч при п = 1 (mod 3).

Экстремальные графы в теореме 1 являются частным случаем графов UKnta, определяемых следующим образом: UKn a суть объединение (а • (п/аJ -}-1) — п) клик размера [п/аJ и (п — а ¦ п/ос) клик размера п/а1. Можно проверить, что n (UKlha) = n, a{UKna) = а.

Теорема 1 обобщалась в различных направлениях несколькими авторами. Так, например, К. Кройтору [25] рассматривал задачу оценки сверху числа м. н. м. в классе всех графов с заданным числом независимости. Дж. М. Нильсен [37] получила достижимую верхнюю оценку числа м. н. м. заданного размера в графах. В обеих указанных задачах максимум достигается на графе UKn>a. Подобные оценки используются для получения оценок времени работы алгоритмов раскраски графов и определения мощности максимального независимого множества (см., например, [26, 37]). Это обеспечивается существованием алгоритмов, перебирающих все м. н. м. в графе за время, пропорциональное количеству м.н. м., умноженному на полином от числа вершин графа [31, 43].

Интерес представляет также получение оценок числа м. н. м. в классах графов, описанных в терминах запрещённых подграфов. М. Гуйтером и Ж. Тузой [30] была получена оценка числа м. н. м. в графах без треугольников (то есть в графах, не содержащих в качестве подграфа). В работе В. Е. Алексеева [1] исследовалось число м.н.м. в графах, не содержащих «большого» паросочетания (объединения графов К2) в качестве порождённого подграфа.

Большое внимание уделяется получению оценок числа независимых множеств в графах с небольшим числом циклов, в первую очередь, деревьев. В работе [40] Г. Продингера и Р. Ф. Тичи были получены верхние и нижние оценки числа независимых множеств в деревьях с заданным числом вершин. Через фп обозначим (п + 2)-ое число Фибоначчи (ф0 = 1, = 2, фп = фп-1 + фп-2 при п ^ 2).

Теорема 2 (Г. Продингер, Р. Тичи [40]). Пусть Т — дерево на п вершинах. Тогда фп ^ г (Т) < 2п~1 + 1, причём равенство ь{Т) = фп имеет, место только в случае, если Т является простой цепью, а равенство г (Т) = 2п~1 + 1 лишь в случае когда Т —звезда.

В той же статье было найдено число независимых множеств в цикле на п вершинах. По-видимому, со статьи Продингера и Тичи берёт начало использование термина «число Фибоначчи графа» в качестве синонима для числа независимых множеств. В работе С. Лин и Ч. Лин [33] были охарактеризованы деревья, число независимых множеств в которых отличается не более чем на 7 от максимально возможного 2П~1 + 1.

В статье Г. С. Вильфа [44] была получена верхняя оценка числа максимальных независимых множеств в деревьях с заданным числом вершин:

Теорема 3 (Г. С. Вильф [44]). Для любого дерева Т на п вершинах выполнены неравенства гм (Т) < при нечётных п, и гм{Т) < 1 + 2(п~2)/2 при чётных п.

Оригинальное доказательство теоремы 3 основывалось на свойствах разбиений натуральных чисел. Б. Е. Саган в работе [41], используя теоретико-графовые рассуждения, упростил доказательство теоремы 3 и полностью охарактеризовал деревья, на которых достигается верхняя оценка. В статье [44] был поставлен вопрос о числе м. н. м. в связных графах с заданным числом вершин. Ответ на него был получен в [28]. В работе [42] теоремы Вильфа и Муна-Мозера одновременно обобщались за счёт рассмотрения класса связных графов с заданным числом циклов. Для каждых фиксированных п и г в [42] были указаны графы, на которых достигается максимум числа м. н. м. в классе всех связных n-вершинных графов с г циклами.

Для дальнейшего изложения введём несколько определений. Пусть U = {ui, ., 1}, V = {г"1, ., Vp}, W = {tyi, ., wq}. Обозначим через Bd, p, q дерево на множестве вершин U U V U W, такое, что его поддеревья, порождённые множествами {щ} U У, {u (i-} UWwU представляют собой соответственно звёзды Ki, p, Кл и цепь P (i-1 • Отметим, чтоВ^дд есть просто цепь длины d. П. Д. Вестергардом и А. С. Педерсеном была получена следующая верхняя оценка числа независимых множеств в деревьях заданного диаметра:

Теорема (П. Д. Вестергард, А. С. Педерсен [39]). Для любого п-вершинного дерева Т диаметра d выполнено неравенство i (T) ^ i{Bd, n-d,), обращающееся в равенство только при Т ~ Bd, n-d, 1 •.

В той же работе [39] был поставлен вопрос о нижних оценках числа независимых множеств в деревьях заданного диаметра. Для деревьев диаметра 4 исчерпывающий ответ был дан в работе [27] (формулировка теоремы приведена в разд. 1.1). Также в работе [27] была описана структура экстремальных деревьев диаметра 5 для достаточно больших п. Проблема Вестергарда (полное описание экстремальных деревьев при произвольном заданном числе вершин и диаметре) до сих пор не решена в общем случае.

Важным направлением является получение асимптотических оценок числа независимых множеств в параметрических классах графов. К таковым относятся диаграммы Хассе частично упорядоченных множеств, плоские прямоугольные решётки и др. В работе [14] А. Д. Коршуновым и А. А. Сапоженко была получена асимптотика числа независимых множеств в графе n-мерного булева куба (в оригинале результат сформулирован в терминах числа двоичных кодов с расстоянием 2).

Теорема (А. Д. Коршунов, А. А. Сапоженко [14]). Для графа п-мерного булева куба Вп справедлива асимптотика i (Bn) ~ 2л/ё22″ -1.

Для числа независимых множеств в полных бинарных деревьев с п ярусами рёбер В. П. Ворониным и Е. В. Демаковой получен следующий результат.

Теорема 4 (В. П. Воронин, Е. В. Демакова [2]). Обозначим через i, n число независимых множеств в полном бинарном дереве, имеющем к ярусов рёбер. Существуют, константы (3 и у такие, что при п —> оо справедлива асимптотика л 2″ ~ Р ¦ 7 •.

Активно также исследовался вопрос асимптотики числа независимых множеств в плоских прямоугольных решётках — графах Гт)7г, определяемых соотношениями ^(Гт-П) = {1,., т} х {1,., п} и.

Я (гт, п) = {{(«ь л), foih)} ¦ In — Ц + |ii — h = l}.

Из многих работ на эту тему упомянем статью Г. С. Вильфа и Н. Кал-кина [23], характерную применением метода трансфер-матриц, в которой доказана следующая.

Теорема (Г. С. Вильф, Н. Калкин [23]). Существует двойной предел при т., п —? оо i (rm, n)™ 77, где 1.503 < г) < 1.5035.

Значительный интерес представляют оценки числа независимых множеств в регулярных и «почти регулярных» графах (то есть графах, в которых степени вершин либо попарно равны, либо лежат в сравнительно узком диапазоне). К задачам такого рода сводятся некоторые перечислительные проблемы теории чисел и теории групп. Например, перечисление множеств, свободных от сумм (МСС), в абелевых группах (то есть множеств А, таких, что, А П {а + b | а, Ъ е А} = 0) сводится к перечислению независимых множеств в графах Кэли. Этот подход был применён Н. Ало-ном в [21] для получения асимптотики логарифма числа МСС в отрезке натуральных чисел. Позже, также с применением теории графов, А. А. Са-поженко [17] получил асимптотику числа МСС в отрезке натуральных чисел. Рабочим инструментом в статье [21] была следующая оценка для числа независимых множеств в регулярных графах.

Теорема (Н. Алон [21]). Для любого крегулярного графа G на п вершинах число независимых множеств i{G) удовлетворяет неравенству i (G) < (1) где f (k) = О (к~01).

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

Лемма 1 (Н.Алон [21]). Для всякого k-регулярного п-вершинного графа существует остовный двудольный подграф, степени вершин которого лежат в интервале k/2 — 2y/k log2 к, к/2 + 2^/к og2k .

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

А. А. Сапоженко предложил более простое доказательство оценки (1), улучшив, кроме того, остаточный член до f (k) — 0(Vk~l In к) и распространив оценку на квазирегулярные графы [16].

В работе [21] высказано следующее.

Предположение (Н. Алон [21]). Наибольшим числом независимых множеств среди к-регулярных графов на п вершинах при 2к п обладает единственный с точностью до изоморфизма граф, представляющий собой объединение ^ непересекающихся полных двудольных графов.

Граф из формулировки гипотезы будем называть далее графом Алона.

Рис. 1. Граф Алона.

Эта гипотеза остается недоказанной до сих пор (апрель 2009), хотя большинство исследователей не сомневаются в ее справедливости. Справедливость этой гипотезы означала бы в частности, что в (1) имеет место оценка f (k) = 0(k~1).

С помощью теоретико-информационного подхода Дж. Каном и А. Лоренцем в статье [32] была получена достижимая верхняя оценка числа независимых множеств в двудольных регулярных графах, что косвенно подтверждает гипотезу Алона.

Теорема 5 (Дж. Кан, А. Лоренц [32]). Пусть G — двудольный к-регулярный граф на п вершинах. Тогда i (G) ^ (2fc+1 — 1)2.

Отметим, что вопрос о единственности экстремального графа в теореме 5 до сих пор остаётся открытым.

Интересен вопрос о числе независимых множеств в графах, для которых известен размер наибольшего независимого множества. Это связано с довольно общим подходом в перечислительной комбинаторике, который может быть назван методом контейнеров [20]. Метод состоит в следующем. Пусть, А и В — семейства подмножеств некоторого множества. Скажем, что семейство В является системой контейнеров для А, если для каждого A G, А найдётся В € В, такое, что, А С В. Тогда, очевидно, выполнено неравенство.

Грубые на первый взгляд, такие оценки при подходящем выборе системы В позволяют получать асимптотику. Таким способом, например, А. А. Сапоженко получил решение проблемы Камерона-Эрдёша [17]. Вопрос о применимости метода контейнеров для задачи оценки числа независимых множеств в графах тесно связан с указанной выше задачей перечисления независимых множеств в графах с фиксированным числом независимости, поскольку семейство всех м. н. м. графа является системой контейнеров для семейства всех независимых множеств, и число независимости графа является прямым ограничением размера таких контейнеров.

В статье [1] была доказана следующая.

Теорема 6 (В.Е. Алексеев [1]). Для любого графа G выполнено неравенство где п = n{G), а = a{G).

Неравенство (2) было использовано в [1] для оценки числа м. н. м. в графах, а в работе [18] — для получения верхних оценок числа независимых множеств в квазирегулярных графах с ограничением на число независимовев.

2) сти и расширителях. Достижимая нижняя оценка числа независимых множеств в графах с фиксированным числом независимости получена в [38].

Краткое содержание диссертации.

Диссертация состоит из трёх глав.

Первая глава посвящена оценкам числа независимых множеств в деревьях фиксированного диаметра. В разделе 1.1 вводится ключевое понятие ёмкости графа и даётся несколько других определений, доказываются встомогательные утверждения. В разделе 1.2 доказываются нижние оценки числа независимых множеств в деревьях диаметра 6,7,8,9. В частности, доказываются следующие теоремы:

Теорема (разд. 1.2, теоремы 8, 9). Любое дерево диаметра 6 на п вершинах содержит не меньше независимых множеств. Любое дерево диаметра 7 на п вершинах содержит не меньше.

35(п-2)/7 независимых множеств. Любое дерево диаметра 8 на п вершинах содерэ/сит не меньше независимых множеств. Любое дерево диаметра 9 на п вершинах содержит не меньше независимых множеств.

В разделе 1.3 доказываются теоремы, характеризующие структуру экстремальных деревьев в проблеме Вестергарда. Дерево Т называется (n, d)-минимальным, если оно имеет наименьшее число независимых множеств среди всех деревьев диаметра dna, n вершинах. Через Ft будем обозначать лес, полученный из дерева Т удалением всех центральных вершин.

Теорема (разд. 1.3, теорема 10). Для произвольного фиксированного d существует конечное множество деревьев Add со следующим свойством. Для любого п и любого (n, d) -минимального дерева Т каждая из компонент леса Ft изоморфна некоторому дереву из М.&-.

Через Т' обозначим такое дерево, что лес FT> является паросочетанием на шести вершинах. Пусть Т" означает дерево диаметра 6, такое, что лес Ft" является объединением четырёх пятивершинных цепей.

Теорема (разд. 1.3, следствие из теоремы 12). При d? {6,7} и при всех достаточно больших п вида 7к + d — 5, к? N, для любого (n, d)~ минималъного дерева Т все компоненты леса Ft изоморфны дереву Т'. При d е {8,9} и при всех достаточно больших п вида 21k—d—7, k EN, для любого (п, d) -минимального дерева Т все компоненты леса Ft изоморфны дереву Т" .

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

В разделе 1.5 получено обобщение теоремы Воронина-Демаковой на случай g-арных деревьев при произвольном q. Обозначим через k число независимых множеств в полном g-арном дереве, имеющем к ярусов рёбер, или, что-то же, диаметр 2к. Доказана следующая.

Теорема (разд. 1.5, теорема 15). При q е {2,3,4} для Lq>k справедлива асимптотика при к оо:

Pq’lf > для некоторых констант f3q и jq.

При q > 5 справедлива асимптотика при к —> оо:

2к lq, 2k ~ aq>0 ¦ %, 02fc+l l>q, 2k+l ~ aq, l'7q где константы aqfi и aqд удовлетворяют неравенству ск9-о > &q, i ¦

Заслуживает внимания различный характер асимптотики величины iqj /с при q < 4 и q ^ 5.

Результаты первой главы опубликованы в [4, 8].

Вторая глава диссертации посвящена оценкам числа максимальных независимых множеств в графах заданного диаметра. В разделе 2.1 вводятся основные определения и доказываются некоторые вспомогательные утверждения. В разделе 2.2 получено полное описание графов с заданным диаметром, на которых достигается минимум числа м. н. м. Определим последовательность фп соотношением фп — Фп-2 + Фп-ъ и начальными условиями фо = ф = 1, Ф2 — 2.

Теорема (разд. 2.2, теорема 16). Для любого d, d ^ 4, и для любого графа G диаметра d выполнено неравенство im{G) ^ Фа+i ¦ Если Im{G) = фл+1, то множество V{G) можно разбить на подмноэ/сества Vo, ., V, d, так, что при любом к, 2 ^ к ^ d, и любом г, 0 ^ г ^ d — k, в G отсутствуют рёбра между вершинами из V} и V^, и для всякого г, 0 ^ г ^ d — 1, подграф графа G, порождённый множеством Vi U Vi+1, является полным двудольным с долями Vi и Vi+i.

В разделе 2.3 приводится полное описание деревьев с заданным диаметром и числом вершин, на которых достигается минимум числа м. н. м. Тем самым получено существенное обобщение теорем Вильфа [44] и Сагана [41]:

Теорема (разд. 2.3, теорема 17). Для любого п-вершинного дерева Т диаметра d выполнено неравенство гм (Т) ^ M (n, d), где.

При d ^ 9 существует единственное с точностью до изоморфизма дерево, на котором достигается указанная оценка (полное описание экстремальных деревьев при всех d см. в разд. 2.3).

Ф<1—1 + (2(^+1)/2 — 1)^.

2) при d ^ 4, п — d = 2k + 1, k > О, при d ^ 4, п — d — 2, при d ^ 5, d ф 7, п — d = 2k ^ 4, при d е {4, 7}, п — d = 2k ^ 4.

M (n, d) = <

Фй—2 + Фа,.

2(n-d)/2фйъ.

Результаты второй главы опубликованы в [9, 10, 11, 12]. В третьей главе диссертации исследуется число независимых множеств в графах с заданным размером максимального независимого множества. Неравенство (2) обращается в равенство при ап (максимум числа независимых множеств достигается на графе UKn>a). Доказываемая в разделе 3.1 теорема 18 даст уточнение оценки (2), делающее её достижимой при всех возможных сочетаниях параметров п, а, а также описывает экстремальные графы.

Теорема (разд. 3.1, теорема 18). Для любого графа G, такого, что n (G) = — пи a (G) — а, выполнено неравенство i{G) ^ i (UKnia), обращающееся в равенство только на графах, изоморфных UКПА.

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

Теорема (разд. 3.2, теоремы 19). Для любых n, a (n ^ 2) среди всех деревьев на п вершинах с числом независимости, а максимальное число независимых множеств имеют только деревья, изоморфные дереву, полученному из звезды Ki>a подразбиением (п — а — 1) рёбер.

Теорема (разд. 3.2, теорема 20). Среди всех лесов на п вершинах без изолированных вершин с числом независимости, а максимум числа независимых множеств достигается только на лесах, являющихся объединением паросочетания на 2(п — а — 1) вершинах и звезды Ki^a-n+i ¦

Раздел 3.3 посвящён оценкам числа независимых множеств в регулярных л-вершинных графах, число независимости в которых близко к п/2 (то есть к максимально возможному).

Теорема (разд. 3.3, теорема 22). Для сколь угодно больших К и N существуют к-регулярный п-вершинный граф G, такой, что к > К, п > N, и.

Т) a (G) <-(lЩк-1)),.

71 logS{G)) >-(l + 0(fc" 1)). С другой стороны, для любой константы в е (0, ½) для любого к-регулярного п-вершинного графа G, такого, что &{G) < |(1 — Q (k~0)), выполнено неравенство log2(i (G))<^(l-fl (*Te)).

В разделе 3.4 доказывается обобщение теоремы 5 на квазирегулярные двудольные графы:

Теорема (разд. 3.4, теорема 23). Пусть G — двудольный граф с долями, А и В. Пусть степени вершин из, А ограничены сверху числом к2, а степени вершин из В ограничены снизу числом к. Тогда.

Результаты третьей главы опубликованы в [3, 5, 6, 7].

Основные результаты диссертации.

1. Для произвольного d описана структура (п, d)-минимальных деревьев (теоремы 10,11, 12). Как следствие, получены асимптотически достижимые нижние оценки числа независимых множеств в деревьях диаметра 6, 7, 8, 9 (теоремы 8, 9, 13).

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

3. Получена достижимая верхняя оценка числа независимых множеств в графах с заданным числом независимости, полностью описаны графы, на которых эта оценка достигается (теорема 18).

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

1. Алексеев В. Е. Верхняя оценка числа максимальных независимых множеств графа // Дискретная математика. 2007. Т. 19. Вып. 3. С. 84−88.

2. Воронин В. П., Демакова Е. В. О числе независимых множеств для некоторых семейств графов // Труды IV Международной конференции «Дискретные модели в теории управляющих систем», Краснови-дово, 19−25 июня 2000 г., М.: МАКСПресс, 2000. С. 145−149.

3. Дайняк А. Б. О числе независимых множеств в графах с фиксированным числом независимости // Дискретная математика. 2007. Т. 19. Вып. 2. С. 63−66.

4. Дайняк А. Б. Уточнение оценки В. Е. Алексеева числа независимых множеств в графах // Проблемы теоретической кибернетики. Тезисыдокладов XV международной конференции (Казань, 2—7 июня 2008) / Под ред. Ю. И. Журавлёва Казань: Отечество, 2008. С. 25.

5. Дайняк А. Б. Оценки числа независимых множеств в графах с фиксированным числом независимости // Вестник Московского университета, сер. 15. Вычислительная математика и кибернетика. 2009. № 2. С. 45−48.

6. Дайняк А. Б. О числе независимых множеств в деревьях фиксированного диаметра // Дискретный анализ и исследование операций. 2009. Т. 16. № 2. С. 61−73.

7. Dainiak А. В. Sharp bounds for the number of maximal independent sets in trees of fixed diameter // arXiv:0812.4948vl. 12 pp.

8. Дистель P. Теория графов (пер. с англ.). Новосибирск: Изд-во ИМ СО РАН, 2002. 336 с.

9. Коршунов А. Д., Сапоженко А. А. О числе двоичных кодов с расстоянием 2 // Проблемы кибернетики. Вып 40. М.: Наука, 1983. С. 111−130.

10. Прасолов В. В. Многочлены. 3-е изд. М.: МЦНМО, 2003. 336 с.

11. Сапоженко А. А. О числе независимых множеств в расширителях // Дискретная математика. 2001. Т. 13. № 1. С. 56−62.

12. Сапоженко А. А. Доказательство гипотезы Камерона-Эрдеша о числе множеств, свободных от сумм // Математические вопросы кибернетики. Вып. 12. М.:Физматлит. 2003. С. 5−14.

13. Сапоженко А. А. О числе независимых множеств в графах // Вестник Московского университета, сер. 1, Математика, Механика. 2007. № 3. С. 33−37.

14. Сапоженко А. А. Проблема Дедекинда и метод граничных функционалов // Математические вопросы кибернетики. Вып. 9. — М.: Наука, 2000. С. 161−220.

15. Сапоженко А. А. О методе контейнеров // Дискретная математика и её приложения. Сборник лекций молодёжных научных школ. Выпуск IV. / Под ред. А. В. Чашкина. М.: ИПМ им. М. В. Келдыша РАН, 2007. С. 11−25.

16. Alon N. Independent sets in regular graphs and sum-free subsets of finite groups // Israel J. Math. 1991. 2(73). P. 247−256.

17. Alon N., Spenser J. H. The Probabilistic Method. Third edition. Wiley-Interscience, 2008. 352 pp. (Русский перевод: Алон H., Спенсер Дж. Вероятностный метод. Пер. 2-го англ. изд. — М.: БИНОМ. Лаборатория знаний, 2007. 320 с.).

18. Calkin N., Wilf H.S. The number of independent sets in a grid graph // SIAM J. Discr. Math. 1998. 11. P. 54−60.

19. Chung F., Frank P., Graham R., Shearer J. Some intersection theorems for ordered sets and graphs // J. Comb. Th. Ser. A. 1986. 43. P. 23—37.

20. Croitoru C. On stables in graphs // Proc. Third Coll. Operations Research, Babes-Bolyai University, Cluj-Napoca, Romania. 1979. P. 55−60.

21. Eppstein D. Small maximal independent sets and faster exact graph coloring // J. Graph Algorithms and Applications (special issue for WADS'01) 2003. 7(2). P. 131−140.

22. Griggs J.R., Grinstead С. M., Guichard D.R. The number of maximal independent sets in a connected graph // Discrete Math. 1988. 68. P. 211 220.

23. Hoyosa H. Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons //Bull. Chem. Soc. Jpn. 1971. 44. P. 2332−2339.

24. Hujter M., Tuza Z. The number of maximal independent sets in triangle-free graphs // SIAM J. Discr. Math. 1993. 6(2). P. 284−288.

25. Johnson D.S., Yannakakis M., Papadimitriou С. H. On generating all maximal independent sets // Information Processing Letters. 1988. 27(3). P. 119−123.

26. Kahn J., Lawrenz A. Generalized rank functions and an entropy argument // J. Comb. Th. Ser. A. 1999. 87. P. 398−403.

27. Lin S., Lin Ch. Trees and forests with large and small independent indices // Chinese J. Math. 1995. 23(3). P. 199—210.

28. Merrifield R. E., Simmons H. E. Topological methods in chemistry, New York, John Wiley к Sons, 1989.

29. Miller R. E., Muller D.E. The problem of maximum consistent subsets — IBM Research Report RC-240. 1960. J.T.Watson Research Center, Yorktown Heights, N.Y.

30. Moon J.W., Moser L. On cliques in graphs // Israel J. Math. 1965. 3. P. 23−28.

31. Nielsen J. M. On the number of maximal independent sets in a graph. Preprint. Research Series RS-02−15, BRICS. Aarhus, Denmark: University of Aarhus, Department of Computer Science, 2002. Юр.

32. Pedersen A. S-, Vestergaard P. D. Bounds on the number of vertex independent sets in a graph // Taiwanese J. Math. 2006. 6(10). P. 15 751 587.

33. Pedersen A. S., Vestergaard P. D. An upper bound on the number of independent sets in a tree // Ars Combinatoria. 2007. 84. P. 85—96.

34. Prodinger H., Tichy R. F., Fibonacci numbers of graphs // Fibonacci Quart. 1982. 20(1). P. 16—21.

35. Sagan В. Б. A note on independent sets in trees // SIAM J. Discr. Math. 1988. 1. P. 105−108.

36. Sagan В. E., Ying G. Ch., Meng К. K., Vatter V. Maximal independent sets in graphs with at most r cycles //J. Graph Th. 2006. 53. P. 270−282.

37. Tsukigama S., Ide M., Ariochi H., Ozaki H. A new algorithm for generating all the maximal independent sets // SIAM J. Comput,. 1977. 3(6). P. 505 517.

38. Wilf H. S. The number of maximal independent sets in a tree // SIAM J. Alg. Discr. Methods 1986. 7. P. 125−130.