# Upper bound on the size of a distance $d$ dominating set

Consider a graph $$G = (V,E)$$ of order $$n$$ and minimum degree $$\delta > 75$$. Given $$d > 1$$, a distance $$d$$ dominating set $$D \subseteq V$$ is such that, for any $$v \in V$$, either $$v \in D$$ or $$v$$ is within distance $$d$$ of some vertex in $$D$$. I want to show that there exists such a dominating set of size $$O(n/\delta)$$.

My current approach is to consider the $$d$$-th power of $$G$$, $$G^d$$, and upper bound the size of a distance $$1$$ dominating set in $$G^d$$ (i.e., a normal dominating set). It is well known that, in general, if $$\delta' > 1$$ is the minimum degree of a graph $$G'$$ of order $$n'$$, then it has a distance $$1$$ dominating set of size at most $$n' \frac{1+\ln(\delta' + 1)}{\delta'+1}$$. However, I am not sure how to bound the minimum degree in $$G^d$$.

• The minimum degree in $G^d$ may not be any higher than $\delta(G)$, for example if $G$ is the disjoint union of cliques. May 3, 2019 at 6:19
• Are there better bounds on $\delta(G^d)$ if $G$ is connected? May 3, 2019 at 7:08
• Not by much. Connect those cliques by a path and now $\delta(G^d) = \delta(G) \cdot O(d)$, which doesn't appear to help you enough. May 3, 2019 at 15:02