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

| cite | improve this answer | |
  • $\begingroup$ Wow, such a simple argument. Thanks, Yuval. $\endgroup$ – MathFan9402 May 3 '19 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.