KYUNGPOOK Math. J. 2019; 59(3): 515-523
Published online September 23, 2019
Copyright © Kyungpook Mathematical Journal.
Strong Roman Domination in Grid Graphs
Xue-Gang Chen, Moo Young Sohn∗
Department of Mathematics, North China Electric Power University, Beijing 102206, China
e-mail : gxcxdm@163.com
Department of Mathematics, Changwon National University, Changwon 51140, Korea
e-mail : mysohn@changwon.ac.kr
Received: January 2, 2019; Revised: September 3, 2019; Accepted: September 19, 2019
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+⌈12|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 ⌈13(8k−⌊k8⌋+1⌉ and ⌈8k3⌉ for k ≥ 8, and that both bounds are sharp bounds.
Keywords: Roman domination number, strong Roman domination number, grid.