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

1.Previous
3.Next