Rainbow domination on trees
Dr. Jiaojiao Wu 吳佼佼博士台 灣 大 學 數 學 系 下午 3:00–4:00 鴻經館 107 室 For a positive integer k, we use [k] to denote the set {1, 2, ... ,k}, and the set of all subsets of [k]. A k-rainbow dominating function of G is a function f : V (G) → such that for every vertex v, either or . The weight of f is defined as.The k-rainbow domination number of G is the minimum weight of a k-rainbow dominating function. We prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We give a linear-time algorithm for the k-rainbow domination problem on trees.