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

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

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

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

История

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

Границы

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

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

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

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

γ(G) ≤ γm∞(G) ≤ α(G) ≤ γ∞(G) ≤ θ(G),

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

Примечания
  1. Klostermeyer, Mynhardt, 2015b.
  2. Arquilla, Frederickson, 1995.
  3. ReVelle, 1997.
  4. ReVelle, Rosing, 2000.
  5. Stewart, 1999.
  6. Burger, Cockayne, Grundlingh, 2004.
  7. Goddard, Hedetniemi, Hedetniemi, 2005.
  8. Regan, 2007.
  9. Anderson, Barrientos, Brigham, 2007.
  10. Klostermeyer, MacGillivray, 2007.
  11. Goldwasser, Klostermeyer, 2008.
  12. Haynes, Hedetniemi, Slater, 1998a.
  13. Chambers, Kinnersly, Prince, 2006.
  14. Goncalves, Pinlou, Rao, 2011.
  15. Goldwasser, Klostermeyer, Mynhardt, 2013.
  16. Finbow, Messinger, van Bommel, 2015.
  17. Messinger, Delaney, 2015.
  18. Beaton, Finbow, MacDonald, 2013.
  19. van Bommels, 2015.
  20. Braga, de Souza, Lee, 2015a.
  21. Braga, de Souza, Lee, 2015b.
  22. Klostermeyer, Mynhardt, 2015a.

Литература
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.