Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 8 3 2023 09 01 Double Roman domination in graphs: algorithmic complexity 491 503 14425 10.22049/cco.2022.27661.1309 EN Abolfazl Poureidi Shahrood University of Technology Journal Article 2022 01 31 Let $G=(V,E)$ be a graph.  A double Roman dominating function  (DRDF) of   $G $   is a function   $f:V\to \{0,1,2,3\}$  such that, for each $v\in V$ with $f(v)=0$,  there is a vertex $u $  adjacent to $v$  with $f(u)=3$ or there are vertices $x$ and $y $  adjacent to $v$  such that  $f(x)=f(y)=2$ and for each $v\in V$ with $f(v)=1$,  there is a vertex $u $    adjacent to $v$    with  $f(u)>1$.  The weight of a DRDF $f$ is   $ f (V) =\sum_{ v\in V} f (v)$.   Let $n$ and  $k$ be integers such that  $3\leq 2k+ 1  \leq n$.  The   generalized Petersen graph $GP (n, k)=(V,E) $  is the  graph  with  $V=\{u_1, u_2,\ldots,  u_n\}\cup\{v_1, v_2,\ldots, v_n\}$ and $E=\{u_iu_{i+1}, u_iv_i, v_iv_{i+k}:  1 \leq i \leq n\}$, where  addition is taken  modulo $n$. In this paper,  we firstly   prove that the  decision     problem  associated with   double Roman domination is NP-omplete even restricted to planar bipartite graphs with maximum degree at most 4.  Next, we   give  a dynamic programming algorithm for  computing a minimum DRDF (i.e., a  DRDF   with minimum weight  along  all   DRDFs)  of $GP(n,k )$  in $O(n81^k)$ time and space  and so a  minimum DRDF  of $GP(n,O(1))$  can be computed in $O( n)$ time and space. https://comb-opt.azaruniv.ac.ir/article_14425_f71d8f6209980c6952292d6281ceb02d.pdf