On algorithmic complexity of double Roman domination

Nader Jafari Rad | Poureidi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137680
Date :  2020/10/15
Publish in :    Discrete Applied Mathematics
DOI :  https://doi.org/https://doi.org/10.1016/j.dam.2020.06.023
Link :  https://www.sciencedirect.com/science/article/pii/S0166218X20303449
Keywords :Dominating set Double Roman dominating function Algorithm 3-SAT Combinatorial problems

Abstract :

---

In this paper, we first show that the decision problem associated to double Roman domination is NP-complete even when restricted to planar graphs. Then, we study the complexity issue of a problem posed in R.A. Beeler, T.W. Haynesa and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29, and show that the problem of deciding whether a given graph is double Roman is NP-hard even when restricted to bipartite or chordal graphs. Then, we give linear algorithms that compute the domination number and the double Roman domination number of a given unicyclic graph. Finally, we give a linear algorithm that decides whether a given unicyclic graph is double Roman.