Animation scientifique

In an undirected graph, a vertex is uni-dominated by a set $S$ if exactly one vertex of $S$ lies in its closed neighborhood. The set $S$ is an efficient dominating set if every vertex is uni-dominated by $S$. Since many graphs have no efficient dominating set, we study two variants: either $S$ must dominate every vertex (Full-Cover), or no vertex can be dominated more than once by $S$ (Non-Overlapping). In both cases we maximize the number of uni-dominated vertices. We present bounds, in particular on trees, and complexity results for both variants, and compare them.