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 exists a spanning tree with at least a given number of leaves. Therefore, it is believed

1.Previous
3.Next