Connected dominating set

In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph. A connected dominating set of a graph G is a set D of vertices with two properties: 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. 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.