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

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

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

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

ИсторияПравить

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

ГраницыПравить

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

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

Открытые вопросыПравить

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

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

${\mathrm{\gamma <!--\; \gamma \; -->}}_{\mathrm{\infty <!--\; \infty \; -->}}(G\mathrm{◻<!--\; ◻\; -->}H)\ge <!--\; \ge \; -->{\mathrm{\gamma <!--\; \gamma \; -->}}_{\mathrm{\infty <!--\; \infty \; -->}}(G){\mathrm{\gamma <!--\; \gamma \; -->}}_{\mathrm{\infty <!--\; \infty \; -->}}(H).$$\gamma _{\infty }(G\,\Box \,H)\geq \gamma _{\infty }(G)\gamma _{\infty }(H).$ 

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

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

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

ЛитератураПравить

• Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniem. Eternal Security in Graphs // J. Combin. Math.. — 2005. — Т. 52. — С. 169–180..
• M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray, J. Yellen. Maximum demand graphs for eternal security // J. Combin. Math. Combin. Comput. — 2007. — Т. 61. — С. 111–128.
• H. Arquilla, H. Frederickson. Graphing an optimal grand strategy // Military Operations Research. — 1995. — Т. 1. — С. 3–17. — doi:10.5711/morj.1.3.3.
• I. Beaton, S. Finbow, J. MacDonald. Eternal domniation set problem of grids // J. Combin. Math. Combin. Comput. — 2013. — Т. 85. — С. 33–38.
• A. Braga, C. de Souza, O. Lee. The eternal domniating set problem for proper interval graphs // Information Processing Letters. — 2015a. — С. 582–587. — doi:10.1016/j.ipl.2015.02.004.
• A. Braga, C. de Souza, O. Lee. A note on the paper "Eternal security in graphs" by Goddard, Hedetniemi, and Hedetniemi (2005). — 2015b.
• A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J. van Vuuren, W. Winterbach. Infinite order domination in graphs // J. Combin. Math. Combin. Comput. — 2004. — Т. 50. — С. 179–194.
• E. Chambers, B. Kinnersly, N. Prince. Mobile eternal security in graphs // Unpublished manuscript. — 2006. Архивировано 30 сентября 2015 года.
• S. Finbow, M-E. Messinger, M. van Bommel. Eternal domination in 3 x n grids // Australas. J. Combin.. — 2015. — Т. 61. — С. 156–174.
• J. Goldwasser, W. Klostermeyer. Tight bounds for eternal dominating sets in graphs // Discrete Math.. — 2008. — Т. 308. — С. 2589–2593. — doi:10.1016/j.disc.2007.06.005.
• J. Goldwasser, W. Klostermeyer, C. Mynhardt. Eternal protection in grid graphs // Utilitas Math.. — 2013. — Т. 91. — С. 47–64.
• D. Goncalves, A. Pinlou, M. Rao, S. Thomasse. The domination number of grids // SIAM Journal of Discrete Mathematics. — 2011. — Т. 25. — С. 1443–1453. — doi:10.1137/11082574.
• Teresa W. Haynes, Stephen Hedetniemi, Peter Slater. Fundamentals of Domination in Graphs. — 1998a. — ISBN 0-8247-0033-3.
• W. Klostermeyer, G. MacGillivray. Eternal security in graphs of fixed independence number // J. Combin. Math. Combin. Comput. — 2007. — Т. 63. — С. 97–101.
• W. Klostermeyer, C. Mynhardt. Domination, Eternal Domination, and Clique Covering // Discuss. Math. Graph Theory. — 2015a. — С. 283. — doi:10.7151/dmgt.1799.
• W. Klostermeyer, C. Mynhardt. Protecting a graph with mobile guards. — 2015b. — С. 21. — doi:10.2298/aadm151109021k. — arXiv:1407.5228.
• M-E. Messinger, A. Delaney. Closing the gap: Eternal domination on 3 x n grids. — 2015.
• F. Regan. Dynamic variants of domination and independence in graphs // graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, Germany. — 2007.
• C. ReVelle. Can you protect the Roman Empire? // Johns Hopkins Magazine. — 1997. — Т. 2.
• C. ReVelle, K. Rosing. Defendens Imperium Romanum: A classical problem in military strategy // Amer. Math. Monthly. — 2000. — Т. 107. — С. 585–594. — doi:10.2307/2589113.
• I. Stewart. Defend the Roman Empire! // Scientific American. — 1999. — Т. 281. — С. 136–138. — doi:10.1038/scientificamerican1299-136.
• C. van Bommel, M. van Bommel. Eternal domination number of 5 x n grids // J. Combin. Math. Combin. Comput. — 2015.