کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421298 | 684186 | 2010 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Rainbow domination on trees Rainbow domination on trees](/preview/png/421298.png)
This paper studies a variation of domination in graphs called rainbow domination. For a positive integer kk, a kk-rainbow dominating function of a graph GG is a function ff from V(G)V(G) to the set of all subsets of {1,2,…,k}{1,2,…,k} such that for any vertex vv with f(v)=0̸f(v)=0̸ we have ∪u∈NG(v)f(u)={1,2,…,k}∪u∈NG(v)f(u)={1,2,…,k}. The 11-rainbow domination is the same as the ordinary domination. The kk-rainbow domination problem is to determine the kk-rainbow domination number γrk(G) of a graph GG, that is the minimum value of ∑v∈V(G)|f(v)|∑v∈V(G)|f(v)| where ff runs over all kk-rainbow dominating functions of GG. In this paper, we prove that the kk-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the kk-rainbow domination problem on trees. For a given tree TT, we also determine the smallest kk such that γrk(T)=|V(T)|.
Journal: Discrete Applied Mathematics - Volume 158, Issue 1, 6 January 2010, Pages 8–12