Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at most distance $d$ from some vertex in $D$. Prove that if $\delta$, the minimum degree of $G$, satisfies $\delta > 50$, then $G$ has a distance $d$-dominating set of size $O(n/\delta)$.
I am considering a greedy algorithm to construct $D$. In each step, pick a vertex that covers the maximum number of "uncovered" vertices (i.e., vertices that are of distance $> d$ from any element in $D$). For each vertex $v$, let $C(v)$ be the set consisting of $v$ together with all of that vertices that are at most distance $d$ from $v$. Suppose that during the process of picking vertices the number of vertices $u$ that do not lie in the union of the sets $C(v)$ of the vertices chosen so far is $r$. Then by assumption, the sum of the cardinalities of the sets $C(u)$ over all uncovered vertices $u$ is at least $r x$....
The drawback of this approach is that I don't see how $x$, a lower bound on the number of vertices within distance $d$ of a vertex in $G$, can be more than $\delta + 1$ (i.e., the order of the complete graph $K_{\delta + 1}$). Unfortunately, if we use this lower bound for $x$ in general, we won't get a dominating set of size $O(n/\delta)$.
