A connected dominating set in a connected graph 
is a dominating set in 
whose vertices induce a connected
subgraph, i.e., one in which there is no dominating vertex not connected to some
other dominating vertex by an edge. Connected dominating sets therefore comprise
a subset of all dominating sets in a graph.
A minimum connected dominating set of a graph 
is a connected dominating set of smallest possible size, where the minimum size is
denoted 
and known as the connected domination number.
It is NP-complete to test if there exists a connected dominating set having size less than some given value.
