Rainbow domination and related problems on strongly chordal graphs

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: V (G) --> 2({1, 2, ..., k}) such that boolean OR(u is an element of NG(v)) f(u) = {1, 2, ..., k} for any vertex v with f(v) = empty set. The k-rainbow domination number gamma(rk)(G) of G is the minimum value of Sigma(v is an element of V(G)) \f(v)\, where f runs over all k-rainbow dominating functions of G. A related concept is as follows. A weak {k}-dominating function of G is a function g: V (G) {0, 1, 2,, k} such that Sigma(u is an element of NG(v)) g(u) >= k for any vertex v with g(v) = 0. The weak {k}-domination number gamma(wk)(G) of G is the minimum value of Sigma(v is an element of V(G)) g(v), where g runs over all weak {k}-dominating functions of G. In this paper, we prove that gamma(wk)(G) = gamma(rk)(G) for any strongly chordal graph G. Our approach is a more general setting called the k-function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak {k}-domination numbers of block graphs. (C) 2013 Published by Elsevier B.V.