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 connecte d domination number of G, denoted gamma(c)(G), is the minimum cardinality o f a connected dominating set. Alternatively, \V\ - gamma(c)(G) is the maxim um number of leaves in a spanning tree of G. Let delta denote the minimum d egree 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 ot her is a randomized parallel algorithm in RNC.