关键词: Domination number, Roman {2}-dominating function, Independent Roman {2}-domination number

Abstract: For a graph G = (V,E), a Roman {2}-dominating function f :V → {0,1,2} has the property that for every vertex v ∈V with f(v) = 0, either v is adjacent to at least one vertex u for which f(u) = 2, or at least two vertices u₁ and u₂ for which f(u₁) =f(u₂) = 1. A Roman {2}-dominating function f = (V₀,V₁,V₂) is called independent if V₁∪V₂ is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =\sum_v∈V f(v), and the independent Roman {2}-domination number i_{R2}(G) is the minimum weight of an independent Roman {2}-dominating function on G. In this paper, we characterize all trees with i_{R2}(T) =γ(T)+ 1, and give a linear time algorithm to compute the value of i_{R2}(T) for any tree T. 

Key words: Domination number, Roman {2}-dominating function, Independent Roman {2}-domination number