Weak Roman domination in Chess graphs

Abstract

Let $G=(V, E)$ be a graph and $f: V \rightarrow\{0,1,2\}$ be a function. A vertex $u$ with weight $f(u)$ is said to be undefended with respect to $f$, if it is not adjacent to any vertex with positive weight. The function $f$ is a weak Roman dominating function (WRDF) if each vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)>0$ such that the function $f^{\prime}: V \rightarrow\{0,1,2\}$ defined by $f^{\prime}(u)=1, f^{\prime}(v)=f(v)-1$ and $f^{\prime}(w)=f(w)$ if $w \in V-\{u, v\}$, has no undefended vertex. The weight of $f$ is $w(f)=\sum_{v \in V} f(v)$. The weak Roman domination number, denoted by $\gamma_r(G)$, is the minimum weight of a weak Roman dominating function on $G$. In this paper, we present a constant time algorithm to obtain $\gamma_r\left(K N_{m, n}\right)$, where, $K N_{m, n}$ is the Knight's graph.