No label defined (Q4826280)

The authors are concerned with ``the construction of protection strategies in a simple graph \(G=(V,E)\) by utilizing the minimum number of guards needed at vertices in \(V\) to protect \(G\) in different scenarios.'' A {guard function} \(f\) maps each vertex \(v\) onto the (non-negative integer) number of {guards} stationed at \(v\); \(f^{-1}(i)\) is denoted by \(V_i\) \((i=0,1,\dots)\); the authors write \(f=(V_0,V_1,\dots,V_k)\) if \(f(v)\leq k\) for all \(v\in V\). The weight of \(f\) is \(\sum_{v\in V}f(v)\); \(f\) is {safe} if \(V\backslash V_0\) is a dominating set of \(G\). A {weak Roman dominating function} [\textit{M. A. Henning} and \textit{S. T. Hedetniemi}, Discrete Math. 266, No. 1--3, 239--251 (2003; Zbl 1024.05068)] is a safe guard function \(f=(V_0,V_1,V_2)\) such that each \(v\in V_0\) is adjacent to some \(u\in V_1\cup V_2\) for which the function obtained from \(f\) by moving 1 guard from \(u\) to an adjacent vertex \(v\), and leaving all other values unchanged is also safe; it is denoted by \(\text{move}(f,u\to v)\). A secure dominating function [\textit{E. J. Cockayne, P. J. Grobler, W. R. Gründlingh, J. Munganga} and \textit{J. H. van Vuuren}, Protection of a graph, to appear in Utilitas Mathematicæ] is a safe guard function \(f=(V_0,V_1)\) such that each \(v\in V_0\) is adjacent to some \(u\in V_1\) for which \(\text{move}(f,u\to v)\) is also a safe guard function; the secure domination number of \(G\), \(\gamma_s(G)\) is the minimum weight of all secure dominating functions. These definitions ``are `smart' in the following sense: they require that, for any unoccupied vertex \(v\) experiencing a problem, there is a guard at an adjacent vertex \(u\) such that moving the guard from \(u\) to \(v\) results in a safe guard function.'' The authors proceed to define {foolproof} versions of these functions, where, for any \(v\in V_0\), the vertex \(u\) is not {some} vertex of \(V_0\cup V_1\) (respectively \(V_0\)) but is \textit{any} vertex in the (open) neighbourhood of \(v\). These 4 concepts are further generalized in the present paper ``so that safe configurations are guaranteed after each of \(k\geq1\) moves to a sequence of problem vertices'' to {smart \(k\)-weak Roman dominating functions}, {foolproof \(k\)-weak Roman dominating functions}, {smart \(k\)-secure dominating functions}, and {foolproof \(k\)-secure dominating functions}, where the minimum weights for a graph \(G\) are denoted, respectively, by \(\gamma_{r,k}(G)\), \(\gamma^*_{r,k}(G)\), \(\gamma_{s,k}(G)\), \(\gamma^*_{s,k}(G)\). In Theorems 3, 4, 5 certain of these minimum weights are determined for paths, cycles, and complete bipartite graphs.