Вечное доминирующее множество

В теории графов вечное или бессмертное доминирующее множество для графа G = (V, E) — это подмножество D вершин V, такое, что D является доминирующим множеством, на котором располагается мобильная охрана первоначально (не более одного охранника может находиться в одной вершине). Множество D должно быть таким, что для любой бесконечной последовательности атак на вершины множество D может быть модифицировано путём передвижения охранника со смежной вершины на атакуемую вершину, если атакуемая вершина не была занята охранником во время атаки. Конфигурация охранников должна после каждой атаки и движения охранника образовывать доминирующее множество. Вечное доминирующее число, γ_∞(G), — это минимальное число вершин во всех таких множествах D. Например, вечное доминирующее число цикла из пяти вершин равно трём.

Задача о вечном доминирующем множестве, известная также как задача о вечном доминировании, может быть представлена как Шаблон:Не переведено 5 между двумя игроками, делающими ходы поочерёдно — защищающаяся сторона выбирает начальное доминирующее множество D и посылает охранника в атакуемую вершину, если в ней не было охранника. Атакующая же сторона в свой ход выбирает, какую вершину она будет атаковать. Атакующая сторона выигрывает, если она может атаковать вершину, рядом с которой нет охранников. Другими словами, атакующая сторона выигрывает игру, если после нескольких атак она сможет атаковать незащищённую вершину.

Как заметили Клостермейер и МинхардтШаблон:Sfn, вечное доминирующее множество связано с задачей о k официантах.

История

Мотивом для понятия послужили древние задачи военной защиты, описанные в серии статей (Арквилла, Фредриксон, РеВелле, Россинг, СтьюартШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn). Задача о вечном доминировании была впервые описана в 2004 в статье Бюргера, Кокейна и ГрудлингхаШаблон:Sfn. Затем последовала публикация статьи о вечном доминировании В. Годдарда, С. М. Хедетними и С. Т. ХедетнимиШаблон:Sfn, в которой был изложен вариант задачи, названный m-вечным доминированием. В этой задаче все охранники, если они хотят, могут двигаться за один ход на соседние вершины в ответ на атаку, как только один охранник передвигается на атакуемую вершину (предполагается, что на атакуемой вершине нет охранника, в противном случае охранники не передвигаются). После статьи В. Годдарда, С. М. Хедетними и С. Т. Хедетними появился ряд статей других авторов. В этой последовательности статей были предложены некоторые другие варианты задачи вечного доминирования, включая задачи вечного покрытия вершин, вечного независимого множества, вечных тотально доминирующих множеств, вечных связных доминирующих множеств и вечных доминирующих множеств в модели изгнания (в этой модели требуется, чтобы при атаке занятой охранником вершины тот должен переместиться на соседнюю свободную вершину, если такая есть). Обзорная статья с описанием многих других результатов по задачам о вечном доминировании и многих вариаций задачи можно найти у Клостермейера и МинхардтаШаблон:Sfn.

Границы

Пусть G — граф с n ≥ 1 вершинами. Вечное доминирующее число не меньше доминирующего числа γ(G) (тривиальный факт). Годдард и Хедетмини в своей статье доказали, что вечное доминирующее число не меньше числа независимости графа G и не больше минимального размера кликового покрытия графа G (минимальный размер кликового покрытия графа G равен хроматическому числу дополнения графа G). Таким образом, согласно теореме о совершенных графах, вечное доминирующее число графа G равно минимальному размеру кликового покрытия графа G для всех совершенных графов. Было показано, что вечное доминирующее число графа G равно минимальному размеру кликового покрытия графа G для некоторых других классов графов, таких как графы дуг окружности (как показал РеганШаблон:Sfn) и параллельно-последовательные графы (как показали Андерсон, Барриентос и ХедетнимиШаблон:Sfn). В. Годдарда, С. М. Хедетними и С. Т. Хедетними также продемонстрировали граф, у которого вечное доминирующее множество графа меньше минимального размера кликового покрытия.

Клочтермейер и МакГилливрей доказалиШаблон:Sfn, что вечное доминирующее число графа с числом независимости α не превосходит α(α + 1)/2. Голдвассер и КлостермейерШаблон:Sfn доказали, что существует бесконечно много графов, у которых вечное доминирующее множество в точности равно α(α + 1)/2.

Границы m-вечного доминантного множества

Годдард и Хедетмини доказали, что m-вечное доминирующее число, обозначаемое γ^m_∞(G), не превосходит числа независимости графа G. Следовательно, параметры вечного доминирования хорошо укладываются в знаменитую цепочку параметров доминированияШаблон:Sfn:

γ(G) ≤ γ^m_∞(G) ≤ α(G) ≤ γ_∞(G) ≤ θ(G),

где θ(G) означает минимальный размер кликового покрытия графа G, а γ_∞(G) — вечное доминирующее число.

Верхняя граница ⌈n/2⌉ параметра γ^m_∞(G) для графов с n вершинами была доказана в статье Чамберса, Киннерсли и ПринцаШаблон:Sfn. См. также статью Клостермейера и МинхардтаШаблон:Sfn.

В решётке m-вечное доминирующее число получило повышенное внимание, вызванное вниманием к доминирующим числам решёток (см. статью Хайнеса, Хедетмини и СлейтераШаблон:Sfn и статью Гонсалвеса, Пинлоу и РаоШаблон:Sfn). В решётках m-вечное доминирующее число первыми изучали Голдвассер, Клостермейер и МинхардтШаблон:Sfn, где они показали, что

γ^m_∞ = ⌈2n/3⌉ для решёток 2 на n с n ≥ 2

и

γ^m_∞ ≤ ⌈8n/9⌉ для решёток 3 на n.

Последнее неравенство улучшили Финбоу, Мессинджер и ван БоммельШаблон:Sfn до

1 + ⌈4n/5⌉ ≤ γ^m_∞ ≤ 2 + ⌈4n/5⌉

где n ≥ 11. Эта граница была затем слегка улучшена для некоторых случаев в статье Мессинджера и ДеланиШаблон:Sfn.

Случаи решёток 4 на n и 5 на n рассматриваются в статье Битона, Финбоу и МакДональдаШаблон:Sfn и в статье Мартина ван Боммеля и Христофера ван БоммеляШаблон:Sfn соответственно.

Брага, де Соуза и ЛиШаблон:Sfn доказали, что γ^m_∞ = α для всех корректных интервальных графов и те же авторы также доказалиШаблон:Sfn, что существует граф Кэли, для которого m-вечное доминирующее число не равно доминирующему множеству, вопреки утверждению в статье В. Годдарда, С. М. Хедетними и С. Т. ХедетнимиШаблон:Sfn.

Открытые вопросы

Согласно Клостермейеру и МинхардтуШаблон:Sfn, одним из главных нерешённых вопросов является следующий: Существует ли граф G, такой, что γ(G) равен вечному доминирующему числу графа G и γ(G) меньше минимального размера кликового покрытия графа G? Клостермейер и Минхардт показали Шаблон:Sfn, что любой такой граф должен содержать треугольники и максимальная степень вершин графа должна быть не меньше четырёх.

Для доминирующих множеств неизвестно, верно ли для всех графов G и H неравенство (по аналогии с гипотезой Визинга)

${\gamma }_{\mathrm{\infty }}(G◻H)\ge {\gamma }_{\mathrm{\infty }}(G){\gamma }_{\mathrm{\infty }}(H).$

Известно, что аналогичное неравенство выполняется не для всех графов G and H в случае задачи о m-вечном доминировании, что показали Клостермейер и МинхардтШаблон:Sfn.

Два фундаментальных открытых вопроса о вечном доминировании указаны Дугласом Вестом на сайте Eternal Domination Number. А именно, равно ли γ_∞(G) минимальному размеру кликового покрытия для всех планарных графов G и ограничено ли γ_∞(G) снизу числом Ловаса, известным также как тэта-функция Ловаса.

Некоторое число открытых вопросов перечислено в статье Клостермейера и МинхардтаШаблон:Sfn, включая упомянутые выше вопросы о вариантах вечных доминирующих множеств.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья