CONNECTED DOMINATION AND SPANNING TREES WITH MANY LEAVES.

Let G = (V,E) be a connected graph. A connected dominating set S ⊂ V is a dominating set that induces a connected subgraph of G. The connected domination number of G, denoted γ_c(G), is the minimum cardinality of a connected dominating set. Alternatively, ∣V∣ - γ_c(G) is the maximum number of leaves in a spanning tree of G. Let δ denote the minimum degree of G. We prove that γ_c(G) ≤ ∣V∣ ln(δ+1) / δ+1 (1 + o_δ(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. [ABSTRACT FROM AUTHOR]