%0 Journal Article %T Double Roman domination in graphs: algorithmic complexity %J Communications in Combinatorics and Optimization %I Azarbaijan Shahid Madani University %Z 2538-2128 %A Poureidi, Abolfazl %D 2023 %\ 09/01/2023 %V 8 %N 3 %P 491-503 %! Double Roman domination in graphs: algorithmic complexity %K Double Roman dominating function %K Algorithm %K Dynamic programming %K generalized Petersen graph %R 10.22049/cco.2022.27661.1309 %X 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. %U http://comb-opt.azaruniv.ac.ir/article_14425_f71d8f6209980c6952292d6281ceb02d.pdf