Rainbow Domination and Related Problems on Some Classes of Perfect Graphs

Overview & Synopsis

Let $k \in \mathbb {N}$ and let G be a graph. A function $f: V(G) \rightarrow 2^{[k]}$ is a rainbow function if, for every vertex x with $f(x)=\varnothing $f(x)=∅, $f(N(x)) =[k]$, where [k] denotes the integers ranging from 1 to k. The rainbow domination number $\gamma _{kr}(G)$ is the minimum of $\sum _{x \in V(G)} |f(x)|$ over all rainbow functions. We investigate the rainbow domination problem for some classes of perfect graphs.