On the Roman Domination Numbers of Generalized Petersen Graphs

For natural numbers \( n \) and \( k \), where \( n > 2k \), a generalized Petersen graph \( P(n,k) \) is obtained by letting its vertex set be \( \{u_1, u_2, \ldots, u_n\} \cup \{v_1, v_2, \ldots, v_n\} \) and its edge set be the union of \( \{u_i u_{i+1}, u_i v_i, v_i v_{i+k}\} \) over \( 1 \leq i \leq n \), where subscripts are reduced modulo \( n \). In this paper, an integer programming formulation for Roman domination is established, which is used to give upper bounds for the Roman domination numbers of the generalized Petersen graphs \( P(n,3) \) and \( P(n,4) \). Together with the dynamic algorithm, we determine the Roman domination number of the generalized Petersen graph \( P(n,3) \) for \( n \geq 5 \).