Algorithmic and complexity aspects of computing Roman {2}-domination in graphs

Let G (V,E) be a graph. A Roman {2}-dominating function (R2DF) } 2, 1, 0{ : Vf on G has the property that for every vertex Vv i ith 0 v feither there is ) (v Nu i ith 2) ( uf or there are ) ( , v N y x i ith 1) ( ) ( y f x f . The i eight of a R2DF f is equal to v V v f f w Theminimum i eight of a R2DF on G is the Roman {2}- domination number of G . In this paper, i e first shoi that the associated decisionproblem for Roman {2}-domination is NP-complete even i hen restricted to chordal and planar graphs. Then, i e give a linear algorithm that computes the Roman {2}-domination number of a given tree

Keywords:

Roman {2}-dominating function , Algorithm , 3-SAT