[2] If d is the connected domination number of an n-vertex graph G, where n > 2, 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.
There exists an approximation for the minimum connected dominating set that achieves a factor of 2 ln Δ + O(1), where Δ is the maximum degree of a vertex in G.[4] The maximum leaf spanning tree problem is MAX-SNP hard, implying that no polynomial time approximation scheme is likely.
[7] The maximum leaf problem is fixed-parameter tractable, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size.
[9] In graphs of maximum degree three, the connected dominating set and its complementary maximum leaf spanning tree problem can be solved in polynomial time, by transforming them into an instance of the matroid parity problem for linear matroids.
[10] Connected dominating sets are useful in the computation of routing for mobile ad hoc networks.