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

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

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

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

История

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

Границы

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

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

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

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

γ (грамм) ≤ γм∞(грамм) ≤ α (грамм) ≤ γ∞(грамм) ≤ θ(грамм)

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

Верхняя граница ⌈п/ 2⌉ на γм∞(грамм) для графов с п вершины были доказаны в Чемберс, Киннерсли и принц (2006), смотрите также Клостермейер и Минхардт (2015b).

В м- число вечного доминирования в сеточных графах привлекло внимание, вдохновленное вниманием, уделяемым доминирующему количеству сеточных графов, см. Хейнс, Хедетниеми и Слейтер (1998a) и Гонсалвес, Пинлу и Рао (2011). В м-вечное число доминирования в сеточных графах впервые было изучено в Гольдвассер, Клостермейер и Минхардт (2013) где было показано, что

γм∞ = ⌈2п/ 3⌉ в пользу 2 п сетка с п ≥ 2

и

γм∞ ≤ ⌈8п/ 9⌉ для 3 по п сетки.

Последний был улучшен в Финбоу, Мессинджер и ван Боммель (2015) к

1 + ⌈4п/5⌉ ≤ γм∞ ≤ 2 + ⌈4п/5⌉

когда п ≥ 11. Эта оценка была впоследствии несколько улучшена в Мессинджер и Делани (2015) в некоторых случаях. Наконец, границы были закрыты в Финбоу и ван Боммел (2020), где показано, что

γм∞ = ⌈(4п+7) / 5⌉ для п ≥ 22.

Шкафы для 4 по и сеток и 5 по п сетки рассматривались в Битон, Финбоу и Макдональд (2013) и ван Боммель и ван Боммель (2015), соответственно.

Брага, де Соуза и Ли (2015) доказал, что γм∞ = α для всех собственных интервальных графов и те же авторы доказали, см. Брага, де Соуза и Ли (2016), что существует Граф Кэли для чего м- число вечного господства не равно числу господства, вопреки утверждению в Годдард, Хедедтниеми и Хедетниеми (2005).

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

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

Похожий на Гипотеза Визинга для доминирующих множеств неизвестно, для всех ли графов грамм и ЧАС

Известно, что аналогичная оценка верна не для всех графов грамм и ЧАС для м- проблема вечного доминирования, как показано на Клостермейер и Минхардт (2015a).

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

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

Рекомендации

  • Андерсон, М .; Barrientos, C .; Brigham, R .; Carrington, J .; Vitray, R .; Йеллен, Дж. (2007), «Графики максимального спроса для вечной безопасности», J. Combin. Математика. Комбинировать. Comput., 61: 111–128.
  • Arquilla, H .; Фредериксон, Х. (1995), "График оптимальной большой стратегии", Исследования военных операций, 1 (3): 3–17, Дои:10.5711 / morj.1.3.3, HDL:10945/38438.
  • Битон, I .; Finow, S .; Макдональд, Дж. (2013), «Проблема вечного господства сеток», J. Combin. Математика. Комбинировать. Comput., 85: 33–38.
  • Брага, А .; de Souza, C .; Ли, О. (2015), "Вечная проблема доминирующего множества для правильных интервальных графов", Письма об обработке информации, 115 (6–8): 582–587, Дои:10.1016 / j.ipl.2015.02.004.
  • Брага, А .; de Souza, C .; Ли, О. (2016), «Заметка к статье Годдарда, Хедетниеми и Хедетниеми« Вечная безопасность в графиках »(2005)», Журнал комбинаторной математики и комбинаторных вычислений, 96: 13–22.
  • Burger, A.P .; Cockayne, E.J .; Grundlingh, W.R .; Mynhardt, C.M .; van Vuuren, J .; Винтербах, В. (2004), "Бесконечное доминирование порядка в графах", J. Combin. Математика. Комбинировать. Comput., 50: 179–194.
  • Chambers, E .; Kinnnersly, B .; Принц, Н. (2006), «Мобильная вечная безопасность в графиках», Неопубликованная рукопись, заархивировано из оригинал в 2015-09-30, получено 2015-02-21.
  • Finbow, S .; Messinger, M-E .; ван Боммель, М. (2015), «Вечное господство в сетках 3 x n», Австралас. J. Combin., 61: 156–174.
  • Finbow, S .; ван Боммель, М.Ф. (2020), «Число вечного господства для сеточных графиков 3 x n», Австралас. J. Combin., 71: 1–23.
  • Goldwasser, J .; Клостермейер, W. (2008), "Тесные границы для вечных доминирующих множеств в графах", Дискретная математика., 308 (12): 2589–2593, Дои:10.1016 / j.disc.2007.06.005.
  • Goldwasser, J .; Klostermeyer, W .; Mynhardt, C. (2013), «Вечная защита в сеточных графах», Utilitas Math., 91: 47–64.
  • Goncalves, D .; Pinlou, A .; Rao, M .; Thomasse, S. (2011), "Преобладающее число решеток", Журнал SIAM по дискретной математике, 25 (3): 1443–1453, arXiv:1102.5206, Дои:10.1137/11082574.
  • Хейнс, Тереза ​​В.; Хедетниеми, Стивен; Слейтер, Питер (1998a), Основы доминирования в графах, Марсель Деккер, ISBN  0-8247-0033-3, OCLC  37903553.
  • Klostermeyer, W .; Макгилливрей, Г. (2007), "Вечная безопасность в графах с фиксированным числом независимости", J. Combin. Математика. Комбинировать. Comput., 63: 97–101.
  • Klostermeyer, W .; Минхардт, К. (2015a), «Доминирование, вечное господство и прикрытие клики», Обсуждать. Математика. Теория графов, 35 (2): 283, arXiv:1407.5235, Дои:10.7151 / dmgt.1799.
  • Klostermeyer, W .; Mynhardt, C. (2015b), «Защита графа с помощью мобильных охранников», Применимый анализ и дискретная математика, 10: 21, arXiv:1407.5228, Дои:10.2298 / aadm151109021k.
  • Messinger, M-E .; Делани, А. (2015), Устранение разрыва: вечное господство на сетках 3 x n.
  • Реган, Ф. (2007), Динамические варианты доминирования и независимости в графах, Университет Рейнишен Фридрих-Вильлемс.
  • ReVelle, C. (2007), «Сможете ли вы защитить Римскую империю?», Журнал Джона Хопкинса, 2.
  • ReVelle, C .; Розинг, К. (2000), "Defendens Imperium Romanum: классическая проблема военной стратегии", Амер. Математика. Ежемесячно, 107 (7): 585–594, Дои:10.2307/2589113, JSTOR  2589113.
  • Стюарт, I. (1999), «Защищай Римскую империю!», Scientific American, 281 (6): 136–138, Bibcode:1999SciAm.281f.136S, Дои:10.1038 / Scientificamerican1299-136.
  • van Bommel, C .; ван Боммель, М. (2016), "Число вечного господства 5 x n сеток", J. Combin. Математика. Комбинировать. Вычислить, 97: 83–102.