I den eviga dominansen upptar en grupp vaktpolletter initialt en dominerande uppsättning på en graf G. En upploppsmakare väljer sedan en nod utan en vakt på den och attackerar den. Vakterna försvarar sig mot attacken: en av dem måste flytta till den attackerade noden, medan var och en av de återstående kan välja att flytta till en av sina angränsande noder. De nya vakternas placering måste återigen dominera. Det här anfallsförsvaret fortsätter hela tiden. Vakterna vinner om de för evigt kan upprätthålla en dominerande uppsättning mot varje sekvens av attacker, annars vinner upploppsmakaren. Vi studerar rektangulära rutnät och ger den första kända allmänna övre gräns för dessa grafer. Vår nya strategi implementerar en fyrkantig rotation princip och evigt dominerar m×n rutnät genom att använda ungefär mn 5 vakter, vilket är asymptotiskt optimalt även för vanlig dominans.
Den mest kända allmänna övre gränsen i rutnät är nm 5 + O(n + m) REF.
Perpetually Dominating Large Grids
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}