Complementarity
If d is the connected domination number of an n-vertex graph G, and l is its max leaf number, then the three quantities d, l, and n obey the simple equation
If D is a connected dominating set, then there exists a spanning tree in G whose leaves include all vertices that are not in D: form a spanning tree of the subgraph induced by D, together with edges connecting each remaining vertex v that is not in D to a neighbor of v in D. This shows that l ≥ n − d.
In the other direction, if T is any spanning tree in G, then the vertices of T that are not leaves form a connected dominating set of G. This shows that n − l ≥ d. Putting these two inequalities together proves the equality n = d + l.
Therefore, in any graph, the sum of the connected domination number and the max leaf number equals the total number of vertices. Computationally, this implies that finding the minimum dominating set is equally difficult to finding a maximum leaf spanning tree.
Read more about this topic: Connected Dominating Set