# Upper bounding the size of a $d$-dominating set

Suppose that $$d > 1$$. Define a $$d$$-dominating set of a graph $$G = (V,E)$$ to be a set $$D \subseteq V$$ such that for any $$v \in V$$, either $$v \in D$$ or $$v$$ has $$\geq$$ $$d$$ neighbors in $$D$$. I would like to show that a graph $$G$$ on $$n$$ vertices and minimum degree $$\delta \geq 150$$ contains a $$d$$-dominating set of size $$O(n \ln{\delta}/\delta)$$. Here is my current approach.

Consider an arbitrary $$p \in [0,1]$$. Randomly and independently, select each vertex of $$V$$ with probability $$p$$. Say $$X$$ is the set of all vertices selected. Define $$Y_X$$ to be the set of all vertices in $$V \setminus X$$ that have at most $$d-1$$ neighbors in $$X$$, so that $$X \cup Y_X$$ is a $$d$$-dominating set. The expected value of $$X$$ is $$np$$. Further,

Pr[$$v \in Y_X$$] $$\leq (1-p) \cdot \sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta - i} = \sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$$.

Hence, the expected value of $$|X| + |Y_X|$$ is at most $$np + n\sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$$. Thus, there must exist an $$X$$ such that $$|X| + |Y_X| \leq np + n\sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$$.

Now, I would like to find a $$p$$ that minimizes the right-hand side of the above inequality, but the summation expression is very unwieldy, so I'm not sure how to proceed from here.

• Have you tried using the one-sided Chebyshev inequality to get a simpler expression? (I haven't tried this myself, just a thought.) May 2, 2019 at 11:48

You had the right approach but it is true that computing $$E[|Y_X|]$$ explicitly is difficult. In this case it is appropriate to use the Chernoff bound. With the Chernoff bound we get $$Pr(v\in Y_X)\le (1-p)e^{-\delta p(1-\frac{d}{\delta p})^2/2}\le (1-p)e^{-\delta p/3}$$ where the second inequality is true for large $$\delta$$. Then by substituting $$p=\frac{3\ln \delta}{\delta}$$ we get $$Pr(v\in Y_X)\le \frac{1}{\delta}-\frac{3\ln \delta}{\delta^2}$$ hence $$E[|X|+|Y|]\le \frac{3n\ln \delta}{\delta}+n(\frac{1}{\delta}-\frac{3\ln \delta}{\delta^2})=O(\frac{n\ln\delta}{\delta})$$ as desired.