Double Roman domination in graphs: algorithmic complexity

Document Type : Original paper

Author

Shahrood University of Technology

Abstract

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.

Keywords

Main Subjects

References

[1] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[2] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Comput. 364 (2020), ID: 124617.
[3] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Maximal double Roman domination in graphs, Appl. Math. Comput. 414 (2022), ID: 126662.
[4] S. Banerjee, M.A. Henning, and D. Pradhan, Algorithmic results on double Roman domination in graphs, J. Comb. Optim. 39 (2020), no. 1, 90–114.
[5] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[6] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.
[7] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019), no. 1.
[8] R. Khoeilar, H. Karami, M. Chellali, and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019), 159–167.
[9] S. Kosari, Z. Shao, S.M. Sheikholeslami, M. Chellali, R. Khoeilar, and H. Karami, Double Roman domination in graphs with minimum degree at least two and no c5-cycle, Graphs Combin. 38 (2022), no. 2, 1–16.
[10] Bojan Mohar, Face covers and the genus problem for apex graphs, J. Combin. Theory Ser. B 82 (2001), no. 1, 102–117.
[11] C. Padamutham and V.S.R. Palagiri, Complexity of Roman {2}-domination and the double Roman domination in graphs, AKCE Int. J. Graphs Comb. 17 (2020), no. 3, 1081–1086.
[12] A. Poureidi and N. Jafari Rad, On algorithmic complexity of double Roman domination, Discrete Appl. Math. 285 (2020), 539–551.
[13] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77.
[14] M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), no. 2, 152–164.
[15] X. Zhang, Z. Li, H. Jiang, and Z. Shao, Double Roman domination in trees, Inform. Process. Lett. 134 (2018), 31–34.
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 491-503

Files

Share

How to cite

Statistics