The connected domination number of a connected graph G, denoted d(G), is the size of a minimum connected dominating set of a graph G. The maximum leaf number l(G) and connected domination number of a graph G are connected by d(G) + l(G) = left bracketing bar G right bracketing bar , where n = left bracketing bar G right bracketing bar >2 is the vertex count of G. It is NP-complete to test if there exists a connected dominating set having size less than some given value. Many families of graphs have simple closed forms, as summarized in the following table. In the table, ⌊x⌋ denotes the floor function.

connected dominating set | dominance | dominating set | domination number | domination polynomial | maximum leaf number | minimum connected dominating set