zbMATH — the first resource for mathematics

A method for eternally dominating strong grids. (English) Zbl 1450.05065
Summary: In the eternal domination game, 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 and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as \(2 \times n, 3 \times n, 4 \times n\), and \(5 \times n\) grids, and recently it was proven in [I. Lamprou et al., Theor. Comput. Sci. 794, 27–46 (2019; Zbl 1433.05225)] that the eternal domination number of these grids in general is within \(O(m + n)\) of their domination number which lower bounds the eternal domination number. S. Finbow et al. [Australas. J. Comb. 61, Part 2, 156–174 (2015; Zbl 1309.05134)] proved that the eternal domination number of strong grids is upper bounded by \(\frac{mn}{6} + O(m + n)\). We adapt the techniques of I. Lamprou et al. [loc. cit.] to prove that the eternal domination number of strong grids is upper bounded by \(\frac{mn}{7} + O(m + n)\). While this does not improve upon a recently announced bound of \(\lceil \frac{m}{3}\rceil \times \lceil \frac{n}{3}\rceil + O(m \sqrt{n})\) [F. Mc Inerney et al., “Eternal domination in grids”, in: 11th International Conference, CIAC 2019, Rome, Italy, May 27–29. 311–322 (2019)] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179.
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs
91A46 Combinatorial games
Full Text: DOI
[1] J. Arquilla and H. Fredricksen. “Graphing” an optimal grand strategy.Military Oper. Res., 1(3):3-17, 1995. [BCG+04]A. Burger, E. J. Cockayne, W. R. Gr¨undlingh, C. M. Mynhardt, J. H. van Vuuren, and W. Winterbach. Infinite order domination in graphs.J. Combin. Math. Combin. Comput., 50:179-194, 2004.
[2] I. Beaton, S. Finbow, and J.A. MacDonald. Eternal domination numbers of4×ngrid graphs.J. Combin. Math. Combin. Comput., 85:33-48, 2013. · Zbl 1274.05348
[3] A. Braga, C. Souza, and O. Lee. The eternal dominating set problem for proper interval graphs.Inform. Process. Lett., 115:582-587, 2015. · Zbl 1329.05224
[4] N. Cohen, F. Mc Inerney, N. Nisse, and S. P´erennes. Study of a combinatorial game in graphs through linear programming.Algorithmica, 82(2):212-244, Feb 2020. · Zbl 1437.91112
[5] A. Z. Delaney and M. E. Messinger. Closing the gap: Eternal domination on3×ngrids.Contrib. Discrete Math., 12(1):47-61, 2017. · Zbl 1376.05114
[6] S. Finbow, M. E. Messinger, and M. F. van Bommel. Eternal domination in3×ngrids.Australas. J. Combin., 61:156-174, 2015. · Zbl 1309.05134
[7] S. Finbow and M. van Bommel. The eternal domination number for 3×n grid graphs.Australas. J. Combin., 76(1):1- 23, 2020. · Zbl 1439.05177
[8] W. Goddard, S. M. Hedetniemi, and S. T. Hedetniemi. Eternal security in graphs.J. Combin. Math. Combin. Comput., 52, 2005. · Zbl 1067.05051
[9] J. L. Goldwasser, W. F. Klostermeyer, and C. M. Mynhardt. Eternal protection in grid graphs.Util. Math., 91:47-64, 2013. · Zbl 1300.05177
[10] D. Gonc¸alves, A. Pinlou, M. Rao, and S. Thomass´e. The domination number of grids.SIAM J. Discrete Math., 25(3):1443-1453, 2011.
[11] W. F. Klostermeyer and G. MacGillivray. Eternal dominating sets in graphs.J. Combin. Math. Combin. Comput., 68, 2009. · Zbl 1176.05057
[12] W. F. Klostermeyer and C. M. Mynhardt. Protecting a graph with mobile guards.Appl. Anal. Discrete Math., 10:1-29, 2016. · Zbl 06750189
[13] I. Lamprou, R. Martin, and S. Schewe. Eternally dominating large grids.Theoret. Comput. Sci., 794:27 - 46, 2019. · Zbl 1433.05225
[14] F. Mc Inerney, N. Nisse, and S. P´erennes. Eternal domination in grids. InAlgorithms and complexity, volume 11485 ofLecture Notes in Comput. Sci., pages 311-322. Springer, Cham, 2019. · Zbl 07163796
[15] C. S. Revelle. Can you protect the roman empire?Johns Hopkins Mag., 50(2), 1997.
[16] C. S. Revelle and K. E. Rosing.Defendens imperium romanum: A classical problem in military strategy. Amer. Math. Monthly, 107:585-594, 2000. · Zbl 1039.90038
[17] I. Stewart. Defend the roman empire!Scientific American, pages 136-138, 1999.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.