On the Algorithmic Complexity of Roman f2g-Domination (Italian Domination)

Nader Jafari Rad | Poureidi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=137641
Date :  2020/06/24
Publish in :    Iranian Journal of Science and Technology, Transactions A: Science


Keywords :Roman f2g-dominating function  Algorithm  3-SAT  PLANAR 3-SAT problem

Abstract :

---

A Roman f2g-dominating function (R2DF) f : V  f0; 1; 2g of a graph G ¼ ðV; EÞ has the property that for every vertex v 2 V with f ðvÞ ¼ 0 either there is a vertex u 2 NðvÞ with f ðuÞ ¼ 2 or there are two vertices x; y 2 NðvÞ with f ðxÞ ¼ f ðyÞ ¼ 1. The weight of f is the sum f ðVÞ ¼ Pv2V f ðvÞ. The minimum weight of an R2DF on G is the Roman f2gdomination number of G. In this paper, we first show that the associated decision problem for Roman f2g-domination is NP-complete even when restricted to planar graphs. Then, we give a linear algorithm that computes the Roman f2gdomination number of a given unicyclic graph.)