, By the previous section (combining moves along |W | coordinates simultaneously), this leads to a new dominating set of V (G) and so, by induction on the number of attacks, the strategy will protect against any infinite sequence of attacks. It is easy to see this is possible in the case where no guards need to move onto a face of a block when moving according to the coordinates W j . To see that it works in the case where guards may also need to move onto a face of a block, it suffices to recall that, for all 1 ? i ? D, each vertex of a ±i-face of an i-block is occupied by g i = S i + g i?1 S i?1 guards, The strategy starts as the one from Theorem 14 for the D-dimensional Cartesian grid G from which G is built. Let us assume that an unoccupied vertex u is attacked and let v ? N (u) be its occupied neighbour
-faces of each -block allow for Lemma 15 to be applied to guards moving in any ( ? 1)-block at the same time as it is being applied to guards moving in an -block, for all at the same time, the additional g ?1 S ?1 guards on each vertex of the ±( ,
, ?1), (?1, 1), (1, 1)} (roughly, it represents all adjacencies in the strong grid, not in the Cartesian grid). Then, A = ((?1, 1), (1, 1)) (for any two "symmetrical" adjacencies, only one is kept). Finally, the sequence defining G 1 is M 1 = (1, 0) (meaning that only the first adjacency in A will be taken into account to define G 1 ), Two examples of graphs in the class F. The edges of the underlying Cartesian grids are in bold. The graph G 1 on the left is defined as follows: D = 2 and A * = {(?1, ?1), vol.15
graphing" an optimal grand strategy, Military Operations Research, vol.1, issue.3, pp.3-17, 1995. ,
Eternal dominating sets on digraphs and orientations of graphs, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-02168424
Eternal domination in split graphs, J. Comb. Math. Comb. Comput, vol.101, pp.121-130, 2017. ,
Eternal domination numbers of 4 × n grid graphs, J. Comb. Math. Comb. Comput, vol.85, pp.33-48, 2013. ,
The eternal dominating set problem for proper interval graphs, Information Processing Letters, vol.115, 2015. ,
Infinite order domination in graphs, J. Comb. Math. Comb. Comput, vol.50, pp.179-194, 2004. ,
Study of a combinatorial game in graphs through linear programming, Algorithmica, vol.82, issue.2, pp.212-244, 2020. ,
URL : https://hal.archives-ouvertes.fr/hal-01462890
, Spy-game on graphs: Complexity and simple topologies, vol.725, pp.1-15, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01463297
, Graph Theory, vol.173, 2012.
Eternal domination in 3 × n grids, Australas. J. Combin, vol.61, pp.156-174, 2015. ,
A method for eternally dominating strong grids, Discrete Mathematics and Theoretical Computer Science, vol.22, issue.1, 2020. ,
URL : https://hal.archives-ouvertes.fr/hal-02004770
Eternal security in graphs, J. Comb. Math. Comb. Comput, vol.52, pp.160-180, 2005. ,
Eternal protection in grid graphs, Util. Math, vol.91, pp.47-64, 2013. ,
The domination number of grids, SIAM J. Discrete Math, vol.25, issue.3, pp.1443-1453, 2011. ,
Eternal domination in grids, Proceedings of the 11th International Conference on Algorithms and Complexity, CIAC 2019, vol.11485, pp.311-322, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02098169
Dynamic dominating sets: the eviction model for eternal domination, 2014. ,
Eternal dominating sets in graphs, J. Comb. Math. Comb. Comput, vol.68, pp.97-111, 2009. ,
Eternal total domination in graphs, Ars Combin, vol.68, pp.473-492, 2012. ,
Protecting a graph with mobile guards, Applicable Analysis and Discrete Mathematics, vol.10, 2014. ,
Eternally dominating large grids, Theoretical Computer Science, vol.794, pp.27-46, 2019. ,
Closing the gap: Eternal domination on 3 × n grids, Contributions to Discrete Mathematics, vol.12, issue.1, pp.47-61, 2017. ,
Can you protect the roman empire?, Johns Hopkins Magazine, vol.50, issue.2, 1997. ,
Defendens imperium romanum: A classical problem in military strategy, Amer. Math. Monthly, vol.107, pp.585-594, 2000. ,
The eternal dominating set problem for interval graphs, Information Processing Letters, vol.146, pp.27-29, 2019. ,
Defend the roman empire! Scientific American, pp.136-138, 1999. ,
Eternal domination numbers of 5 × n grid graphs, J. Comb. Math. Comb. Comput, vol.97, pp.83-102, 2016. ,