×

A note on the eternal dominating set problem. (English) Zbl 1416.91058

Summary: We consider the “all guards move” model for the eternal dominating set problem. A set of guards form a dominating set on a graph and at the beginning of each round, a vertex not in the dominating set is attacked. To defend against the attack, the guards move (each guard either passes or moves to a neighboring vertex) to form a dominating set that includes the attacked vertex. The minimum number of guards required to defend against any sequence of attacks is the “eternal domination number” of the graph. In 2005, it was conjectured [W. Goddard et al., J. Comb. Math. Comb. Comput. 52, 169–180 (2005; Zbl 1067.05051)] there would be no advantage to allow multiple guards to occupy the same vertex during a round. We show this is, in fact, false. We also describe algorithms to determine the eternal domination number for both models for eternal domination and examine the related combinatorial game, which makes use of the reduced canonical form of games.

MSC:

91A46 Combinatorial games
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C57 Games on graphs (graph-theoretic aspects)
91A43 Games involving graphs

Citations:

Zbl 1067.05051
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albert MH, Nowakowski RJ, Wolfe D (2007) Lessons in play. A K Peters Ltd, Massachusetts
[2] Arquilla, J; Fredricksen, H, “graphing” an optimal grand strategy, Mil Oper Res, 1, 3-17, (1995) · doi:10.5711/morj.1.3.3
[3] Beaton, I; Finbow, S; MacDonald, JA, Eternal domination numbers of \(4 × n\) grid graphs, J Combin Math Combin Comput, 85, 33-48, (2013) · Zbl 1274.05348
[4] Berlekamp ER, Conway JH, Guy RK (2001) Winning ways for your mathematical plays, vol 1, 2nd edn. A K Peters Ltd, Massachusetts · Zbl 1005.00004
[5] Burger, AP; Cockayne, EJ; Gründlingh, WR; Mynhardt, CM; Vuuren, JH; Winterbach, W, Infinite order domination in graphs, J Combin Math Combin Comput, 50, 179-194, (2004) · Zbl 1052.05054
[6] Finbow, S; Messinger, ME; Bommel, M, Eternal domination of \(3 × n\) grid graphs, Aust J Combin, 61, 156-174, (2015) · Zbl 1309.05134
[7] Fomin FV, Kratsch D (2010) Exact exponential algorithms, texts in theoretical computer science. Springer, Berlin · Zbl 1370.68002 · doi:10.1007/978-3-642-16533-7
[8] Fricke, GH; Hedetniemi, SM; Hedetniemi, ST, \(γ \)-graphs of graphs, Disc Math Graph Theory, 31, 517-531, (2011) · Zbl 1229.05219 · doi:10.7151/dmgt.1562
[9] Goddard, W; Hedetniemi, SM; Hedetniemi, ST, Eternal security in graphs, J Combin Math Combin Comput, 52, 169-180, (2005) · Zbl 1067.05051
[10] Grossman, JP; Siegel, A; Albert, MH (ed.); Nowakowski, RJ (ed.), Reductions of partizan games, 427-445, (2009), New York · Zbl 1192.91055 · doi:10.1017/CBO9780511807251.022
[11] Klostermeyer, WF; MacGillivray, G, Eternal dominating sets in graphs, J Combin Math Combin Comput, 68, 97-111, (2009) · Zbl 1176.05057
[12] Klostermeyer, WF; Mynhardt, CM, Protecting a graph with mobile guards, Appl Anal Disc Math, 10, 1-29, (2016) · Zbl 1461.05157 · doi:10.2298/AADM151109021K
[13] McCuaig, W; Shepherd, B, Domination in graphs with minimum degree two, J Gr Theory, 13, 749-762, (1989) · Zbl 0708.05058 · doi:10.1002/jgt.3190130610
[14] ReVelle, CS, Can you protect the Roman empire?, John Hopkins Mag, 50, 40, (1997)
[15] ReVelle, CS; Rosing, KE, Defendens imperium romanum: a classical problem in military strategy, Am Math Mon, 107, 585-594, (2000) · Zbl 1039.90038 · doi:10.1080/00029890.2000.12005243
[16] Siegel AN (2013) Combinatorial game theory. American Mathematical Society, Providence · Zbl 1288.91003 · doi:10.1090/gsm/146
[17] Stewart, I, Defend the Roman empire!, Sci Am, 281, 136-138, (1999) · doi:10.1038/scientificamerican1299-136
[18] Woeginger GJ (2001) Exact algorithms for NP-hard problems: a survey. In: Proc. of the 5th international workshop on combinatorial optimization, Springer LNCS 2570, Berlin, pp 185-208 · Zbl 1024.68529
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.