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

  • 1
    $\begingroup$ The minimum degree in $G^d$ may not be any higher than $\delta(G)$, for example if $G$ is the disjoint union of cliques. $\endgroup$ May 3, 2019 at 6:19
  • $\begingroup$ Are there better bounds on $\delta(G^d)$ if $G$ is connected? $\endgroup$ May 3, 2019 at 7:08
  • $\begingroup$ 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. $\endgroup$ May 3, 2019 at 15:02


You must log in to answer this question.

Browse other questions tagged .