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 kk, a kk-rainbow dominating function of a graph GG is a function f:V(G)→2{1,2,…,k}f:V(G)→2{1,2,…,k} such that ∪u∈NG(v)f(u)={1,2,…,k}∪u∈NG(v)f(u)={1,2,…,k} for any vertex vv with f(v)=0̸f(v)=0̸. The kk-rainbow domination number γrk(G) of GG 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. A related concept is as follows. A weak {k}{k}-dominating function of GG is a function g:V(G)→{0,1,2,…,k}g:V(G)→{0,1,2,…,k} such that ∑u∈NG(v)g(u)≥k∑u∈NG(v)g(u)≥k for any vertex vv with g(v)=0g(v)=0. The weak {k}{k}-domination number γwk(G) of GG is the minimum value of ∑v∈V(G)g(v)∑v∈V(G)g(v), where gg runs over all weak {k}{k}-dominating functions of GG. In this paper, we prove that γwk(G)=γrk(G) for any strongly chordal graph GG. Our approach is a more general setting called the kk-function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak {k}{k}-domination numbers of block graphs.