Wiecznie dominujący zestaw

W teorii grafów wieczny zbiór dominujący dla grafu G = ( V , E ) jest podzbiorem D z V takim, że D jest zbiorem dominującym , na którym początkowo znajdują się ruchome osłony (co najwyżej jeden strażnik może znajdować się na dowolnym wierzchołku) . Zbiór D musi być taki, aby dla dowolnej nieskończonej sekwencji ataków zachodzących sekwencyjnie w wierzchołkach zbiór D mógł być modyfikowany przez przesunięcie strażnika z sąsiedniego wierzchołka do atakowanego wierzchołka, pod warunkiem, że atakowany wierzchołek nie ma na nim żadnej osłony w czasie jest atakowany. Konfiguracja osłon po każdym ataku musi wywołać zestaw dominujący. Wieczna liczba dominacji γ _∞ ( G ) to minimalna możliwa liczba wierzchołków w zbiorze początkowym D . Na przykład liczba wiecznej dominacji cyklu na pięciu wierzchołkach wynosi dwa.

Problem wiecznego zestawu dominującego, znany również jako problem wiecznej dominacji i problem wiecznego bezpieczeństwa, może być również interpretowany jako gra kombinatoryczna rozgrywana między dwoma graczami, którzy naprzemiennie turami: obrońcą, który wybiera początkowy zestaw dominujący D i strażnikiem do wysłania do każdego ataku, który występuje w wierzchołku bez osłony; oraz atakujący, który w swojej turze wybiera wierzchołek, który ma zostać zaatakowany. Atakujący wygrywa grę, jeśli kiedykolwiek uda mu się wybrać wierzchołek do ataku w taki sposób, że na tym wierzchołku lub na sąsiednim wierzchołku nie ma strażnika; w przeciwnym razie obrońca wygrywa. Innymi słowy, atakujący wygrywa grę, jeśli kiedykolwiek może zaatakować wierzchołek w taki sposób, że ataku nie można obronić.

Jak zauważono w Klostermeyer i Mynhardt (2015b) , problem wiecznego zbioru dominującego jest powiązany z problemem k -serwera w informatyce.

Historia

Zmotywowany starożytnymi problemami obrony wojskowej opisanymi w serii artykułów Arquilla i Fredricksen (1995) , ReVelle (1997) , ReVelle & Rossing (1999 ) i Stewart (1999) , problem wiecznej dominacji został po raz pierwszy opisany w 2004 roku w artykule Burgera, Cockayne'a i Grundlingha (2004) . Następnie opublikowano artykuł Hedetniemi & Hedetniemi (2005) temat wiecznej dominacji strażnicy mogą przesuwać się do sąsiednich wierzchołków, jeśli sobie tego życzą, w odpowiedzi na atak, o ile jeden strażnik przesuwa się do atakowanego wierzchołka (zakładając, że na atakowanym wierzchołku nie było strażnika, w przeciwnym razie żaden strażnik nie musi się poruszać). Po artykule Goddard, Hededtniemi & Hedetniemi (2005) , w literaturze matematycznej pojawiło się wiele artykułów innych autorów. W tych kolejnych artykułach zaproponowano kilka dodatkowych wariacji na temat problemu wiecznej dominacji, w tym problem wiecznego pokrycia wierzchołków, problem wiecznego zbioru niezależnego, wieczne totalne zbiory dominujące, wiecznie połączone zbiory dominujące i wieczne zbiory dominujące w modelu eksmisji (ten ostatni model wymaga, aby podczas ataków wierzchołek ze strażnikiem i strażnikiem musiał przejść do sąsiedniego wierzchołka, który nie zawiera strażnika, jeśli taki istnieje). Artykuł opisujący wiele wyników dotyczących problemu wiecznej dominacji i wiele odmian tego problemu można znaleźć w Klostermeyer & Mynhardt (2015b) .

Miedza

Niech G będzie grafem o n ≥ 1 wierzchołkach. Trywialnie, wieczna liczba dominacji jest co najmniej liczbą dominacji γ( G ). W swojej pracy Goddard, Hedetniemi i Hedetniemi udowodnili, że liczba wiecznej dominacji jest co najmniej liczbą niezależności G , a co najwyżej liczbą obejmującą klikę G (klika obejmująca liczbę G jest równa liczbie chromatycznej dopełnienia G ). Dlatego liczba wiecznej dominacji G jest równa liczbie obejmującej klikę G dla wszystkich doskonałych grafów, ze względu na twierdzenie o doskonałym grafie . Wykazano, że liczba wiecznej dominacji G jest równa liczbie obejmującej klikę G dla kilku innych klas grafów, takich jak grafy kołowo-łukowe (jak udowodniono w Regan (2007) ) i grafy szeregowo-równoległe (jak udowodniono w Anderson, Barrientos & Brigham (2007) ). Goddard, Hedetniemi i Hedetniemi również zademonstrowali graf, w którym liczba wiecznej dominacji na wykresie jest mniejsza niż liczba pokrywająca klikę.

Klostermeyer i MacGillivray (2007) udowodnili , że liczba wiecznej dominacji grafu o liczbie niezależności α jest najbardziej α ( α + 1)/2. Goldwasser i Klostermeyer (2008) udowodnili, że istnieje nieskończenie wiele grafów, w których liczba wiecznej dominacji wynosi dokładnie α ( α + 1)/2.

Granice na m -wieczna liczba dominacji

Goddard, Hedetniemi i Hedetniemi udowodnili, że m -liczba wiecznej dominacji, oznaczona jako γ ^m _∞ ( G ), jest co najwyżej liczbą niezależności G . Dlatego parametry wiecznej dominacji dobrze pasują do słynnego łańcucha parametrów dominacji, patrz ( Haynes, Hedetniemi i Slater 1998a ), jak następuje:

γ( G ) ≤ γ ^m _∞ ( G ) ≤ α ( G ) ≤ γ _∞ ( G ) ≤ θ ( G )

gdzie θ ( G ) oznacza liczbę obejmującą klikę G , a γ _∞ ( G ) oznacza liczbę wiecznej dominacji.

Górna granica ⌈ n /2⌉ na γ ^m _∞ ( G ) dla grafów z n wierzchołkami została udowodniona w Chambers, Kinnersly & Prince (2006) , patrz także Klostermeyer & Mynhardt (2015b ) .

Uwagę przyciągnęła m-eternal domination number in grid graphs, zainspirowana uwagą poświęconą liczbie dominacji w grid graphs, zob. Haynes , Hedetniemi i Slater (1998a) oraz Goncalves, Pinlou i Rao (2011) . M - wieczna liczba dominacji w grafach siatkowych została po raz pierwszy zbadana w Goldwasser, Klostermeyer & Mynhardt (2013), gdzie wykazano, że

γ ^m _∞ = ⌈2 n /3⌉ dla siatki 2 na n z n ≥ 2

I

γ ^m _∞ ≤ ⌈8 n /9⌉ dla 3 na n siatek.

Ten ostatni został ulepszony w Finbow, Messinger & van Bommel (2015) do

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

gdy n ≥ 11. Ta granica została następnie nieco poprawiona w Messinger i Delaney (2015) w niektórych przypadkach. Ostatecznie granice zostały zamknięte w pracy Finbow i van Bommel (2020) , gdzie wykazano, że

γm ^∞ = ⌈(4 n +7)/ _5⌉ dla n ≥ 22.

Przypadki dla siatek 4 by i siatek oraz 5 by n zostały rozważone w Beaton, Finbow & MacDonald (2013) oraz van Bommel & van Bommel (2015) , odpowiednio.

Braga, de Souza & Lee (2015) udowodnili, że γ ^m _∞ = α dla wszystkich właściwych grafów przedziałowych i ci sami autorzy udowodnili również, patrz Braga, de Souza & Lee (2016) , że istnieje graf Cayleya , dla którego m - liczba wiecznej dominacji nie jest równa liczbie dominacji, w przeciwieństwie do twierdzenia w Goddard, Hededtniemi & Hedetniemi (2005) .

Otwarte pytania

Według Klostermeyer & Mynhardt (2015b) jednym z głównych nierozwiązanych pytań jest: Czy istnieje graf G taki, że γ ( G ) jest równy liczbie wiecznej dominacji G , a γ ( G ) jest mniejszy niż liczba obejmująca klikę z G ? Klostermeyer i Mynhardt (2015a) udowodnili, że każdy taki graf musi zawierać trójkąty i musi mieć maksymalny stopień wierzchołków co najmniej cztery.

Podobnie jak w przypadku hipotezy Vizinga dla zbiorów dominujących, nie wiadomo, czy dla wszystkich grafów G i H

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

Wiadomo, że analogiczna granica nie zachodzi dla wszystkich grafów G i H dla problemu m -wiecznej dominacji, jak pokazano w Klostermeyer i Mynhardt (2015a) .

Douglas West wymienił dwa fundamentalne otwarte pytania dotyczące wiecznej dominacji w [1] . Mianowicie, czy γ _∞ ( G ) jest równe liczbie pokrywającej klikę dla wszystkich grafów planarnych G i czy γ _∞ ( G ) może być od dołu ograniczone liczbą Lovásza , znaną również jako funkcja teta Lovásza.

Klostermeyer & Mynhardt (2015b) podano szereg innych otwartych pytań , w tym wiele pytań dotyczących wspomnianych powyżej odmian wiecznie dominujących zbiorów.

• Anderson, M.; Barrientos, C.; Brigham, R.; Carrington, J.; Vitray, R.; Yellen, J. (2007), „Wykresy maksymalnego zapotrzebowania na wieczne bezpieczeństwo” , J. Combin. Matematyka Połącz. Oblicz. , 61 : 111–128 .
• Arquilla, H.; Frederickson, H. (1995), „Wykreślanie optymalnej wielkiej strategii”, Military Operations Research , 1 (3): 3–17, doi : 10.5711/morj.1.3.3 , hdl : 10945/38438 .
• Beaton, I.; Finow S.; MacDonald, J. (2013), „Wieczna dominacja ustawiła problem siatek”, J. Combin. Matematyka Połącz. Oblicz. , 85 : 33–38 .
• Braga, A.; de Souza, C.; Lee, O. (2015), „Wieczny dominujący problem zestawu dla odpowiednich wykresów interwałowych”, Information Processing Letters , 115 (6–8): 582–587, doi : 10.1016 / j.ipl.2015.02.004 .
• Braga, A.; de Souza, C.; Lee, O. (2016), „Notatka na temat artykułu „Wieczne bezpieczeństwo w grafach” autorstwa Goddarda, Hedetniemi i Hedetniemi (2005)”, Journal of Combinatorial Mathematics and Combinatorial Computing , 96 : 13–22 .
• Burger, AP; Cockayne, EJ; Grundlingh, WR; Mynhardt, CM; van Vuuren, J.; Winterbach, W. (2004), „Dominacja nieskończonego porządku na grafach”, J. Combin. Matematyka Połącz. Oblicz. , 50 : 179-194 .
• Komory, E.; Kinnersly, B.; Prince, N. (2006), „Mobilne wieczne bezpieczeństwo na wykresach” , niepublikowany rękopis , zarchiwizowane z oryginału w dniu 30.09.2015 , pobrane 21.02.2015 .
• Finbow, S.; Messinger, ja.; van Bommel, M. (2015), „Wieczna dominacja w sieciach 3 xn”, Australas. J. Kombajn. , 61 : 156–174 .
• Finbow, S.; van Bommel, MF (2020), „Wieczna liczba dominacji dla wykresów siatki 3 xn”, Australas. J. Kombajn. , 71 : 1–23 .
• Goldwasser, J.; Klostermeyer, W. (2008), „Wąskie granice dla wiecznych dominujących zbiorów w grafach”, Discrete Math. , 308 (12): 2589–2593, doi : 10.1016/j.disc.2007.06.005 .
• Goldwasser, J.; Klostermeyer, W.; Mynhardt, C. (2013), „Wieczna ochrona na wykresach siatkowych”, Utilitas Math. , 91 : 47–64 .
• Goncalves, D.; Pinlou, A.; Rao, M.; Thomasse, S. (2011), „Liczba dominacji siatek”, SIAM Journal on Discrete Mathematics , 25 (3): 1443–1453, arXiv : 1102,5206 , doi : 10,1137/11082574 .
•    Haynes, Teresa W .; Hedetniemi, Stefan; Slater, Peter (1998a), Podstawy dominacji w wykresach , Marcel Dekker, ISBN 0-8247-0033-3 , OCLC 37903553 .
• Klostermeyer, W.; MacGillivray, G. (2007), „Wieczne bezpieczeństwo na wykresach o ustalonej liczbie niezależności”, J. Combin. Matematyka Połącz. Oblicz. , 63 : 97–101 .
• Klostermeyer, W.; Mynhardt, C. (2015a), „Dominacja, wieczna dominacja i zakrywanie kliki”, Dyskutuj. Matematyka Teoria grafów , 35 (2): 283, arXiv : 1407,5235 , doi : 10,7151/dmgt.1799 .
• Klostermeyer, W.; Mynhardt, C. (2015b), „Protecting a graph with mobile guards”, Applicable Analysis and Discrete Mathematics , 10 : 21, arXiv : 1407,5228 , doi : 10,2298/aadm151109021k .
• Messinger, ja.; Delaney, A. (2015), Zamykanie luki: Wieczna dominacja w sieciach 3 xn .
• Regan, F. (2007), Dynamiczne warianty dominacji i niezależności w grafach , Rheinischen Friedrich-Wilhlems University .
• Revelle, C. (2007), „Czy możesz chronić Cesarstwo Rzymskie?”, Johns Hopkins Magazine , 2 .
•   Revelle, C.; Rosing, K. (2000), „Defendens Imperium Romanum: klasyczny problem strategii wojskowej”, Amer. Matematyka Miesięczny , 107 (7): 585–594, doi : 10.2307/2589113 , JSTOR 2589113 .
• Stewart, I. (1999), „Broń Cesarstwa Rzymskiego!”, Scientific American , 281 (6): 136–138, Bibcode : 1999SciAm.281f.136S , doi : 10.1038/scientificamerican1299-136 .
• van Bommel, C.; van Bommel, M. (2016), „Wieczna liczba dominacji 5 xn siatek”, J. Combin. Matematyka Połącz. Comput , 97 : 83–102 .