Partitions and Domination in a Graph

Abstract

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.