Connected domination and spanning trees with many leaves

Let G = (V, E) be a connected graph. A connected dominating set S subset of V is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted gamma(c)(G), is the minimum cardinality of a connected dominating set. Alternatively, \V\ - gamma(c)(G) is the maximum number of leaves in a spanning tree of G. Let delta denote the minimum degree of G. We prove that gamma(c)(G) less than or equal to \V\ln(delta + 1)/delta + 1(1 + o(delta)(1)). Two algorithms that construct a set this good are presented. One is a sequential polynomial time algorithm, while the other is a randomized parallel algorithm in RNC.