Roman [1,2]-domination of graphs

A [1, 2]- set of a graph G is a set S of vertices of G if every vertex not in.. has one or two neighbors in S The [1, 2]- domination number gamma([1,2])(G) of.. equals the minimum cardinality of a [1, 2]- set of G A Roman [1, 2]- dominating function (R[1, 2] DF) on a graph G is a function f from the vertex set V of G to the set {0, 1, 2} such that any vertex assigned 0 under f has one or two neighbors assigned 2. The weight of an R[1, 2] DF f is the sum Sigma(x is an element of v) f(x). The Roman [1, 2]-domination number gamma(R[1,2])(G) of G equals the minimum weight of an R[1, 2] DF on G. In this paper, we prove that the decision problem on the Roman [1, 2]- domination is NP-complete for bipartite and chordal graphs. Moreover, we give some bounds on the Roman [1, 2]- domination number. In particular, we show that for any nontrivial tree T,gamma(R[1,2])(T) >= gamma(R[1,2])(T) + 1 and characterize all trees obtaining equality in this bound.