Вечный доминирующий набор

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

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

Как отмечается в работе Klostermeyer & Mynhardt (2015b) , проблема вечного доминирующего множества связана с проблемой k -сервера в информатике.

История

Руководствуясь древними проблемами военной обороны, описанными в серии статей Arquilla & Fredricksen (1995) , ReVelle & Rosing (2000) и Stewart (1999) ,проблема вечного доминирования была первоначально описана в 2004 году в статье Бургера и др. (2004) . статьи о вечном доминировании За этим последовала публикация Годдарда, Хедетниеми и Хедетниеми (2005) , в которой также был представлен вариант проблемы, называемый m – вечное доминирование, в котором всем стражам разрешено перемещаться в соседние вершины, если они этого хотят в ответ на атаку, пока один охранник перемещается в атакуемую вершину (при условии, что в атакованной вершине не было охранника, в противном случае охраннику не нужно двигаться).После статьи Годдарда, Хедетниеми и Хедетниеми (2005) в математической литературе появился ряд статей других авторов. В этих последующих статьях было предложено несколько дополнительных вариаций проблемы вечного доминирования, включая проблему вечного вершинного покрытия, проблему вечного независимого множества, вечные полные доминирующие множества, вечные связные доминирующие множества и вечные доминирующие множества в модели выселения (последняя модель требует, чтобы при атаке вершина с защитой и охранник перемещалась в соседнюю вершину, которая не содержит защиты, если таковая имеется). Обзорный документ, описывающий многие результаты по проблеме вечного доминирования и многие варианты этой проблемы, можно найти по адресу Клостермайер и Минхардт (2015b) .

Границы

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

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

Границы m числа вечного господства

Годдард, Хедетниеми и Хедетниеми доказали число m -вечного доминирования, обозначаемое γ. ^м _∞ ( G ), не более чем число независимости G . Следовательно, параметры вечного доминирования прекрасно вписываются в знаменитую цепочку параметров доминирования, см. ( Haynes, Hedetniemi & Slater 1998a ), а именно:

γ( G ) ≤ γ ^м _∞ ( грамм ) ≤ α( грамм ) ≤ γ _∞ ( грамм ) ≤ θ ( грамм )

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

Верхняя граница ⌈ n /2⌉ на γ ^м _∞ ( G ) для графов с n вершинами было доказано в Chambers, Kinnersly & Prince (2006) , см. также Klostermeyer & Mynhardt (2015b) .

Вечное число доминирования в сеточных графах привлекло внимание, вдохновленное вниманием, уделяемым числу доминирования в сеточных графах, см. Haynes, Hedetniemi & Slater (1998a) и Goncalves et al. (2011) . Число вечного доминирования в сеточных графах впервые изучалось в работе Goldwasser, Klostermeyer & Mynhardt (2013) , где было показано, что

с ^м _∞ = ⌈2 n /3⌉ для сетки 2 на n с n ≥ 2

и

с ^м _∞ ≤ ⌈8 n /9⌉ для сеток 3× n .

Последний был улучшен в Finbow, Messinger & van Bommel (2015) до

1 + ⌈4 н /5⌉ ≤ с ^м _∞ ≤ 2 + ⌈4 n /5⌉

когда n была немного улучшена в работе Messinger & Delaney (2015) ≥ 11. Впоследствии эта граница в некоторых случаях . Наконец, границы были закрыты в работе Finbow & van Bommel (2020) , где было показано, что

с ^м _∞ = ⌈(4 n +7)/5⌉ для n ≥ 22.

Случаи сеток размером 4 и n и сеток 5 x n рассматривались в работах Beaton, Finbow & MacDonald (2013) и van Bommel & van Bommel (2016) соответственно.

Брага, де Соуза и Ли (2015) доказали, что γ ^м _∞ = α для всех правильных интервальных графов, и те же авторы также доказали (см. Braga, de Souza & Lee (2016)) , что существует граф Кэли , для которого m -вечное число доминирования не равно числу доминирования, в отличие от иск в Goddard, Hedetniemi & Hedetniemi (2005) .

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

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

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

$\gamma _{\infty }(G\,\Box \,H)\geq \gamma _{\infty }(G)\gamma _{\infty }(H).$

Известно, что аналогичная оценка не справедлива для всех графов G и H для задачи m -вечного доминирования, как показано в работе Klostermeyer & Mynhardt (2015a) .

Два фундаментальных открытых вопроса о вечном господстве перечислены Дугласом Уэстом в [1] . А именно, равен ли γ _∞ ( G ) числу покрытия клики для всех плоских графов G и может ли γ _∞ ( G ) быть ограничено снизу числом Ловаса , также известным как тэта-функция Ловаса.

поставлен ряд других открытых вопросов В обзорной статье Klostermeyer & Mynhardt (2015b) , включая множество вопросов о вариациях вечных доминирующих множеств, упомянутых выше.

Ссылки

• Андерсон, М.; Барриентос, К.; Бригам, Р.; Кэррингтон, Дж.; Витрей, Р.; Йеллен, Дж. (2007), «Графики максимального спроса для вечной безопасности» , Дж. Комбин. Математика. Комбинировать. Вычислить. , 61 : 111–128 .
• Аркилла, Х.; Фредриксен, Х. (1995), «Построение графика оптимальной большой стратегии», Military Operations Research , 1 (3): 3–17, doi : 10.5711/morj.1.3.3 , hdl : 10945/38438 , JSTOR   43940682 .
• Битон, И.; Финбоу, С.; Макдональд, Дж. (2013), «Проблема вечного доминирования сеток», Дж. Комбин. Математика. Комбинировать. Вычислить. , 85 : 33–38 .
• Брага, А.; де Соуза, К.; Ли, О. (2015), «Проблема о вечном доминирующем множестве для правильных интервальных графов», Information Processing Letters , 115 (6–8): 582–587, doi : 10.1016/j.ipl.2015.02.004 .
• Брага, А.; де Соуза, К.; Ли, О. (2016), «Заметка к статье Годдарда, Хедетниеми и Хедетниеми (2005) «Вечная безопасность в графах»», Журнал комбинаторной математики и комбинаторных вычислений , 96 : 13–22 .
• Бургер, АП; Кокейн, Э.Дж.; Грундлинг, WR; Минхардт, CM; ван Вуурен, Дж.; Винтербах, В. (2004), «Доминирование бесконечного порядка в графах», Дж. Комбин. Математика. Объединить. Вычислить. , 50 : 179–194 .
• Чемберс, Э.; Кинерсли, Б.; Принс, Н. (2006), «Вечная мобильная безопасность в графиках» , неопубликованная рукопись , заархивировано из оригинала 30 сентября 2015 г. , получено 21 февраля 2015 г.
• Финбоу, С.; Мессингер, Мэн; ван Боммель, М. (2015), «Вечное доминирование в сетках 3 xn», Австралия. Дж. Комбин. , 61 : 156–174 .
• Финбоу, С.; ван Боммел, МФ (2020), «Число вечного доминирования для графов с сеткой 3 xn», Австралия. Дж. Комбин. , 71 : 1–23 .
• Годдард, Уэйн; Хедетниеми, Сандра М.; Хедетниеми, Стивен Т. (январь 2005 г.). «Вечная безопасность в графах» . Журнал комбинаторной математики и комбинаторных вычислений . 52 .
• Гольдвассер, Дж.; Клостермайер, В. (2008), «Точные границы для вечных доминирующих множеств в графах», Discrete Math. , 308 (12): 2589–2593, doi : 10.1016/j.disc.2007.06.005 .
• Гольдвассер, Дж.; Клостермайер, В.; Минхардт, К. (2013), «Вечная защита в сеточных графах», Utilitas Math. , 91 : 47–64 .
• Гонсалвес, Д.; Пинлоу, А.; Рао, М.; Томасс, С. (2011), «Число доминирования сеток», SIAM Journal on Discrete Mathematics , 25 (3): 1443–1453, arXiv : 1102.5206 , doi : 10.1137/11082574 .
• Хейнс, Тереза ​​В .; Хедетниеми, Стивен; Слейтер, Питер (1998a), Основы доминирования в графиках , Марсель Деккер, ISBN  0-8247-0033-3 , OCLC   37903553 .
• Клостермайер, В.; МакГилливрей, Г. (2007), «Вечная безопасность в графах с фиксированным числом независимости», Дж. Комбин. Математика. Объединить. Вычислить. , 63 : 97–101 .
• Клостермайер, В.; Минхардт, К. (2015a), «Доминирование, вечное господство и прикрытие клики», Обсудить. Математика. Теория графов , 35 (2): 283, arXiv : 1407.5235 , doi : 10.7151/dmgt.1799 .
• Клостермайер, В.; Минхардт, К. (2015b), «Защита графа с помощью мобильных охранников», Applicable Analysis and Discrete Mathematics , 10:21 , arXiv : 1407.5228 , doi : 10.2298/aadm151109021k .
• Мессингер, Мэн; Делани, А. (2015), Ликвидация разрыва: вечное доминирование на сетках 3xn .
• Риган, Ф. (2007), Динамические варианты доминирования и независимости в графах , Рейнский университет Фридриха-Вильлемса .
• РеВелл, К. (2007), «Сможете ли вы защитить Римскую империю?», Журнал Джонса Хопкинса , 2 .
• РеВель, К.; Розинг, К. (2000), «Defendens Imperium Romanum: классическая проблема военной стратегии», Amer. Математика. Monthly , 107 (7): 585–594, doi : 10.2307/2589113 , JSTOR   2589113 .
• Стюарт, И. (1999), «Защитите Римскую империю!», Scientific American , 281 (6): 136–138, Бибкод : 1999SciAm.281f.136S , doi : 10.1038/scientificamerican1299-136 .
• ван Боммель, К.; ван Боммель, М. (2016), «Вечное число доминирования в сетках 5 xn», Дж. Комбин. Математика. Комбинировать. Компьютер , 97 : 83–102 .