Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$ Let $d &gt; 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 &gt; 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 $&gt; 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)$.
Let $S$ be a maximal set of vertices in which any two vertices are at distance at least 3. (Note maximal just means that $S$ cannot be enlarged by adding new vertices.) By design, any other vertex is at distance at most 2 from some vertex in $S$, and therefore $S$ is a 2-dominating set. On the other hand, if we define the $B_1(v)$ to consist of all vertices at distance at most 1 from $v$, then the sets $B_1(v)$ for $v \in S$ are disjoint. Since the minimum degree is  $\delta$, the size of each set $B_1(v)$ is at least $\delta+1$, hence $|S| \leq n/(\delta+1)$.