Обратные задачи, связанные с независимостью и доминированием в графах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Курносов Артем Дмитриевич

• Курносов Артем Дмитриевич
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Курносов Артем Дмитриевич

Содержание

Обозначения и основные определения

Введение

4

1 Перечислительные задачи по независимым

множествам для двудольных графов

1.1 Оценки величины (п)

1.2 Оценки величины у (п)

2 Графические и древесные последовательности

2.1 Г

рафические последовательности

33

33

34

44

44

2.2 Древесные последовательности

3 Операции, слабо меняющие число независимости и число доминирования графа

3.1 X-операции над графом

48

48

3.2 У-операции над графом

3.3 Общие свойства X- и У-операций для Т-упорядоченных

последовательностей вершин|

4 Число независимости в деревьях с заданной

степенной последовательностью

4.1 Вспомогательные утверждения

4.2 Нижняя оценка числа независимости

4.3 Верхняя оценка числа независимости

56

56

4.4 Достижимость всех промежуточных значений числа

независимости

68

5 Число доминирования в деревьях с заданной

степенной последовательностью

5.1 Вспомогательные утверждения

5.2 Нижняя оценка числа доминирования

5.3 Верхняя оценка числа доминирования

74

74

75

5.4 Достижимость всех промежуточных значений числа

доминирования

91

6 Число связного доминирования в графах с заданной степенной последовательностью!

6.1 Достижимая нижняя оценка числа связного доминирования

100

6.2 Бирегулярные графы с листьями

А О вопросах оптимальности при конструировании

последовательностей деревьев, реализующих все

значения а и все значения

А.1 Оптимальная реализация всех значений а

А.2 Операция связывания цепей

А.3 Оптимальная реализация всех значений

114

114

Заключение

123

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

124

Обозначения и основные определения

В работе рассматриваются простые неориентированные графы. Мы будем использовать приводимые ниже обозначения, в целом согласующиеся с современной литературой (см., та^ |1,2|).

• V(О) и Е(О) — множества вершин и рёбер графа О соответственно.

• Нуль-графом будем называть граф О с V(О) =

• Через |О| или V(О) будем обозначать число вершин в графе О.

• е(О) — число рёбер О.

• Е(А, В) — множество рёбер вида «V, где и € А^ € В. Если А = {V}, то будем сокращённо писать Е(V, В) вместо Е({V}, В).

• Положим Е(А) := Е(А, А) для произвольного подмножества вершин А.

• Для графа О = (V, Е) и подмножества V' С V через О — V' обозначаем подграф О, порождаемый множеством V \ V'. Сокращённо будем писать О — V вместо О — V', если V' = {V}.

• Для графа О = (V, Е) и подмножества Е' С Е через О — Е' обозначаем граф (V, Е \ Е'). Сокращённо записываем О — е вместо О — Е', если Е' = {е}.

• Объединение О1 и О2 графов О1 = (VI, Е^ и О2 = ("^2, Е2) — это граф О' = (V! и V!, Е1 и Е2).

• Через Рп и Сп будем обозначать соответственно цепь и цикл на п вершинах. Формально будем считать, что Р0 и Со — нуль-графы.

• Кп — полный граф на п вершинах.

• Ктп — полный двудольный граф с долями размера т и п.

• Граф вида К1,п (в вырожденном случае К0 и К1) будем называть графом-звездой.

• N0(5") — множество вершин среди V(О) \ Б, смежных с какими-либо вершинами подмножества 5 С V(О). Если 5 = {V}, то будем сокращённо писать Ас^).

• Ь(О) — множество висячих вершин графа О.

• Ьс(^) — множество висячих вершин в С, смежных с вершиной V.

• Н(С) — множество всех вершин С, смежных с листьями.

• Положим Я(С) := С - (Ь(С) и Н(С)).

• degG(v) — степень вершины V в графе С, то есть мощность Ас('у).

• Вершину V € V(С) будем называть проходной в С, если degG(v) =

• Т — класс деревьев.

• Т — класс лесов.

• В — класс двудольных графов.

В любом дереве путь между любой парой вершин единственен. Это позволяет корректно ввести следующее обозначение: для вершин дерева и и V через u~v обозначим путь между и и V, а через (u~v) обозначим этот же путь, но не включающий сами и и V.

Подмножество I вершин графа С называется независимым множеством, если никакие две вершины и^ € I не соединены ребром в С. Наибольший размер независимого множества в графе С называется числом независимости и обозначается как а(С).

Везде в тексте под максимальными и минимальными множествами подразумеваются множества, являющиеся соответственно максимальными и минимальными по включению. Максимальные и минимальные по размеру множества будем называть соответственно наибольшими и наименьшими. Максимальные независимые множества сокращённо будем записывать как м. н. м. Количество всех независимых множеств графа С будем обозначать ¿(С), количество всех м. н. м. графа С — ¿т(С), а множество всех м. н. м. будем обозначать Хт(С).

Для произвольной пары смежных или совпадающих вершин V и т будем говорить, что вершина V покрывается вершиной т (или т покрывает V). Будем говорить, что вершина V покрывается множеством вершин Ш, если V покрывается т для некоторой и> € Ш. Подмножество Б вершин графа С называется доминирующим, если каждая вершина графа покрывается этим подмножеством. Таким образом, любая вершина графа либо принадлежит доминирующему множеству, либо у неё есть сосед из доминирующего множества. Число доминирования 7(С) — это размер наименьшего доминирующего множества графа С.

Если доминирующее множество Б порождает связный подграф в исходном графе, то Б называется связным доминирующим множеством. Величина 7с(С) — это размер наименьшего связного доминирующего множества графа С, она называется числом связного доминирования и определена только для связных графов.

Введение диссертации (часть автореферата) на тему «Обратные задачи, связанные с независимостью и доминированием в графах»

Введение

1. Актуальность и степень разработанности темы исследования

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

Независимое множество — одно из важнейших понятий теории графов, оно тесно связано со многими другими её объектами: кликовое число графа есть число независимости в дополнении этого графа; хроматическое число графа есть минимальное число попарно непересекающихся независимых множеств, на которые можно разбить все вершины этого графа; паросочетание есть независимое множество в рёберном графе; а любое максимальное независимое множество является доминирующим множеством. Последнее свойство, связывающее между собой независимые и доминирующие множества, влечёт тривиальное соотношение 7(С) ^ а (С) для любого графа С.

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

Перечислительная задача подсчёта числа антицепей в булевом кубе (то есть величины ¿(О) в диаграмме соответствующего частичного порядка) была поднята Дедекиндом в 1897 году [6], данные числа, зависящие от размерности булева куба, называются дедекиндовыми числами. Позднее было опубликовано множество работ, затрагивающих данную проблему, многие из которых давали асимптотические оценки на дедекиндовы числа (см., например, [7-10]).

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

Тичи [11] в 1982 году. Там же они показали, что в классе Т при фиксированном числе вершин наибольшее значение ¿(О) имеет граф-звезда, а наименьшее — цепь Рп. Причём для Рп выполнено рекуррентное соотношение:

1(Ро) = 1; 1(Р1) = 2; ¿(Рп) = ¿(Рп-1) + ¿(Рп—2), п ^ 2.

То есть величина ¿(О) есть число Фибоначчи в минимальном случае, а именно когда граф является цепью. Вероятно поэтому число независимых множеств в графе также называют числом Фибоначчи графа.

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

работе [12], где Меррифилд и Симмонс среди прочего подробно рассмотрели вопрос

корреляции между данной величиной и точками кипения определённых видов моле-

кул; а также благодаря работе Гутмана [13], где впервые использовалось упомянутое

наименование термина. Индекс Меррифилда - Симмонса является одним из многих топологических индексов, то есть инвариантов молекулярных графов, применяемых в компьютерной химии, в числе которых можно также выделить индекс Винера Ш(О)

(см. [14]) и индекс Хосойи Z(О) (см. [15]). Индекс Винера представляет собой сумму расстояний между вершинами по всем парам вершин связного графа, а индекс Хосойи есть не что иное, как количество всех паросочетаний графа. Примечательно, что для многих классов графов, исследованных с точки зрения величин ¿(О) и Z(О), графы, являющиеся экстремальными по 1, являются экстремальными и по Z, причём экстремаль-

ности противоположны (см., например, [16]). Однако, связь этих величин монотонной не

является, то есть на тех же классах графов соотношения ¿(О1) > ¿(О2) и Z(О1) < Z(О2)

не равносильны [16].

Как и исследованию величины ¿, количеству м. н. м. ¿т посвящена довольно обширная литература. Было получено множество результатов, дающих ответы на вопросы об экстремальных значениях параметров 1 и 1т для различных классов графов. Подробнее

со списком таких исследований можно ознакомиться в обзоре [17].

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

инженерия, исследование операций. Одна лишь монография [18] (Хэйнс, Хедетниеми, Слэйтер), подробно освещающая результаты по доминированию в графах, содержит более 1200 библиографических ссылок.

Наиболее ранними по доминирующим множествам работами считаются такие, в которых были поставлены и частично решены задачи о расстановке фигур шахматной доски, интерес к которым возник приблизительно в 1850 году. К задачам такого рода, легко интерпретируемым в терминах доминирования в графе, относится, например, следующая: сколько минимум ферзей можно поставить на шахматную доску, так, чтобы каждое из оставшихся полей доски билось каким-либо ферзём? Одна из первых подобных

работ принадлежит российскому шахматисту Янишу К. А. [19] (который некоторое время активно изучал возможности применения математических методов в шахматах), выпущенную в 1862 году на французском языке.

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

социальных сетей [20,21]; компьютерной инженерии, в том числе проектирования и

обслуживания беспроводных сетей [22]; задач размещения объектов и связей между ними (это могут быть объекты инфраструктуры или, например, деталей электронной

схемы), прокладки оптимальных маршрутов [18,23] и др.

Имеются довольно интересные открытые проблемы, касающиеся доминирующих множеств, одной из самых известных и главных является гипотеза, высказанная Визин-

гом ещё в 1963 году (см. [24,25]).

Гипотеза (Визинга). Для произвольных графов С и Н и их прямого (или декартова) произведения С □ Н выполняется соотношение

7(С □ Н) ^ 7(С)7(Н). 9

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

Кларка и Суэна [26], опубликованной в 2000 году, для произвольных графов О и Н

была получена оценка

7(О □ Н) ^ 27(О)7(Н). (1)

В 2012 в работе Суэна и Тарра [27] оценка была улучшена до

7(О □ Н) ^ 17(О)7(Н) + ±шш{7(О), 7(Н)}.

Для произвольного графа О без индуцированного подграфа К1,3 и произвольного графа Н в оценке (1) можно заменить коэффициент 1/2 на 2/3 (см. [28], Кроп, 2017 г.). На настоящий момент попытки доказать гипотезу продолжаются.

Отметим, что задача о доминирующем множестве, состоящая в ответе на вопрос о существовании в графе доминирующего множества размера не больше предписанного, является КР-полной; КР-полной является и аналогичная задача о независимом

множестве (и клике), см., например, [29,30]

Добавляя различные уточнения к определению доминирующего множества (они могут заключаться, например, в дополнительных требованиях к доминирующему множеству), мы получим множество вариаций доминирования в графах: независимое доминирующее множество — множество, являющееся одновременно и независимым, и доминирующим; связное доминирующее множество; вечное доминирующее множе-

ство [31]; полное доминирующее множество — такое доминирующее множество Д, что у каждой вершины Д есть сосед в Д, другими словами, каждая вершина V графа должна покрываться какой-либо вершиной и € Д, отличной от V; к-доминирующее множество — такое доминирующее множество Д графа О(^ Е), что любая вершина V \ Д покрывается минимум к вершинами из Д, и т. д. Все эти и многие другие вариации доминирования активно исследуются в современной литературе. В данной работе мы рассмотрим лишь одну из таких вариаций: связное доминирование.

Понятие связного доминирования тесно связано с понятием остовного дерева. Если через /С(О) обозначить максимально возможное число листьев в остовном дереве связного графа О, то для произвольного связного графа с хотя бы тремя вершинами можно записать простое общеизвестное соотношение:

7е(О)+ /С(О) = |О|. 10

Оно следует из того, что любое минимальное связное доминирующее множество Б является множеством нелистовых вершин некоторого остовного дерева (в подграфе, порождаемом Б, можно выделить остовное дерево, а затем добавить к нему оставшиеся вершины графа в виде листьев, в силу минимальности вершины Б сами при этом не будут являться листьями) и, наоборот, множество нелистовых вершин остовного дерева образует связное доминирующее множество.

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

Задача поиска остовного дерева с наибольшим числом листьев упоминается уже

в статье В. Г. Визинга [25] 1968 года. Эта задача является ХР-трудной даже для кубических графов [32], поэтому неудивительно, что имеется и продолжает появляться заметное количество работ, в которых приводятся различные нижние оценки величины /е(С) (что соответствует верхним оценкам числа 7с(С)), а также относительно быстрые

приближённые алгоритмы для данной задачи: [33-43]. В большинстве работ рассматриваются графы с определённой дополнительной информацией о структуре, например, с ограничением снизу на степени вершин или запретами на содержание определённых подграфов.

Термин "связное доминирование" впервые использовался в литературе Сампаткума-

ром и Валикаром [44]. Терминология "связного доминирования" используется, например, и в работах [45-49], где некоторые из авторов рассматривают не только верхние, но и нижние оценки 7с(С).

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

проводных (см., например, [50,51]). Использование связного доминирующего множества позволяет упрощать процедуру передачи и хранения информации для различных узлов сети. Например, имея связное доминирующее множество узлов Б, можно осуществлять передачу данных между любыми двумя узлами сети, используя только узлы Б в качестве промежуточных звеньев маршрута, множество Б в таком случае является множеством так называемых маршрутизаторов. Именно маршрутизаторы по хранящейся в них таблице маршрутизации определяют, куда дальше нужно пересылать пакет полученных данных, и связность Б обеспечивает возможность этой передачи для всей сети, даже если во всех узлах, не входящих в Б, хранить информацию только о

смежных с ними маршрутизаторах. В монографии [52] можно ознакомиться с более

подробным списком исследований подобного рода.

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

Сформулируем общие постановки обратных задач существования и минимизации (задачу максимизации можно определить аналогично). Пусть 0 — класс графов, а р : 0 ^ $ и — : 0 ^ Т — заданные инварианты графа (значениями инварианта могут быть числа, а могут быть, например, последовательности чисел). Обратная задача существования для пары (0, р) ставится следующим образом: для каких в € $ найдётся граф О € 0, такой, что р(О) = в? Если р(О) = в, то будем говорить, что в реализуется графом О, а граф О при этом будет реализацией значения в. Для значений инварианта, являющихся решениями задачи существования, можно также поставить обратную задачу описания: для данного в € $ описать множество графов О € 0 с р(О) = в.

Пусть $ — множество всех значений, которые некоторый инвариант р принимает на произвольных графах. При $ С N будем говорить, что класс графов 0 является сильно р-полным, если для каждого в € $ найдётся его реализация О € 0. Если же такой граф О € 0 найдётся для всех достаточно больших в € Б, то класс 0 назовём слабо р-полным, или просто р-полным.

Если существование соответствующих реализаций установлено, то имеет смысл обратная задача минимизации для тройки (0, р, —): для заданного в € $ найти величину Ь® ф(в) = т£{—(О) | О € 0, р(О) = в} (для аналогичной задачи максимизации соответствующего конечного максимума потенциально может и не быть). Нас будет интересовать в первую очередь асимптотика функции Ь® ^ (в) для р-полных классов графов. Если 0 — класс всех графов, то вместо Ь® ^(в) будем писать Ь®,ф(в).

Классическим примером обратной задачи является задача определения для заданного набора целых неотрицательных чисел, соответствует ли этот набор степеням вершин некоторого графа; в терминах общей постановки существования пара (0, р) тогда соответствует классу всех графов и степенной последовательности р = (^1, ... , ^п)

графа. Данная задача была независимо решена Гавелом [53], Хакими [54], а также Эр-

дёшем и Галлаи [55]. Ещё одним примером обратной задачи, нашедшей отражение в литературе, является задача реализуемости индекса Винера деревьями. Задача долгое время оставалась нерешённой. В итоге было доказано, что лишь 49 натуральных чисел не

попадают в множество значений Ш, реализуемых деревьями (см. [56], Вагнер, [57], Ван

Ю). Таким образом, Т — Ш-полный класс. В работах Цабарки, Секея и Вагнера [58], а

также Ли С., Ли З. и Вана [59] представлены некоторые обратные задачи для других инвариантов (в основном на классе деревьев), многие из которых успешно решены.

Перейдём к рассмотрению результатов по обратным задачам, касающихся неза-

висимых множеств. В 1989 году Линек [60] доказал сильную ¿-полноту класса В. Так

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

Теорема 1 (Линек, [60]). Для любого нечётного натурального числа п, удовлетворяющего неравенству 2к-1 + 1 ^ п ^ 2к — 1, существует двудольный граф с долями размера а = |_1о§2 п] и |_1о§2(п — 2" + 1)], реализующий число п в качестве значения ¿.

Получившаяся оценка не является асимптотически точной, в разделе 1.1 мы рассмотрим примеры более "эффективной" реализации для некоторых чисел, а именно чисел вида 2п — 1.

Что весьма интересно, при доказательстве теоремы 1 Линек попутно решил другую обратную задачу: он показал, что для любого натурального п ^ 2 существует двудольный граф С с долями размера п] и п] +1, реализующий п как величину с(С), где с(С) — это число всех полных двудольных подграфов С с непустыми долями.

В работе [60] Линек также выдвинул гипотезу, что класс Т является ¿-полным.

Данная гипотеза на настоящий момент не доказана, однако имеются работы, где полу-

чены некоторые занимательные результаты, связанные с ней. Например, Вагнер [61| доказал, что для любого натурального т доля деревьев на п вершинах, число независимых множеств которых кратно т, стремится к 1 при п ^ то. То есть, в частности, это означает, что раз почти все деревья имеют чётное число независимых множеств, то для реализации нечётного числа придётся приложить определённые усилия.

Доказательство Вагнера основано на рекурсивном вычислении ¿(Т) при помощи

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

Лау [62], более того, построенные там реализации имеют максимальную степень не выше трёх.

В своей работе [63] Ли, Чжао и Гутман рассмотрели несколько другую обратную задачу, состоящую в отыскании всех графов требуемого класса, реализующих числа, попадающие в предписанный числовой промежуток: ими было описано множество всех п-вершинных деревьев Т, для которых 2п-2 ^ ¿(Т) ^ 2п-1. При этом значение ¿(Т) = 2п-1 + 1 является максимальным на классе [11] и достигается только на графе-звезде.

Величина ¿(С) исследовалась и на многих других классах графов. К примеру, для каждого класса унициклических графов с фиксированным числом вершин: Педерсен

и Вестергаард [64] вычислили оба экстремальных значения ¿, а при дополнительно

заданном обхвате — максимальное значение, в обоих случаях они также описали мно-

жество экстремальных графов; Ли Ш. и Чжу [65] вычислили максимум инварианта при дополнительно заданном диаметре и описали экстремальный граф, являющийся единственным.

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

отметим также работу Андриантианы [66], в которой рассматривается класс деревьев с предписанной степенной последовательностью, и для него описывается единственное с точностью до изоморфизма дерево, одновременно имеющее на классе наибольшее значение индекса Меррифилда - Симмонса и наименьшие значения индекса Хосойи и энергии, где энергия графа — сумма абсолютных величин собственных значений матрицы смежности этого графа. В той же работе было показано, что многие результаты об экстремальных значениях ¿ (как и оставшихся двух индексов) при различных ограниче-

ниях на деревья, известные до выхода [66], являются простыми следствиями основной теоремы данной работы.

Перейдём к результатам, связанным с ¿т. В 1960 году Миллер и Мюллер [67]

привели верхнюю оценку величины ¿т для класса всех графов с фиксированным числом

вершин. Эта же задача была независимо решена в работе Муна и Мозера [68] 1965 года.

При этом результат в обеих работах был получен в терминах максимальных клик. В

тех же работах описаны и все экстремальные графы.

Нижняя оценка числа максимальных независимых множеств для класса всех графов тривиальна: для пустого графа 1т(О) = 1. Ясно, что присутствие изолированных вершин никак не отражается на величине 1т. Поэтому имеет смысл рассматривать графы без оных. Однако даже при рассмотрении всех графов без изолированных вершин (для фиксированного числа вершин) нижняя оценка остаётся тривиальной: полный двудольный граф имеет ровно два максимальных независимых множества. Можно заметить, что и в этом примере есть особый тип вершин: так называемые вершины-дубликаты. Вершины и, V графа О называются дубликатами друг друга, если Ас(«) = N0^). Количество дубликатов у произвольной вершины также не влияет на 1т, то есть можно удалить или наоборот добавить сколько угодно дубликатов, не изменив при этом

1т.

Джоу, Чан, Линь и Ма [69] рассмотрели как раз класс S графов без дубликатов и изолированных вершин (но граф К1 тоже включён ими в S в виде исключения). Они решили обратную задачу описания для класса S и величины 1т для значений 1т(О) € {1, 2, 3}, а также обратную задачу максимизации для тройки (Б, 1т, V) (напомним, что V — число вершин графа). Вот соответствующий результат.

Теорема 2 (Джоу, Чан, Линь и Ма, [69]). Пусть О — граф без изолированных вершин и вершин-дубликатов с 1т(О) = к, к ^ 2. Тогда |О| ^ 2к-1 + к — 2, причём оценка является достижимой для любого к ^ 2.

Очевидно, оценка теоремы 2 задаёт также нижнюю оценку числа 1т для графов с фиксированным числом вершин класса Б. Если в классе Б ограничиться рассмотрением лишь деревьев, получится класс Бт деревьев без листьев-дубликатов (нелистовых дубликатов и изолированных вершин, за исключением случая К1, быть в дереве не может по

определению). В 2018 году Талецкий и Малышев [70] решили обратную задачу описания для класса п-вершинных деревьев из Бт и экстремального значения величины 1т: ими было описано множество всех п-вершинных деревьев из Бт с наименьшим количеством максимальных независимых множеств для любого п.

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

шинами в 1987 году получил Фюреди [71]. Позже, в 1988, независимо от него Григгс,

Гринстед и Гишар [72] получили точную верхнюю оценку уже для связных графов с

любым фиксированным числом вершин. Ими же были охарактеризованы все экстремальные графы, на которых достигается полученный максимум. Для класса деревьев с фиксированным числом вершин точное значение аналогичного максимума получил Вильф [73], задействовав алгебраические методы. Позднее Саган привёл теоретико-

графовое доказательство того же результата [74] и дополнительно описал все деревья,

на которых оценка достигается. Лю [75] нашёл точную верхнюю оценку ¿т для класса двудольных графов с фиксированным числом вершин и описал все экстремальные графы.

Кроме работ, в которых исследуется максимальное значение ¿т на классах с фиксированным числом вершин, имеется множество работ, посвящённых значениям

данного инварианта, близких к максимуму, например: Цзинем З. и Ли С. [76] получено

второе по величине значение для класса всех графов, Джоу и Линем [77] получено второе

значение для классов деревьев и лесов, Цзинем и Янем [78] — второе и третье значения

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

В 2015 году автором настоящей диссертационной работы в соавторстве с Дайняком

А. Б. [80] были исследованы обратные задачи существования и минимизации для тройки (В, ¿т, V) и была дана асимптотическая оценка на величину Ь^ и(п). Соответствующие

результаты представлены в теоремах 1.2.1 и 1.2.2

Не вызывает сомнений, что наиболее элементарными, но при этом важнейшими глобальными характеристиками графа являются его число вершин и число рёбер. Самой же используемой локальной характеристикой, пожалуй, является степень вершины в

графе. Поэтому неудивительно, что уже упомянутая ранее и решённая в работах [53-55] задача реализации целочисленной последовательности в виде степенной последовательности графа стала одной из первых рассмотренных в литературе обратных задач, а соответствующие условия существования широко известны среди специалистов по теории

графов. Хакими [54,81] исследовал реализации не только графов, но и мультиграфов.

В частности, для последовательности натуральных чисел он привёл критерий суще-

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

ответ на вопрос, в каких случаях для данной натуральной последовательности связная

"мультиреализация" единственна с точностью до изоморфизма [81].

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

активно использовалась следующая операция по перестроению графа, которая, очевидно, сохраняет степенную последовательность. Пусть четыре различные вершины графа О таковы, что «V, € Е(О) и «ад, ^ € Е(О), тогда операция, заключающаяся в удалении из О рёбер «V, и и проведении рёбер «и, называется элементарным ¿-инвариантным преобразованием. Данная операция является довольно естественным слабо меняющим граф действием по его перестроению, поэтому неудивительно, что она нередко возникала в том или ином виде в других работах по теории графов. Например,

в книге Зыкова [82] она называется 4-сдвигом. В дальнейшем мы будем склоняться именно к такому названию термина, а в разделе 3 и вовсе переопределим операцию в более общем виде.

Алгоритм, задействованный Гавелом [53] и Хакими [54] для определения графично■

Список литературы диссертационного исследования кандидат наук Курносов Артем Дмитриевич, 2020 год

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

[1] Diestel R. Graph Theory. 5th edition. — Heidelberg: Springer-Verlag, Graduate Texts in Mathematics, 2017. — Vol. 173. — 447 P.

[2] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. — М.: Наука. Физматлит, 1990. — 384 С.

[3] Thai M.P., Pardalos P.M. Handbook of Optimization in Complex Networks. — New York: Springer, SOIA book series, 2012. — Vol. 58. — 544 P.

[4] Коршунов А.Д., Сапоженко А.А. О числе двоичных кодов с расстоянием 2 // Проблемы кибернетики. — 1983. — Т. 40. — С. 111-130.

[5] Daum S., Ghaffari M., Gilbert S., Kuhn F., Newport C. Maximal independent sets in multichannel radio networks // PODC 2013: Proceedings of the 2013 ACM symposium on Principles of distributed computing, Montreal, Canada, July 22-24, 2013. — P. 335344.

[6] Dedekind R. Uber Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler // Festschrift Hoch. Braunschweig u. ges. Werke. — 1897. — Vol. 2. — P. 103-148.

[7] Kleitman D.J. On Dedekind's Problem: The Number of Monotone Boolean Functions // Proceedings of the American Mathematical Society. — 1969. — Vol. 21, N. 3. — P. 677682.

[8] Коршунов А.Д. Решение проблемы Дедекинда о числе монотонных булевых функций // Докл. АН СССР. — 1977. — Т. 233, № 4. — С. 543-546.

[9] Kahn J. Entropy, independent sets and antichains: a new approach to Dedekind's problem // Proceedings of the American Mathematical Society. — 2002. — Vol. 130, N. 2. — P. 371-378.

[10] Сапоженко А.А. Проблема Дедекинда и метод граничных функционалов. — М.: Физматлит, 2009 — 152 С.

[11] Prodinger H., Tichy R. F. Fibonacci numbers of graphs // The Fibonacci Quarterly. — 1982. — Vol. 20, N. 1. — P. 16-21.

[12] Merrifield R.E., Simmons H.E. Topological methods in chemistry. — Chichester: Wiley, Surface Science Letters, 1989. — Vol. 221, N. 3. — P. A521.

[13] Gutman I. Topological properties of benzenoid systems. Merrifield - Simmons indices and independence polynomials of unbranched catafusenes // Rev. Roum. Chim. — 1991. — Vol. 36. — P. 379-388.

[14] Wiener H. Structural determination of paraffin boiling points //J. Amer. Chem. Soc. — 1947. — Vol. 1, N. 69. — P. 17-20.

[15] Hosoya H. Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons // Bulletinof the Chemical Society of Japan. — 1971. — Vol. 44, N. 9. — P. 2332-2339.

[16] Wagner S., Gutman I. Maxima and minima of the Hosoya index and the Merrifield-Simmons index: a survey of results and techniques // Acta Appl Math. — 2010. — Vol. 112. — P. 323-346.

[17] Дайняк А.Б., Сапоженко А.А. Независимые множества в графах // Дискрет. матем. — 2016. — Т. 28, № 1. — С. 44-77.

[18] Haynes T.W., Hedetniemi S.T., Slater P.J. Fundamentals of Domination in Graphs. — New York: Marcel Dekker, Inc., Monographs and textbooks in Pure and Applied Mathematics, 1998. — 455 P.

[19] De Jaenisch C.F. Applications de I'Analuse mathematique an Jen des Echecs. — Petrograd, 1862.

[20] Kelleher L.L., Cozzens M.B. Dominating sets in social network graphs // Mathematical Social Sciences. — 1988. — Vol. 16, N. 3. — P. 267-279.

[21] Wang F., Camacho E., Xu K. Positive Influence Dominating Set in Online Social Networks // Combinatorial Optimization and Applications (Proc. of the International Conference on Combinatorial Optimization and Applications, Huangshan, China, June 10-12, 2009). — Heidelberg: Springer, Lecture Notes in Computer Science, 2009. — Vol. 5573. — P. 313-321.

[22] Karbasi A.H., Atani R.E. Application of dominating sets in wireless sensor networks // International Journal of Security and its Applications. — 2013. — Vol. 7, N. 4. — P. 185-202.

[23] Hooker J.N., Garfinkel R.S., Chen C.K. Finite Dominating Sets for Network Location Problems // Operations Research. — 1991. — Vol. 39, N. 1. — P. 100-118.

[24] Визинг В.Г. Декартово произведение графов // Вычислительные системы. — 1963. — Т. 9. — С. 30-43.

[25] Визинг В.Г. Некоторые нерешённые задачи в теории графов // Успехи мат. наук. — 1968. — Т. 23. — С. 117-134.

[26] Clark W.E., Suen S. An Inequality Related To Vizing's Conjecture // The electronic journal of combinatorics. — 2000. — Vol. 7, N. 1. — Article N. 4.

[27] Suen S., Tarr J. An Improved Inequality Related to Vizing's Conjecture // The electronic journal of combinatorics. — 2012. — Vol. 19, N. 1. — P. P8.

[28] Krop E. Vizing's conjecture: A two-thirds bound for claw-free graphs // Discrete Applied Mathematics. — 2017. — Vol. 230. — P. 162-165.

[29] Karp R.M. Reducibility Among Combinatorial Problems // Complexity of Computer Computations (Proceedings of a symposium on the Complexity of Computer Computations, the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, March 20-22, 1972). — New York: Plenum Press, The IBM Research Symposia Series, 1972. — P. 85-103.

[30] Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. — San Francisco: W. H. Freeman and Co., A Series of Books in the Mathematical Sciences, 1979. — 340 P.

[31] Goddard W., Hedetniemi S.M., Hedetniemi S.T. Eternal Security in Graphs //J. Combin. Math. — 2005. — Vol. 52. — P. 169-180.

[32] Lemke P. The maximum-leaf spanning tree problem in cubic graphs is NP-complete // IMA Preprint Series, 1988. — N. 428.

[33] Zelinka B. Finding a Spanning Tree of a Graph with Maximal Number of Terminal Vertices // Kybernetika. — 1973. — Vol. 9, N. 5. — P. 357-360.

[34] Storer J.A. Constructing full spanning trees for cubic graphs // Inform. Process. Lett. — 1981. — Vol. 13, N. 1, I. 1. — P. 8-11.

[35] Griggs J.R., Kleitman D.J., Shastri A. Spanning trees with many leaves in cubic graphs // Journal of Graph Theory. — 1989. — Vol. 13, N. 6. — P. 669-695.

[36] Kleitman D.J., West D.B. Spanning trees with many leaves // SIAM J. Discrete Math. — 1991. — Vol. 4, N. 1. — P. 99-106.

[37] Griggs J.R., Wu M. Spanning trees in graphs of minimum degree 4 or 5 // Discrete Mathematics. — 1992. — Vol. 104, N. 2. — P. 167-183.

[38] Симарова Е.Н. Оценка количества листьев в остовном дереве связного графа с минимальной степенью 6 // Зап. научн. сем. ПОМИ. — 2017. — Т. 464. — С. 112—131.

[39] Bonsma P., Zickfeld F. Spanning trees with many leaves in graphs without diamonds and blossoms // Theoretical Informatics: Proc. of the 8th Latin American Symposium on Theoretical Informatics, Buzios, Brazil, April 7-11, 2008. — Heidelberg: Springer, Lecture Notes in Computer Science. — Vol. 4957. — P. 531-543.

[40] Гравин Н.В. Построение остовного дерева графа с большим количеством листьев // Зап. научн. семин. ПОМИ. — 2010. — Т. 381. — С. 31-46.

[41] Bankevich A.V., Karpov D.V. Bounds of the number of leaves of spanning trees //J. Math. Sci. — 2012. — Vol. 184. — P. 564-572.

[42] Карпов Д.В. Нижние оценки количества листьев в остовных деревьях // Зап. научн. сем. ПОМИ. — 2016. — Т. 450. — С. 62-73.

[43] Fusco E., Monti A. Spanning Trees with Many Leaves in Regular Bipartite Graphs // Algorithms and Computation: Proc. of the 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. — Heidelberg: Springer, Lecture Notes in Computer Science. — Vol. 4835. — P. 904-914.

[44] Sampathkumar E., Walikar H.B. The connected domination number of a graph //J. Math. Phys. Sci. — 1979. — Vol. 13, N. 6. — P. 607-613.

[45] Caro Y., West D.B., Yuster R. Connected domination and spanning trees with many leaves // SIAM J. Discrete Math. — 2000. — Vol. 13, N. 2. — P. 202-211.

[46] Hedetniemi S.T., Laskar R.C. Connected domination in Graphs // Graph theory and combinatorics: Proc. of the Cambridge Combinatorial Conference in honour of Paul Erdos on Graph Theory and Combinatorics, Cambridge, UK, March 21-25, 1983. — London: Academic Press, 1984. — P. 209-218.

[47] Gayathri M. Connected domination in graphs // Graduate Theses and Dissertations. — 2005. — URL: https://scholarcommons.usf.edu/etd/2961.

[48] Duckworth W, Mans B. Connected domination of regular graphs // Discrete Math. — 2009. — Vol. 309, N. 8. — P. 2305-2322.

[49] Desormeaux W.J., Haynes T.W., Henning M.A. Bounds on the connected domination number of a graph // Discrete Appl. Math. — 2013. — Vol. 161, N. 18. — P. 2925-2931.

[50] Das B.,Bhargavan V. Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets // ICC 1997: Proc. of the 6th International Conference on Communications, Montreal, Canada, June 8-12, 1997. — Vol. 1. — P. 376-380.

[51] Alzoubi K.M., Wan P.J, Frieder O. New distributed algorithm for connected dominating set in wireless ad hoc networks // System Sciences 2002: Proc. of the 35th Annual Hawaii International Conference on System Sciences, Big Island, HI, USA, January 10, 2002. — P. 3849-3855.

[52] Du D.Z., Wan P.J. Connected dominating set: theory and applications. — New York: Springer, Springer Optimization and Its Applications, 2013. — Vol. 77. — 206 P.

[53] Havel V. A remark on the existence of finite graphs (Czech.) // Cas. Pestovani Mat. — 1955. — Vol. 80. — P. 477-480.

[54] Hakimi S.L. On the realizability of a set of integers as degrees of the vertices of a graph // SIAM J. Appl. Math. — 1962. — Vol. 10. — P. 496-506.

[55] Erdos P., Gallai T. Grafok eloirt fokszamu pontokkal // Matematikai Lapok. — 1960. — Vol. 11. — P. 264—274.

[56] Wagner S. A class of trees and its Wiener index // Acta Appl. Math. — 2006. — Vol. 91, N. 2. — P. 119-132.

[57] Wang H., Yu G. All but 49 numbers are Wiener indices of trees // Acta Appl. Math. — 2006. — Vol. 92, N. 1. — P. 15-20.

[58] Czabarka E., Szekely L., Wagner S. The inverse problem for certain tree parameters // Discrete Applied Mathematics. — 2009. — Vol. 157, N. 15. — P. 3314-3319.

[59] Li X., Li Z., Wang L. The inverse problems for some topological indices in combinatorial chemistry //J. Comput. Biol. — 2003. — Vol. 10, N. 1. — P. 47-55.

[60] Linek V. Bipartite graphs can have any number of independent sets // Discrete Mathematics. — 1989. — Vol. 76, N. 2. — P. 131-136.

[61] Wagner S.G. Almost all trees have an even number of independent sets // Electron. J. Combin. — 2009. — Vol. 16, N. 1. — P. R93.

[62] Law H.-F. On the number of independent sets in a tree // Electr. J. Comb. — 2010. — Vol. 17. — P. N18.

[63] LiX., Zhao H., Gutman I. On the Merrifield-Simmons index of trees // MATCH Communications in Mathematical and in Computer Chemistry. — 2005. — Vol. 54, N. 2. — P. 389-402.

[64] Pedersen A.S., Vestergaard P.D. The Number of Independent Sets in Unicyclic Graphs // Discrete Appl. Math. — 2005. — Vol. 152, N. 1-3. — P. 246-256.

[65] Li S., Zhu Zh. The number of independent sets in unicyclic graphs with a given diameter // Discrete Appl. Math. — 2009. — Vol. 157, N. 7. — P. 1387-1395.

[66] Andriantiana E. Energy, Hosoya index and Merrifield-Simmons index of trees with prescribed degree sequence // Discrete Applied Mathematics. — 2013. — Vol. 161, N. 6. — P. 724-741.

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

[68] Moon J., Moser L. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Vol. 3, N. 1. — P. 23-28.

[69] JouM.-J., Chang G.J., Lin C.C., MaT.-H. A finiteness theorem for maximal independent sets //J. Graphs and Combinatorics. — 1996. — Vol. 12. — P. 321-326.

[70] Талецкий Д.С., Малышев Д.С. Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств // Дискретная математика. — 2018. — Т. 30, № 4. — С. 115-133.

[71] Furedi Z. The number of maximal independent sets in connected graphs // Journal of Graph Theory. — 1987. — Vol. 11, N. 4. — P.463-470.

[72] Griggs J., Grinstead C., Guichard D. The number of maximal independent sets in a connected graph // Discrete Mathematics. — 1988. — Vol. 68, N. 2-3. — P. 211-220.

[73] Wilf H. The number of maximal independent sets in a tree // SIAM Journal of Algebraic Discrete Methods. — 1986. — Vol. 7, N. 1. — P. 125-130.

[74] Sagan B.E. A note on independent sets in trees // SIAM J. Disc. Math. — 1988. — Vol. 1, N. 1. — P. 105-108.

[75] Liu J. Maximal independent sets in bipartite graphs // Journal of Graph Theory. — 1993. — Vol. 17, N. 4. — P. 495-507.

[76] Jin Z., Li X. Graphs with the second largest number of maximal independent sets // Discrete Mathematics. - 2008. - Vol. 308, N. 23. - P. 5864-5870.

[77] JouM.-J., Lin J.J. Trees with the second largest number of maximal independent sets // Discrete Mathematics. - 2009. - Vol. 309, N. 13. - P. 4469-4474.

[78] Jin Z., Yan S.H.F. Trees with the second and third largest number of maximal independent sets // Ars Combinatoria. - 2009. - Vol. 93. - P. 341-351.

[79] Jou M.-J., Lin J.J. Trees with the fourth largest number of maximal independent sets / / Ars Combinatoria. - 2013. - Vol. 109. - P. 299-308.

[80] Дайняк А.Б., Курносое А.Д. Об одной экстремальной обратной задаче теории графов // Дискретный анализ и исследование операций. — 2015. — Т. 22, № 1. — С. 19-31.

[81] Hakimi S.L. On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness // SIAM J. Appl. Math. - 1963. - Vol. 11, N. 1. - P. 135-147.

[82] Зыков А.А. Основы теории графов. — М.: Наука. Физматлит, 1987. — 384 С.

[83] Edmonds J. Existence of k-edge connected ordinary graphs with prescribed degrees // Journal of Research of the National Bureau of Standards. — 1964. — Vol. 68B, N. 2. — P. 73-74.

[84] Wang D. L., Kleitman D.J. On the existence of n-connected graphs with prescribed degrees (n ^ 2) // Networks. - 1973. - Vol. 3, N. 3. - P. 225-239.

[85] Gale D. A theorem on flows in networks // Pacific J. Math. - 1957. - Vol. 7, N. 2. -P. 1073-1082.

[86] Ryser H.J. Combinatorial properties of matrices of zeros and ones // Canad. J. Math. — 1957. - Vol. 9. - P. 371-377.

[87] Rao A.R. The clique number of a graph with given degree sequence // Graph Theory (Proc. Symp. on Graph Theory, Calcutta, India, December 20-25, 1976). — New Delhi: MacMillan and Co. India Ltd., ISI Lecture Notes, 1979. - Vol. 4. - P. 251-267.

[88] Kezdy A.E., Lehel J. Degree sequences of graphs with prescribed clique size // Combinatorics, Graph Theory, and Algorithms — 1999. — Vol. 2. — P. 535-544.

[89] Bessy S., Rautenbach D. Extremal Values of the Chromatic Number for a Given Degree Sequence // Graphs and Combinatorics. — 2017. — Vol. 33, N. 4. — P. 789-799.

[90] C. Lai The smallest degree sum that yields potentially Ck-graphical sequences //J. Comb. Math. Comb. Comput. — 2004. — Vol. 49. — P. 57-64.

[91] Yin J.-H. Degree sequences of graphs containing a cycle with prescribed length // Czechoslovak Mathematical Journal. — 2009. — Vol. 59, N. 134. — P. 481-487.

[92] Favaron O., Maheo M., Sacle J. On the residue of a graph //J. Graph Theory. — 1991. — Vol. 15, N. 1. — P.39-64.

[93] Griggs R., Kleitman D. Independence and the Havel-Hakimi Residue // Discrete Math. — 1994. — Vol. 127. — P. 209-212.

[94] Caro Y. New results on the independence number // Technical Report, Tel Aviv University. — 1979.

[95] Wei V.K. A lower bound on the stability number of a simple graph // Bell Laboratories Technical Memorandum, N. 81-11217-9, Murray Hill, NJ. — 1981.

[96] Harant J., Rautenbach D. Independence in connected graphs // Discrete Applied Mathematics. — 2011. — Vol. 159, N. 1. — P. 79-86.

[97] Gentner M., Henning M., Rautenbach D. Largest domination number and smallest independence number of forests with given degree sequence // Discrete Applied Mathematics. — 2016. — Vol. 206. — P. 181-187.

[98] Pepper R. On the Annihilation Number of a Graph // Recent advances in applied mathematics and computational and information sciences. — 2009. — Vol. 1. — P. 217220.

[99] Pepper R. Binding Independence // Ph.D. Dissertation, University of Houston. — 2004.

[100] Larson C.E., Pepper R. Graphs with equal Independence and Annihilation Numbers // Electron. J. Combin. — 2011. — Vol. 18. — P. 180.

[101] Gentner M., Henning M., Rautenbach D. Smallest domination number and largest independence number of graphs and forests with given degree sequence // Journal of Graph Theory. — 2018. — Vol. 88, N. 1. — P. 131-145.

[102] Курносое А.Д., Дайняк А.Б. Независимые множества в деревьях с заданными степенными последовательностями // Труды IX Международной конференции «Дискретные модели в теории управляющих систем», Красновидово, Московская область, 20-22 мая, 2015. — С. 141-142.

[103] Dehgardi N., Norouzian S. and Sheikholeslami S.M. Bounding the domination number of a tree in terms of its annihilation number // Transactions on Combinatorics. — 2013. — Vol. 2, N. 1. — P. 9-16.

[104] Favaron O. A bound on the independent domination number of a tree // Vishwa International Journal of Graph Theory. — 1992. — Vol. 1, N. 1. — P. 19-27.

[105] Курносое А.Д. Множество всех возможных значений числа доминирования в деревьях с заданной степенной последовательностью // Дискретный анализ и исследование операций. 2020. — Т. 27, № 1. — С. 61-87.

[106] Lemanska M. Lower bound on the domination number of a tree // Discussiones Mathematicae, Graph Theory. — 2004. — Vol. 24. — P. 165-169.

[107] Slater P. J. Locating dominating sets and locating-dominating sets // Graph Theory, Combinatorics and Applications (Proc. Seventh Quad. Internat. Conf. on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, USA, June 1-5, 1992). — New York: Wiley, 1995. — Vol. 2. — P. 1073-1079.

[108] Desormeaux W. J, Haynes T. W, Henning M. A. Improved bounds on the domination number of a tree // Discrete Applied Mathematics. — 2014. — Vol. 177. — P. 88-94.

[109] Курносое А.Д. О нижней оценке числа связного доминирования в графах с фиксированной степенной последовательностью // Труды МФТИ. — 2020. — Т. 12, № 2. — С. 40-54.

[110] Jaume D.A., Pastine A., Schvollner V.N. 2-switch: transition and stability on graphs and forests. — URL: https://arxiv.org/abs/2004.11164.

[111] Kaspar S., Gayathri B., Kulandaivel M.P., Shobanadevi N. Towards connected domination in graphs // International Journal of Pure and Applied Mathematics. — 2017. — Vol. 117, N. 14. — P. 53-62.