Strong Roman Domination in Grid Graphs

Abstract

Consider a graph G of order n and maximum degree . Let f : V (G) → {0, 1, ... , [/2 ]+1 } be a function that labels the vertices of G. Let B0 = {v in V (G) : f(v) = 0}. The function f is a strong Roman dominating function for G if every v in B0 has a neighbor w such that f(w) >1+[ 1 /2 |N(w) B0} ]. In this paper, we study the bounds on strong Roman domination numbers of the Cartesian product Pm􀀀Pk of paths Pm and paths Pk. We compute the exact values for the strong Roman domination number of the Cartesian product P2􀀀Pk and P3􀀀Pk. We also show that the strong Roman domination number of the Cartesian product P4􀀀Pk is between [ 1/3 (8k-[ k/ 8] +1)] and [ 8k/3] for k> 8, and that both bounds are sharp bounds.