In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. Definitions A connected dominating set of a graph G is a set D of vertices with two properties: Any node in D can reach any other node in D by a path that stays entirely within D. That is, D induces a connected subgraph of G. Every vertex in G either belongs to D or is adjacent to a vertex in D. That is, D is a dominating set of G. A minimum connected dominating set of a graph G is a connected dominating set with the smallest possible cardinality among all connected dominating sets of G. The connected domination number of G is the number of vertices in the minimum connected dominating set. Any spanning tree T of a graph G has at least two leaves, vertices that have only one edge of T incident to them. A maximum leaf spanning tree is a spanning tree that has the largest possible number of leaves among all spanning trees of G. The max leaf number of G is the number of leaves in the maximum leaf spanning tree. Complementarity 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 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 Putting these two inequalities together proves the equality 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 determining the connected domination number is equally difficult as finding the max leaf number. Algorithms It is NP-complete to test whether there exists a connected dominating set with size less than a given threshold, or equivalently to test whether there