=. ?. , Let u ? R v with w as their LCV and such that dist(w, u) = dist(w, v) is maximum. Let C be the column of w, u, and v. As mentioned in the proof of Claim 6.4.12, there must be a directed (shortest and included in C) path from w to u and a directed (shortest and included in C) path from w to v. Moreover, Claim 6.4.12 implies that all the vertices of these paths (but w) have out-degree 3 (since all shortest paths from R to u and v go through w). In particular, u and v have out-degree 3 (unless they are in the first or last row), particular, the modifications done by the algorithm (relative to each w ? Q) are independent of each other. Proof of the claim

S. D. Andres, M. Huggan, F. Mc-inerney, and R. J. Nowakowski, The orthogonal colouring game, Theoretical Computer Science, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02017462

A. Bonato, N. Clarke, D. Cox, S. Finbow, F. Mc-inerney et al., Hyperopic cops and robbers, Theoretical Computer Science, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01627391

N. Cohen, N. A. Martins, F. Mc-inerney, N. Nisse, S. Pérennes et al., Spy-game on graphs: Complexity and simple topologies, vol.725, pp.1-15, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01463297

N. Cohen, F. Mc-inerney, N. Nisse, and S. Pérennes, Study of a combinatorial game in graphs through linear programming, Algorithmica, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01881473

J. Bensmail, D. Mazauric, F. Mc-inerney, N. Nisse, and S. Pérennes, Sequential metric dimension, Proceedings of the 16th Workshop on Approximation and Online Algorithms, WAOA 2018, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01717629

J. Bensmail, F. Mc-inerney, and N. Nisse, Metric dimension: From graphs to digraphs, Proceedings of the 10th Latin & American Algorithms, Graphs and Optimization Symposium, 2019.

A. Bonato and F. Mc-inerney, The game of wall cops and robbers, Proceedings of the 2nd International Conference on Computational Intelligence, vol.3, 2015.

N. Cohen, F. Mc-inerney, N. Nisse, and S. Pérennes, Study of a combinatorial game in graphs through linear programming, Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), vol.22, pp.1-22, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01881473

F. Mc-inerney, N. Nisse, and S. Pérennes, Eternal domination in grids
URL : https://hal.archives-ouvertes.fr/hal-02098169

, Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC 2019), pp.311-322, 2019.

J. Bensmail, D. Mazauric, F. Mc-inerney, N. Nisse, and S. Pérennes, Localiser une cible dans un graphe, 20es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications AlgoTel, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01774827

J. Bensmail, F. Mc-inerney, and N. Nisse, Dimension métrique des graphes orientés, 21es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications AlgoTel, 2019.

N. Cohen, N. Martins, F. Mc-inerney, N. Nisse, S. Pérennes et al., Enquêter dans les graphes, 19es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications AlgoTel, 2017.

S. D. Andres, F. Dross, M. Huggan, F. Mc-inerney, and R. J. Nowakowski, On the complexity of orthogonal colouring games and the np-completeness of recognising graphs admitting a strictly matched involution, Discrete Applied Mathematics. RR
URL : https://hal.archives-ouvertes.fr/hal-02053265

J. Bensmail, F. Mc-inerney, and K. Szabo-lyngsie, On {a, b}-edge-weightings of bipartite graphs with odd a, b
URL : https://hal.archives-ouvertes.fr/hal-01988399

A. Gagnon, A. Hassler, J. Huang, A. Krim-yee, F. Mc-inerney et al., A method for eternally dominating strong grids
URL : https://hal.archives-ouvertes.fr/hal-02004770

M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Mathematics, vol.8, pp.1-12, 1984.

N. Alon, D. Moshkovitz, and S. Safra, Algorithmic construction of sets for k -restrictions, ACM Trans. Algorithms, vol.2, issue.2, pp.153-177, 2006.

J. Arquilla and H. Fredricksen, graphing" an optimal grand strategy, Military Operations Research, vol.1, issue.3, pp.3-17, 1995.

G. Bagan, A. Joffard, and H. Kheddouci, Eternal dominating sets on digraphs and orientations of graphs, 2018.
URL : https://hal.archives-ouvertes.fr/hal-02168424

R. F. Bailey and P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society, vol.43, pp.209-242, 2011.

S. Bard, C. Duffy, M. Edwards, G. Macgillivray, and F. Yang, Eternal domination in split graphs, J. Comb. Math. Comb. Comput, vol.101, pp.121-130, 2017.

I. Beaton, S. Finbow, and J. A. Macdonald, Eternal domination numbers of 4 × n grid graphs, J. Comb. Math. Comb. Comput, vol.85, pp.33-48, 2013.

R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanujan, Metric dimension of bounded tree-length graphs, SIAM J. Discrete Mathematics, vol.31, issue.2, pp.1217-1243, 2017.

Y. Ben-haim, S. Gravier, A. Lobstein, and J. Moncel, Adaptive identification in graphs, J. Comb. Theory, Ser. A, vol.115, issue.7, pp.1114-1126, 2008.

A. Berarducci and B. Intrigila, On the cop number of a graph, Advances in Applied Mathematics, vol.14, pp.389-403, 1993.

H. L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comput. Sci, vol.2, pp.133-147, 1991.

H. L. Bodlaender and T. Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, vol.21, pp.358-402, 1996.

A. Bonato and W. B. Kinnersley, , 2018.

A. Bonato and R. Nowakowski, The game of Cops and Robbers on Graphs, 2011.

J. A. Bondy and U. S. Murty, Graph theory, vol.244, 2008.

B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sokól et al., Electronic Journal of Combinatorics, 2017.

B. Bosek, P. Gordinowicz, J. Grytczuk, N. Nisse, J. Sokól et al., Localization game on geometric and planar graphs, Discrete Applied Mathematics, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01620365

C. L. Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics, vol.3, issue.14, pp.35-39, 1901.

A. Braga, C. Souza, and O. Lee, The eternal dominating set problem for proper interval graphs, Information Processing Letters, vol.115, 2015.

A. Brandt, J. Diemunsch, C. Erbes, J. Legrand, and C. Moffatt, A robber locating strategy for trees, Discrete Applied Mathematics, vol.232, pp.99-106, 2017.

B. Bre?ar, P. Dorbec, W. Goddard, and B. L. Hartnell, Vizing's conjecture: A survey and recent results, Journal of Graph Theory, vol.69, issue.1, pp.46-76, 2012.

B. Bre?ar, P. Dorbec, S. Klav?ar, G. Ko?mrlj, and G. Renault, Complexity of the game domination problem, Theoretical Computer Science, vol.648, issue.4, pp.1-7, 2016.

B. Bre?ar, S. Klav?ar, and D. F. , Domination game and an imagination strategy, SIAM J. Discrete Mathematics, vol.24, pp.979-991, 2010.

B. Bre?ar, S. Klav?ar, and D. F. , Domination game played on trees and spanning subgraphs, Discrete Mathematics, vol.313, pp.915-923, 2013.

A. Burger, E. J. Cockayne, W. R. Gründlingh, C. M. Mynhardt, J. H. Van-vuuren et al., Infinite order domination in graphs, J. Comb. Math. Comb. Comput, vol.50, pp.179-194, 2004.

J. M. Carraher, I. Choi, M. Delcourt, L. H. Erickson, and D. B. West, Locating a robber on a graph via distance queries, Theoretical Computer Science, vol.463, pp.54-61, 2012.

G. Chartrand, L. Eroh, M. Johnson, and O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, vol.105, issue.1-3, pp.99-113, 2000.

G. Chartrand, M. Rains, and P. Zhang, The directed distance dimension of oriented graphs, Mathematica Bohemica, vol.125, pp.155-168, 2000.

G. Chartrand, M. Rains, and P. Zhang, On the dimension of oriented graphs, Utilitas Mathematica, vol.60, pp.139-151, 2001.

R. Chérifi, S. Gravier, X. Lagraula, C. Payan, and I. Zighem, Domination number of the cross product of paths, Discrete Applied Mathematics, vol.94, issue.1-3, pp.101-139, 1999.

E. Chiniforooshan, A better bound for the cop number of general graphs, Journal of Graph Theory, vol.58, issue.1, pp.45-48, 2008.

W. E. Clark and S. Suen, An inequality related to vizing's conjecture, Electronic Journal of Combinatorics, vol.7, issue.1, 2000.

N. E. Clarke, Constrained Cops and Robber, Canada, 2002.

A. Z. Delaney and M. E. Messinger, Closing the gap: Eternal domination on 3 × n grids, Contributions to Discrete Mathematics, vol.12, issue.1, pp.47-61, 2017.

J. Díaz, O. Pottonen, M. J. Serna, and E. J. Van-leeuwen, Complexity of metric dimension on planar graphs, J. Comput. Syst. Sci, vol.83, issue.1, pp.132-158, 2017.

R. Diestel, of Graduate texts in mathematics, Graph Theory, vol.173, 2012.

P. Dorbec, G. Ko?mrlj, and G. Renault, The domination game played on unions of graphs, Discrete Mathematics, vol.338, pp.71-79, 2015.

R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness, Theoretical Computer Science, vol.141, pp.109-131, 1995.

R. G. Downey and M. R. Fellows, Fundamentals of parameterized complexity, vol.4, 2013.

P. A. Dreyer, Applications and variations of domination in graphs, 2000.

H. E. Dudeney, The Canterbury puzzles, puzzle 73, 1908.

M. Fehr, S. Gosselin, and O. R. Oellermann, The metric dimension of cayley digraphs, Discrete Mathematics, vol.306, pp.31-41, 2006.

M. Feng, M. Xu, and K. Wang, On the metric dimension of line graphs, Discrete Applied Mathematics, vol.161, pp.802-805, 2013.

S. Finbow, M. E. Messinger, and M. F. Van-bommel, Eternal domination in 3 × n grids, Australas. J. Combin, vol.61, pp.156-174, 2015.

F. V. Fomin, F. Giroire, A. Jean-marie, D. Mazauric, and N. Nisse, To satisfy impatient web surfers is hard, Theoretical Computer Science, vol.526, pp.1-17, 2014.
URL : https://hal.archives-ouvertes.fr/inria-00625703

F. V. Fomin, P. A. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan, Pursuing a fast robber on a graph, Theoretical Computer Science, pp.1167-1181, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00476686

F. Foucaud, R. Klasing, and P. J. Slater, Centroidal bases in graphs, Networks, vol.64, issue.2, pp.96-108, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01428804

F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs. i. bounds, Theoretical Computer Science, vol.668, pp.43-58, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01198784

F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau, and P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs, II. algorithms and complexity. Algorithmica, vol.78, issue.3, pp.914-944, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01198784

P. Frankl, Cops and robbers in graphs with large girth and cayley graphs, Discrete Applied Mathematics, vol.17, pp.301-305, 1987.

M. Gardner, Mathematical games -the fantastic combinations of john conway's new solitaire game "life, Scientific American, vol.223, pp.120-123, 1970.

M. Gardner, Mathematical games: Cram, crosscram and quadraphage: new games having elusive winning strategies, Scientific American, vol.230, issue.2, pp.106-108, 1974.

M. R. Garey and D. S. Johnson, Computers and Intractability -A guide to NP-completeness, 1979.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1990.

T. Gavenciak, P. Gordinowicz, V. Jelínek, P. Klavík, and J. Kratochvíl, Cops and robbers on intersection graphs, European Journal of Combinatorics, vol.72, pp.45-69, 2018.

F. Giroire, N. Nisse, S. Pérennes, and R. P. Soares, Fractional combinatorial games, INRIA, vol.8371, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00865345

W. Goddard, S. M. Hedetniemi, and S. T. Hedetniemi, Eternal security in graphs, J. Comb. Math. Comb. Comput, vol.52, pp.160-180, 2005.

W. Goddard and M. A. Henning, Domination in planar graphs with small diameter, Journal of Graph Theory, vol.40, issue.1, pp.1-25, 2002.

J. L. Goldwasser, W. F. Klostermeyer, and C. M. Mynhardt, Eternal protection in grid graphs, Utilitas Mathematica, vol.91, pp.47-64, 2013.

D. Gonçalves, A. Pinlou, M. Rao, and S. Thomassé, The domination number of grids, SIAM J. Discrete Mathematics, vol.25, issue.3, pp.1443-1453, 2011.

S. Gravier and A. Khelladi, On the domination number of cross products of graphs, Discrete Mathematics, vol.145, issue.1-3, pp.273-277, 1995.
URL : https://hal.archives-ouvertes.fr/hal-00290404

F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, vol.2, pp.191-195, 1976.

S. Hartung and A. Nichterlein, On the parameterized and approximation hardness of metric dimension, Proceedings of the 28th Conference on Computational Complexity, CCC, pp.266-276, 2013.

J. Haslegrave, R. A. Johnson, and S. Koch, Locating a robber with multiple probes, Discrete Mathematics, vol.341, issue.1, pp.184-193, 2018.

T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs, 1998.

A. Isaza, J. Lu, V. Bulitko, and R. Greiner, A cover-based approach to multiagent moving target pursuit, 4th Conference on Artificial Intelligence and Interactive Digital Entertainment, 2008.

Y. Kakuda, T. Kikuno, and N. Yoshida, A linear algorithm for the domination number of a series-parallel graph, Discrete Applied Mathematics, vol.5, issue.3, pp.299-311, 1983.

M. Karo?ski, T. Luczak, and A. Thomason, Edge weights and vertex colours, J. Comb. Theory, Ser. B, vol.91, pp.151-157, 2004.

R. M. Karp, Reducibility among Combinatorial Problems, pp.85-103, 1972.

M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Information Theory, vol.44, issue.2, pp.599-611, 1998.

A. Kehagias and G. Konstantinidis, Selfish cops and active robber: Multiplayer pursuit evasion on graphs, Theoretical Computer Science, 2019.

W. B. Kinnersley, Cops and robbers is exptime-complete, J. Comb. Theory, Ser. B, vol.111, pp.201-220, 2015.

W. F. Klostermeyer, M. Lawrence, and G. Macgillivray, Dynamic dominating sets: the eviction model for eternal domination, 2014.

W. F. Klostermeyer and G. Macgillivray, Eternal dominating sets in graphs, J. Comb. Math. Comb. Comput, vol.68, pp.97-111, 2009.

W. F. Klostermeyer and C. M. Mynhardt, Eternal total domination in graphs, Ars Combinatoria, vol.68, pp.473-492, 2012.

W. F. Klostermeyer and C. M. Mynhardt, Protecting a graph with mobile guards, Applicable Analysis and Discrete Mathematics, vol.10, 2014.

A. Kosowski, B. Li, N. Nisse, and K. Suchan, k-chordal graphs: From cops and robber to compact routing via treewidth, Algorithmica, vol.72, issue.3, pp.758-777, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00687120

R. Kusters, Memoryless determinacy of parity games. Automata, Logics, and Infinite Games: A Guide to Current Research, vol.2500, pp.95-106, 2002.

I. Lamprou, R. Martin, and S. Schewe, Perpetually dominating large grids, 10th Int. Conf. on Algorithms and Complexity (CIAC 2017), pp.393-404, 2017.

U. Larsson, R. J. Nowakowski, J. P. Neto, and C. P. Santos, Guaranteed scoring games, Electronic Journal of Combinatorics, vol.23, 2016.

U. Larsson, R. J. Nowakowski, and C. P. Santos, Game comparison through play, Theoretical Computer Science, vol.725, pp.52-63, 2018.

U. Larsson, R. J. Nowakowski, and C. P. Santos, Games with guaranteed scores and waiting moves, Internat. J. Game Theory, vol.47, pp.653-671, 2018.

A. Lozano, Symmetry breaking in tournaments, The Electronic Journal of Combinatorics, vol.20, issue.1, p.69, 2013.

L. Lu and X. Peng, On Meyniel's conjecture of the cop number, Journal of Graph Theory, vol.71, issue.2, pp.192-205, 2012.

G. Macgillivray and K. Seyffarth, Domination numbers of planar graphs, Journal of Graph Theory, vol.22, issue.3, pp.213-229, 1996.

M. Mamino, On the computational complexity of a game of cops and robbers, Theoretical Computer Science, vol.477, pp.48-56, 2013.

P. Manuel, B. Rajan, I. Rajasingh, and M. C. Monica, Landmarks in torus networks, Journal of Discrete Mathematical Sciences and Cryptography, vol.9, issue.2, pp.263-271, 2013.

J. F. Mertens, Stochastic games. Handbook of game theory with economic applications, vol.3, pp.1809-1832, 2002.

R. J. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics, vol.43, pp.235-239, 1983.

S. Pancahayani and R. Simanjuntak, Directed metric dimension of oriented graphs with cyclic covering, J. Comb. Math. Comb. Comput, vol.94, pp.15-25, 2015.

A. Quilliot, Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, 1983.

B. Rajan, I. Rajasingh, J. A. Cynthia, and P. Manuel, Metric dimension of directed graphs, International Journal of Computer Mathematics, vol.91, issue.7, pp.1397-1406, 2014.

C. S. Revelle, Can you protect the roman empire, Johns Hopkins Magazine, vol.50, issue.2, 1997.

C. S. Revelle and K. E. Rosing, Defendens imperium romanum: A classical problem in military strategy, American Mathematical Monthly, vol.107, pp.585-594, 2000.

M. Rinemberg and F. J. Soulignac, The eternal dominating set problem for interval graphs, Information Processing Letters, vol.146, pp.27-29, 2019.

H. E. Robbins, A theorem on graphs, with an application to a problem in traffic control, American Mathematical Monthly, vol.46, pp.281-283, 1939.

B. S. Schröder, The copnumber of a graph is bounded by 3 2 genus(g) + 3. Categorical perspectives, Trends in Mathematics, pp.243-263, 1998.

A. Scott and B. Sudakov, A bound for the cops and robbers problem, SIAM J. Discrete Mathematics, vol.25, issue.3, pp.1438-1442, 2011.

S. M. Seager, Locating a robber on a graph, Discrete Mathematics, issue.22, pp.3265-3269, 2012.

S. M. Seager, A sequential locating game on graphs, Ars Combinatoria, vol.110, pp.45-54, 2013.

S. M. Seager, Locating a backtracking robber on a tree, Theoretical Computer Science, vol.539, pp.28-37, 2014.

P. J. Slater, Leaves of trees, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp.549-559, 1975.

J. Peter and . Slater, Domination and location in acyclic graphs, Networks, vol.17, issue.1, pp.55-64, 1987.

I. Stewart, Defend the roman empire! Scientific American, pp.136-138, 1999.

C. M. Van-bommel and M. F. Van-bommel, Eternal domination numbers of 5 × n grid graphs, J. Comb. Math. Comb. Comput, vol.97, pp.83-102, 2016.

J. M. Van-rooij and H. L. Bodlaender, Exact algorithms for dominating set, Discrete Applied Mathematics, vol.159, issue.17, pp.2147-2164, 2011.

N. Vieille, Stochastic games: Recent results. Handbook of game theory with economic applications, vol.3, pp.1833-1850, 2002.
URL : https://hal.archives-ouvertes.fr/hal-00596229

V. G. Vizing, Some unsolved problems in graph theory. Uspehi Mat. Nauk, vol.23, pp.117-134, 1968.