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 ,
The orthogonal colouring game, Theoretical Computer Science, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-02017462
Hyperopic cops and robbers, Theoretical Computer Science, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-01627391
, Spy-game on graphs: Complexity and simple topologies, vol.725, pp.1-15, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01463297
Study of a combinatorial game in graphs through linear programming, Algorithmica, 2019. ,
URL : https://hal.archives-ouvertes.fr/hal-01881473
Sequential metric dimension, Proceedings of the 16th Workshop on Approximation and Online Algorithms, WAOA 2018, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01717629
Metric dimension: From graphs to digraphs, Proceedings of the 10th Latin & American Algorithms, Graphs and Optimization Symposium, 2019. ,
The game of wall cops and robbers, Proceedings of the 2nd International Conference on Computational Intelligence, vol.3, 2015. ,
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
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.
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
Dimension métrique des graphes orientés, 21es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications AlgoTel, 2019. ,
Enquêter dans les graphes, 19es Rencontres Francophones sur les aspects Algorithmiques des Télécommunications AlgoTel, 2017. ,
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
On {a, b}-edge-weightings of bipartite graphs with odd a, b ,
URL : https://hal.archives-ouvertes.fr/hal-01988399
A method for eternally dominating strong grids ,
URL : https://hal.archives-ouvertes.fr/hal-02004770
A game of cops and robbers, Discrete Applied Mathematics, vol.8, pp.1-12, 1984. ,
Algorithmic construction of sets for k -restrictions, ACM Trans. Algorithms, vol.2, issue.2, pp.153-177, 2006. ,
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
Base size, metric dimension and other invariants of groups and graphs, Bulletin of the London Mathematical Society, vol.43, pp.209-242, 2011. ,
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. ,
Metric dimension of bounded tree-length graphs, SIAM J. Discrete Mathematics, vol.31, issue.2, pp.1217-1243, 2017. ,
Adaptive identification in graphs, J. Comb. Theory, Ser. A, vol.115, issue.7, pp.1114-1126, 2008. ,
On the cop number of a graph, Advances in Applied Mathematics, vol.14, pp.389-403, 1993. ,
On the complexity of some coloring games, Internat. J. Found. Comput. Sci, vol.2, pp.133-147, 1991. ,
Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, vol.21, pp.358-402, 1996. ,
, , 2018.
The game of Cops and Robbers on Graphs, 2011. ,
, Graph theory, vol.244, 2008.
, Electronic Journal of Combinatorics, 2017.
Localization game on geometric and planar graphs, Discrete Applied Mathematics, 2017. ,
URL : https://hal.archives-ouvertes.fr/hal-01620365
Nim, a game with a complete mathematical theory, Annals of Mathematics, vol.3, issue.14, pp.35-39, 1901. ,
The eternal dominating set problem for proper interval graphs, Information Processing Letters, vol.115, 2015. ,
A robber locating strategy for trees, Discrete Applied Mathematics, vol.232, pp.99-106, 2017. ,
Vizing's conjecture: A survey and recent results, Journal of Graph Theory, vol.69, issue.1, pp.46-76, 2012. ,
Complexity of the game domination problem, Theoretical Computer Science, vol.648, issue.4, pp.1-7, 2016. ,
Domination game and an imagination strategy, SIAM J. Discrete Mathematics, vol.24, pp.979-991, 2010. ,
Domination game played on trees and spanning subgraphs, Discrete Mathematics, vol.313, pp.915-923, 2013. ,
Infinite order domination in graphs, J. Comb. Math. Comb. Comput, vol.50, pp.179-194, 2004. ,
Locating a robber on a graph via distance queries, Theoretical Computer Science, vol.463, pp.54-61, 2012. ,
Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, vol.105, issue.1-3, pp.99-113, 2000. ,
The directed distance dimension of oriented graphs, Mathematica Bohemica, vol.125, pp.155-168, 2000. ,
On the dimension of oriented graphs, Utilitas Mathematica, vol.60, pp.139-151, 2001. ,
Domination number of the cross product of paths, Discrete Applied Mathematics, vol.94, issue.1-3, pp.101-139, 1999. ,
A better bound for the cop number of general graphs, Journal of Graph Theory, vol.58, issue.1, pp.45-48, 2008. ,
An inequality related to vizing's conjecture, Electronic Journal of Combinatorics, vol.7, issue.1, 2000. ,
Constrained Cops and Robber, Canada, 2002. ,
Closing the gap: Eternal domination on 3 × n grids, Contributions to Discrete Mathematics, vol.12, issue.1, pp.47-61, 2017. ,
Complexity of metric dimension on planar graphs, J. Comput. Syst. Sci, vol.83, issue.1, pp.132-158, 2017. ,
of Graduate texts in mathematics, Graph Theory, vol.173, 2012. ,
The domination game played on unions of graphs, Discrete Mathematics, vol.338, pp.71-79, 2015. ,
Fixed-parameter tractability and completeness, Theoretical Computer Science, vol.141, pp.109-131, 1995. ,
, Fundamentals of parameterized complexity, vol.4, 2013.
Applications and variations of domination in graphs, 2000. ,
The Canterbury puzzles, puzzle 73, 1908. ,
The metric dimension of cayley digraphs, Discrete Mathematics, vol.306, pp.31-41, 2006. ,
On the metric dimension of line graphs, Discrete Applied Mathematics, vol.161, pp.802-805, 2013. ,
Eternal domination in 3 × n grids, Australas. J. Combin, vol.61, pp.156-174, 2015. ,
To satisfy impatient web surfers is hard, Theoretical Computer Science, vol.526, pp.1-17, 2014. ,
URL : https://hal.archives-ouvertes.fr/inria-00625703
Pursuing a fast robber on a graph, Theoretical Computer Science, pp.1167-1181, 2010. ,
URL : https://hal.archives-ouvertes.fr/inria-00476686
Centroidal bases in graphs, Networks, vol.64, issue.2, pp.96-108, 2014. ,
URL : https://hal.archives-ouvertes.fr/hal-01428804
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
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
Cops and robbers in graphs with large girth and cayley graphs, Discrete Applied Mathematics, vol.17, pp.301-305, 1987. ,
Mathematical games -the fantastic combinations of john conway's new solitaire game "life, Scientific American, vol.223, pp.120-123, 1970. ,
Mathematical games: Cram, crosscram and quadraphage: new games having elusive winning strategies, Scientific American, vol.230, issue.2, pp.106-108, 1974. ,
Computers and Intractability -A guide to NP-completeness, 1979. ,
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1990. ,
Cops and robbers on intersection graphs, European Journal of Combinatorics, vol.72, pp.45-69, 2018. ,
Fractional combinatorial games, INRIA, vol.8371, 2013. ,
URL : https://hal.archives-ouvertes.fr/hal-00865345
Eternal security in graphs, J. Comb. Math. Comb. Comput, vol.52, pp.160-180, 2005. ,
Domination in planar graphs with small diameter, Journal of Graph Theory, vol.40, issue.1, pp.1-25, 2002. ,
Eternal protection in grid graphs, Utilitas Mathematica, vol.91, pp.47-64, 2013. ,
The domination number of grids, SIAM J. Discrete Mathematics, vol.25, issue.3, pp.1443-1453, 2011. ,
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
On the metric dimension of a graph, Ars Combinatoria, vol.2, pp.191-195, 1976. ,
On the parameterized and approximation hardness of metric dimension, Proceedings of the 28th Conference on Computational Complexity, CCC, pp.266-276, 2013. ,
Locating a robber with multiple probes, Discrete Mathematics, vol.341, issue.1, pp.184-193, 2018. ,
Fundamentals of Domination in Graphs, 1998. ,
A cover-based approach to multiagent moving target pursuit, 4th Conference on Artificial Intelligence and Interactive Digital Entertainment, 2008. ,
A linear algorithm for the domination number of a series-parallel graph, Discrete Applied Mathematics, vol.5, issue.3, pp.299-311, 1983. ,
Edge weights and vertex colours, J. Comb. Theory, Ser. B, vol.91, pp.151-157, 2004. ,
Reducibility among Combinatorial Problems, pp.85-103, 1972. ,
On a new class of codes for identifying vertices in graphs, IEEE Trans. Information Theory, vol.44, issue.2, pp.599-611, 1998. ,
Selfish cops and active robber: Multiplayer pursuit evasion on graphs, Theoretical Computer Science, 2019. ,
Cops and robbers is exptime-complete, J. Comb. Theory, Ser. B, vol.111, pp.201-220, 2015. ,
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 Combinatoria, vol.68, pp.473-492, 2012. ,
Protecting a graph with mobile guards, Applicable Analysis and Discrete Mathematics, vol.10, 2014. ,
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
, Memoryless determinacy of parity games. Automata, Logics, and Infinite Games: A Guide to Current Research, vol.2500, pp.95-106, 2002.
Perpetually dominating large grids, 10th Int. Conf. on Algorithms and Complexity (CIAC 2017), pp.393-404, 2017. ,
Guaranteed scoring games, Electronic Journal of Combinatorics, vol.23, 2016. ,
Game comparison through play, Theoretical Computer Science, vol.725, pp.52-63, 2018. ,
Games with guaranteed scores and waiting moves, Internat. J. Game Theory, vol.47, pp.653-671, 2018. ,
Symmetry breaking in tournaments, The Electronic Journal of Combinatorics, vol.20, issue.1, p.69, 2013. ,
On Meyniel's conjecture of the cop number, Journal of Graph Theory, vol.71, issue.2, pp.192-205, 2012. ,
Domination numbers of planar graphs, Journal of Graph Theory, vol.22, issue.3, pp.213-229, 1996. ,
On the computational complexity of a game of cops and robbers, Theoretical Computer Science, vol.477, pp.48-56, 2013. ,
Landmarks in torus networks, Journal of Discrete Mathematical Sciences and Cryptography, vol.9, issue.2, pp.263-271, 2013. ,
Stochastic games. Handbook of game theory with economic applications, vol.3, pp.1809-1832, 2002. ,
Vertex-to-vertex pursuit in a graph, Discrete Mathematics, vol.43, pp.235-239, 1983. ,
Directed metric dimension of oriented graphs with cyclic covering, J. Comb. Math. Comb. Comput, vol.94, pp.15-25, 2015. ,
Problèmes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, 1983. ,
Metric dimension of directed graphs, International Journal of Computer Mathematics, vol.91, issue.7, pp.1397-1406, 2014. ,
Can you protect the roman empire, Johns Hopkins Magazine, vol.50, issue.2, 1997. ,
Defendens imperium romanum: A classical problem in military strategy, American Mathematical Monthly, vol.107, pp.585-594, 2000. ,
The eternal dominating set problem for interval graphs, Information Processing Letters, vol.146, pp.27-29, 2019. ,
A theorem on graphs, with an application to a problem in traffic control, American Mathematical Monthly, vol.46, pp.281-283, 1939. ,
The copnumber of a graph is bounded by 3 2 genus(g) + 3. Categorical perspectives, Trends in Mathematics, pp.243-263, 1998. ,
A bound for the cops and robbers problem, SIAM J. Discrete Mathematics, vol.25, issue.3, pp.1438-1442, 2011. ,
Locating a robber on a graph, Discrete Mathematics, issue.22, pp.3265-3269, 2012. ,
A sequential locating game on graphs, Ars Combinatoria, vol.110, pp.45-54, 2013. ,
Locating a backtracking robber on a tree, Theoretical Computer Science, vol.539, pp.28-37, 2014. ,
Leaves of trees, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp.549-559, 1975. ,
Domination and location in acyclic graphs, Networks, vol.17, issue.1, pp.55-64, 1987. ,
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. ,
Exact algorithms for dominating set, Discrete Applied Mathematics, vol.159, issue.17, pp.2147-2164, 2011. ,
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
Some unsolved problems in graph theory. Uspehi Mat. Nauk, vol.23, pp.117-134, 1968. ,