Eternal distance-\(k\) domination on graphs. (English) Zbl 1517.05131
Summary: Eternal domination is a dynamic process by which a graph is protected from an infinite sequence of vertex intrusions. In eternal distance-\(k\) domination, guards initially occupy the vertices of a distance-\(k\) dominating set. After a vertex is attacked, guards “defend” by each moving up to distance \(k\) to form a distance-\(k\) dominating set, such that some guard occupies the attacked vertex. The eternal distance-\(k\) domination number of a graph is the minimum number of guards needed to defend against any sequence of attacks. The process is well-studied for the situation where \(k=1\). We introduce eternal distance-\(k\) domination for \(k > 1\). Determining whether a given set is an eternal distance-\(k\) domination set is in EXP, and in this paper we provide a number of results for paths and cycles, and relate this parameter to graph powers and domination in general. For trees we use decomposition arguments to bound the eternal distance-\(k\) domination numbers, and solve the problem entirely in the case of perfect \(m\)-ary trees.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C12 | Distance in graphs |
| 05C05 | Trees |
References:
| [1] | Blažej, V.; Křišt’an, JM; Valla, T.; Filiot, E.; Jungers, R.; Potapov, I., On the m-eternal domination number of cactus graphs, Reachability Problems (2019), Cham: Springer, Cham · Zbl 1455.05052 · doi:10.1007/978-3-030-30806-3_4 |
| [2] | Cohen, N.; Martins, NA; Mc Inerney, F.; Nisse, N.; Pérennes, S.; Sampaio, R., Spy-game on graphs: complexity and simple topologies, Theor. Comput. Sci., 725, 1-15 (2018) · Zbl 1394.91051 · doi:10.1016/j.tcs.2017.11.015 |
| [3] | Finbow, S.; Gaspers, S.; Messinger, ME; Ottoway, P., A note on the eternal dominating set problem, Int. J. Game Theory, 47, 543-555 (2018) · Zbl 1416.91058 · doi:10.1007/s00182-018-0623-0 |
| [4] | Finbow, S.; Messinger, ME; van Bommel, MF, Eternal domination on \(3 \times n\) grids, Australas. J. Comb., 61, 2, 156-174 (2015) · Zbl 1309.05134 |
| [5] | Gagnon, A.; Hassler, A.; Huang, J.; Krim-Yee, A.; Mc Inerney, F.; Zacarias, A.; Seamone, B.; Virgile, V., A method for eternally dominating strong grids, Discrete Math. Theor. Comput. Sci., 22, 1, 1-11 (2020) · Zbl 1450.05065 |
| [6] | Henning, M.; Klostermeyer, WF; MacGillivray, G., Bounds for the \(m\)-eternal domination number of a graph, Contrib. Discrete Math., 12, 2, 91-103 (2017) · Zbl 1376.05112 |
| [7] | Klostermeyer, WF, Complexity of eternal security, J. Comb. Math. Comb. Comput., 61, 135-141 (2007) · Zbl 1133.05071 |
| [8] | Klostermeyer, W. F.: Errata. https://www.unf.edu/ wkloster/errata.html |
| [9] | Klostermeyer, WF; MacGillivray, G., Eternal dominating sets in graphs, J. Comb. Math. Comb. Comput., 68, 97-111 (2009) · Zbl 1176.05057 |
| [10] | Klostermeyer, WF; Mynhardt, CM, Protecting a graph with mobile guards, Appl. Anal. Discrete Math., 10, 1-29 (2016) · Zbl 1461.05157 · doi:10.2298/AADM151109021K |
| [11] | Lamprou, I.; Martin, R.; Schewe, S., Eternally dominating large grids, Theor. Comput. Sci., 794, 19, 27-46 (2019) · Zbl 1433.05225 · doi:10.1016/j.tcs.2018.09.008 |
| [12] | Sridharan, N.; Subramanian, VSA; Elias, ME, Bounds on the distance two-domination number of a graph, Graphs Comb., 18, 667-675 (2002) · Zbl 1009.05105 · doi:10.1007/s003730200050 |
| [13] | van Bommel, CM; van Bommel, MF, Eternal domination numbers of \(5 \times n\) grid graphs, J. Comb. Math. Comb. Comput., 97, 83-102 (2016) · Zbl 1405.05139 |
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.
