Rainbow domination on trees
Journal
Discrete Applied Mathematics
Journal Volume
158
Journal Issue
1
Pages
8-12
Date Issued
2010
Author(s)
Abstract
This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V (G) to the set of all subsets of {1, 2, ..., k} such that for any vertex v with f (v) = 0{combining long solidus overlay} we have ∪u ∈ NG (v) f (u) = {1, 2, ..., k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number γr k (G) of a graph G, that is the minimum value of ∑v ∈ V (G) | f (v) | where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that γr k (T) = | V (T) |. © 2009 Elsevier B.V. All rights reserved.
Type
journal article