Partitions and Domination in a Graph

Consider a graph \( G \) in which the vertices are partitioned into \( k \) subsets. For each subset, we want a set of vertices of \( G \) that dominate that subset. Note that the vertices doing the domination need not be in the subset itself. We are interested in dominating the entire graph \( G \) as well as dominating each of the \( k \) subsets and minimizing the sum of these \( k + 1 \) dominating sets. For trees and for all values of \( k \), we can determine an upper bound on this sum and characterize the trees that achieve it.