# Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

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)$$.

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)$$.

• Wow, such a simple argument. Thanks, Yuval. – MathFan9402 May 3 at 8:05