On the Roman Domination Numbers of Generalized Petersen Graphs

Abstract

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,\dots ,u_n\}\cup \{v_1,v_2,\dots ,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\le i\le 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\ge 5$.