Eternal Distance-k Domination on Graphs

被引：0
作者：
Cox D. [2 ]
Meger E. [1 ]
Messinger M.E. [3 ]
机构：
[1] Laboratoire d’algèbre, du combinatoire et d’informatique mathématique, Université du Québec à Montréal, Montréal
[2] Department of Mathematics and Statistics, Mount Saint Vincent University, Halifax
[3] Department of Mathematics and Computer Science, Mount Allison University, Sackville
来源：
La Matematica | 2023年 / 2卷 / 2期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Domination; Eternal domination; Graph theory; Trees;
D O I：
10.1007/s44007-023-00044-3
中图分类号：
学科分类号：
摘要：
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. © The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2023.
引用
收藏
页码：283 / 302
页数：19
相关论文
共 13 条
  • [1] Blazej V., Krist'an J.M., Valla T., On the m-eternal domination number of cactus graphs, Reachability Problems, (2019)
  • [2] Cohen N., Martins N.A., Mc Inerney F., Nisse N., Perennes S., Sampaio R., Spy-game on graphs: complexity and simple topologies, Theor. Comput. Sci, 725, pp. 1-15, (2018)
  • [3] Finbow S., Gaspers S., Messinger M.E., Ottoway P., A note on the eternal dominating set problem, Int. J. Game Theory, 47, pp. 543-555, (2018)
  • [4] Finbow S., Messinger M.E., van Bommel M.F., Eternal domination on 3×n grids, Australas. J. Comb, 61, 2, pp. 156-174, (2015)
  • [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, pp. 1-11, (2020)
  • [6] Henning M., Klostermeyer W.F., MacGillivray G., Bounds for the m-eternal domination number of a graph, Contrib. Discrete Math, 12, 2, pp. 91-103, (2017)
  • [7] Klostermeyer W.F., Complexity of eternal security, J. Comb. Math. Comb. Comput, 61, pp. 135-141, (2007)
  • [8] Klostermeyer W.F., Errata
  • [9] Klostermeyer W.F., MacGillivray G., Eternal dominating sets in graphs, J. Comb. Math. Comb. Comput, 68, pp. 97-111, (2009)
  • [10] Klostermeyer W.F., Mynhardt C.M., Protecting a graph with mobile guards, Appl. Anal. Discrete Math, 10, pp. 1-29, (2016)
12