A connected dominating set of a connected graph 
is a dominating set whose vertices
induce a connected subgraph. Connected dominating
sets therefore form a subset of the dominating sets
of 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.
An inclusion-minimal connected dominating set, meaning one with no proper subset that is also a connected dominating set, is called a minimal connected dominating set. Every minimum connected dominating set is inclusion-minimal, but the converse need not hold.
It is NP-complete to test if there exists a connected dominating set having size less than some given value.
