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→{0,1,2,3}  such that, for each v∈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∈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)=∑v∈Vf(v).   Let n and  k be integers such that  3≤2k+1≤n.  The   generalized Petersen graph GP(n,k)=(V,E)  is the  graph  with  V={u1,u2,…,un}∪{v1,v2,…,vn} and E={uiui+1,uivi,vivi+k:1≤i≤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(n81k) 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