Strong Roman Domination in Grid Graphs.

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 ∈ V (G) : f(v) = 0}. The function f is a strong Roman dominating function for G if every v ∈ B0 has a neighbor w such that f(w)≥1+⌈½|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⌋+ k ≥ 8, and that both bounds are sharp bounds. [ABSTRACT FROM AUTHOR]