An important subclass of the dominating sets is the class of connected dominating sets. If "S" is a connected dominating set, one can form a spanning tree of "G" in which "S" forms the set of non-leaf vertices of the tree; conversely, if "T" is any spanning tree in a graph with more than two vertices, the non-leaf vertices of "T" form a connected dominating set. Therefore, finding minimum connected dominating sets is equivalent to finding spanning trees with the maximum possible number of leaves.