Dominating Sets With at Most $k$ Components

Abstract

A connected dominating set $D$ of a graph $G$ has the property that not only does $D$ dominate the graph but the subgraph induced by the vertices of $D$ is also connected. We generalize this concept by allowing the subgraph induced by $D$ to contain at most $k$ components and examine the minimum possible order of such a set. In the case of trees, we provide lower and upper bounds and a characterization for those trees which achieve the former.