Skip to Main content Skip to Navigation
Journal articles

Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between

Fionn Mc Inerney 1, 2 Nicolas Nisse 1 Stéphane Pérennes 1 
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 ACRO - Algorithmique, Combinatoire et Recherche Opérationnelle
LIS - Laboratoire d'Informatique et Systèmes
Abstract : In the eternal domination game played on graphs, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices on their turn. The goal is to determine the eternal domination number $\gamma^{\infty}_{all}$ of a graph, which is the minimum number of guards required to defend against an infinite sequence of attacks. This paper first continues the study of the eternal domination game on strong grids $P_n\boxtimes P_m$. Cartesian grids $P_n \square P_m$ have been vastly studied with tight bounds existing for small grids such as $k\times n$ grids for $k\in \{2,3,4,5\}$. It was recently proven that $\gamma^{\infty}_{all}(P_n \square P_m)=\gamma(P_n \square P_m)+O(n+m)$ where $\gamma(P_n \square P_m)$ is the domination number of $P_n \square P_m$ which lower bounds the eternal domination number [Lamprou et al. Eternally dominating large grids. Theoretical Computer Science, 794:27-46, 2019]. We prove that, for all $n,m\in \mathbb{N^*}$ such that $m\geq n$, $\lfloor \frac{n}{3} \rfloor \lfloor \frac{m}{3} \rfloor+\Omega(n+m)=\gamma_{all}^{\infty} (P_{n}\boxtimes P_{m})=\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil + O(m\sqrt{n})$ (note that $\lceil \frac{n}{3} \rceil \lceil \frac{m}{3} \rceil$ is the domination number of $P_n\boxtimes P_m$). We then generalise our technique to prove that $\gamma_{all}^{\infty}(G)=\gamma(G)+o(\gamma(G))$ for all graphs $G\in \mathcal{F}$, where $\mathcal{F}$ is a large family of $D$-dimensional grids which are supergraphs of the $D$-dimensional Cartesian grid and subgraphs of the $D$-dimensional strong grid. In particular, $\mathcal{F}$ includes both the $D$-dimensional Cartesian grid and the $D$-dimensional strong grid.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-02801932
Contributor : Fionn Mc Inerney Connect in order to contact the contributor
Submitted on : Monday, February 21, 2022 - 9:48:44 PM
Last modification on : Thursday, August 4, 2022 - 4:58:28 PM

File

eter_dom_grids_journal.pdf
Files produced by the author(s)

Identifiers

Citation

Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes. Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between. Algorithmica, Springer Verlag, 2021, 83 (5), pp.1459-1492. ⟨10.1007/s00453-020-00790-8⟩. ⟨hal-02801932v3⟩

Share

Metrics

Record views

159

Files downloads

164