科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 u1 and u2 for which f(u1) = f(u2) = 1.A Roman {2}-dominating function f =(V0,V1,V2) is called independent if V1 ∪ V2 is an independent set. The weight of an independent Roman {2}-dominating function f is the value ω(f) =Σ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.
- 单位
