The maximum leaf number l(G) of a graph G is the largest number of tree leaves in any of its spanning trees. (The corresponding smallest number of leaves is known as the minimum leaf number.) The maximum leaf number and connected domination number d(G) 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. 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 | connected domination number | minimum leaf number | spanning tree | tree leaf