<p><b>1)</b> To refine daniello's answer, there is a standard bound in domination that for any graph of minimum degree $d$, there is a dominating set of size at most (roughly) $\frac{\log d}{d}n$.
This bound has a simple and nice probabilistic proof (similar to the one given by daniello); see for example Theorem 1.2.2 in the Alon-Spencer book <em>The probabilistic method</em> (there the exact bound they give is $\frac{1+\ln (d+1)}{d+1}n$).</p>

<p>Moreover the bound is known to be asymptotically tight. See <a href="http://link.springer.com/article/10.1007%2FBF01787474" rel="noreferrer">this paper by Alon</a>, also available on the author's webpage, for the tightness (in the language of hypergraph transversals).</p>

<p>Note that for small values of $d$, it is an active field of research to determine the best bound, and the situation is not yet fully understood already for small $d$; see <a href="http://link.springer.com/article/10.1007/s00373-015-1585-7" rel="noreferrer">this paper</a> for a nice discussion about this, as well as some early references for the above bound.</p>

<p>Now, when $d=n^k$, the bound gives a dominating set of size roughly $kn^{1-k}\ln n$, about the same as what we get from daniello's answer. I don't know whether the Alon construction is tight for such values of $d$, but my guess would be yes.</p>

<p><b>2)</b> A second easy observation is that when the degrees are bounded by above (say by $\Delta$), any vertex can dominate at most $\Delta+1$ vertices and hence any dominating set has size at least $\frac{n}{\Delta+1}$. This is easily seen to be tight by creating a graph from a collection of disjoint stars with $\Delta$ leaves each (potentially adding a few edges to make it connected).</p>

CC BY-SA 3.0
2016-02-09T22:04:14.800Z
Thank you @Florent Foucaud, especially for the referenced paper you provided.
MarsPlus
CC BY-SA 3.0
2016-02-05T22:38:19.483Z
2016-02-05T22:38:19.483Z
Florent Foucaud
<p>If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the probability that $v$ is not dominated by $S$ is upper bounded by $(1 - \frac{d}{n})^{\frac{n\ln n}{d}} \leq e^{-\ln n} = \frac{1}{n}$. Introduce an indicator variable for every vertex that is $1$ if it is not dominated by $S$ and $0$ otherwise. The number of undominated vertices is the sum of indicator variables, so the expected number of undominated vertices is at most $n \cdot \frac{1}{n} = 1$. Hence there exists a set of size $\frac{n \ln n}{d}$ that leaves at most one vertex undominated, add this vertex to the dominating set.    </p>

<p>For your question it means that if all vertices have degree at least $n^k$ then there is a dominating set of size $n^{1-k}\log n + 1$. Would be nice to see if one can get rid of the $\log n$ or not. </p>

CC BY-SA 3.0
2016-02-04T15:06:43.507Z
Imagine picking S in $n \ln n/d$ rounds adding one vertex to S at a time. The probability that $v$ becomes dominated in round $i$ is at least $d/n$ since it has at least $d$ neighbors and we pick from $n-i+1 \geq n$ vertices. So the probability that $v$ never gets dominated is at most $(1-(d/n))$ to the power of the number of rounds.
daniello
CC BY-SA 3.0
2016-02-04T22:27:51.797Z
Is there any reason to believe that the log n factor can be removed? I suspect that it may be necessary.
Chandra Chekuri
CC BY-SA 3.0
2016-02-04T22:41:20.950Z
Another way to see the bound is by observing that if you can obtain a fractional solution to the dominating set by setting a value of $1/(d+1)$ on each vertex where $d$ is the minimum degree. The total value of this fractional solution is $n/(d+1)$ and it is easy to see that it is feasible. Now by randomized rounding or known integrality gap results there is an integral solution of value $n\ln n/(d+1)$.
Chandra Chekuri
CC BY-SA 3.0
2016-02-05T07:32:26.983Z
Isn't the integrality gap $\log d$? Then one could excgange the $\log n$ factor with $\log d$.
daniello
CC BY-SA 3.0
2016-02-06T03:20:04.773Z
Yes, that is correct. The bound should be $n H_{d+1}/(d+1)$ where $H_k$ is the $k$'th harmonic number. $H_{d+1}$ is at most $1 + \ln (d+1)$. Hence this bound matches what Florent posted in the answer below.
Chandra Chekuri
CC BY-SA 3.0
2016-02-11T21:55:25.187Z
I believe the right asymptotic bound also falls out if you pick each vertex for a dominating set with probability $\Theta(\log d / (d+1))$ and apply the local lemma.
Andrew D. King
CC BY-SA 3.0
2016-02-04T09:15:36.583Z
2016-02-04T09:15:36.583Z
daniello
<p>I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has degree $\ge n^k \,(k&lt; 1)$, is it possible to bound the size of dominating set, i.e $O(n^k)$? Could anyone point me out any materials/papers/books related to this problem?</p>

<graph-theory><graph-algorithms><co.combinatorics><randomized-algorithms>
The relationship between degree of vertex and size of dominating set
MarsPlus
# The relationship between degree of vertex and size of dominating set

(Asked by: username_0 on 2016-02-04)

I was wondering is there any relationship between degree of vertex and size of dominating set. For example, if I know the number of vertices is $n$, and I could know each vertex in the graph has degree $\ge n^k \,(k< 1)$, is it possible to bound the size of dominating set, i.e $O(n^k)$? Could anyone point me out any materials/papers/books related to this problem?

**Tags:** graph-theory, graph-algorithms, co.combinatorics, randomized-algorithms


---

## 2 answers

### Answer by username_2 on 2016-02-04. Score: 6 | Accepted answer

If all vertices have degree at least $d$ then there is always a dominating set of size $\frac{n \ln n}{d} + 1$. Pick a random set $S$ of size $\frac{n \ln n}{d}$. For a particular vertex $v$, the probability that $v$ is not dominated by $S$ is upper bounded by $(1 - \frac{d}{n})^{\frac{n\ln n}{d}} \leq e^{-\ln n} = \frac{1}{n}$. Introduce an indicator variable for every vertex that is $1$ if it is not dominated by $S$ and $0$ otherwise. The number of undominated vertices is the sum of indicator variables, so the expected number of undominated vertices is at most $n \cdot \frac{1}{n} = 1$. Hence there exists a set of size $\frac{n \ln n}{d}$ that leaves at most one vertex undominated, add this vertex to the dominating set.

For your question it means that if all vertices have degree at least $n^k$ then there is a dominating set of size $n^{1-k}\log n + 1$. Would be nice to see if one can get rid of the $\log n$ or not.

> **Comments:**
> **username_2**: Imagine picking S in $n \ln n/d$ rounds adding one vertex to S at a time. The probability that $v$ becomes dominated in round $i$ is at least $d/n$ since it has at least $d$ neighbors and we pick from $n-i+1 \geq n$ vertices. So the probability that $v$ never gets dominated is at most $(1-(d/n))$ to the power of the number of rounds.  
> **username_3**: Is there any reason to believe that the log n factor can be removed? I suspect that it may be necessary.  
> **username_3**: Another way to see the bound is by observing that if you can obtain a fractional solution to the dominating set by setting a value of $1/(d+1)$ on each vertex where $d$ is the minimum degree. The total value of this fractional solution is $n/(d+1)$ and it is easy to see that it is feasible. Now by randomized rounding or known integrality gap results there is an integral solution of value $n\ln n/(d+1)$.  
> **username_2**: Isn't the integrality gap $\log d$? Then one could excgange the $\log n$ factor with $\log d$.  
> **username_3**: Yes, that is correct. The bound should be $n H_{d+1}/(d+1)$ where $H_k$ is the $k$'th harmonic number. $H_{d+1}$ is at most $1 + \ln (d+1)$. Hence this bound matches what Florent posted in the answer below.  
> **username_4**: I believe the right asymptotic bound also falls out if you pick each vertex for a dominating set with probability $\Theta(\log d / (d+1))$ and apply the local lemma.  

---

### Answer by username_1 on 2016-02-05. Score: 5

**1)** To refine username_2's answer, there is a standard bound in domination that for any graph of minimum degree $d$, there is a dominating set of size at most (roughly) $\frac{\log d}{d}n$.
This bound has a simple and nice probabilistic proof (similar to the one given by username_2); see for example Theorem 1.2.2 in the Alon-Spencer book *The probabilistic method* (there the exact bound they give is $\frac{1+\ln (d+1)}{d+1}n$).

Moreover the bound is known to be asymptotically tight. See [this paper by Alon](http://link.springer.com/article/10.1007%2FBF01787474), also available on the author's webpage, for the tightness (in the language of hypergraph transversals).

Note that for small values of $d$, it is an active field of research to determine the best bound, and the situation is not yet fully understood already for small $d$; see [this paper](http://link.springer.com/article/10.1007/s00373-015-1585-7) for a nice discussion about this, as well as some early references for the above bound.

Now, when $d=n^k$, the bound gives a dominating set of size roughly $kn^{1-k}\ln n$, about the same as what we get from username_2's answer. I don't know whether the Alon construction is tight for such values of $d$, but my guess would be yes.

**2)** A second easy observation is that when the degrees are bounded by above (say by $\Delta$), any vertex can dominate at most $\Delta+1$ vertices and hence any dominating set has size at least $\frac{n}{\Delta+1}$. This is easily seen to be tight by creating a graph from a collection of disjoint stars with $\Delta$ leaves each (potentially adding a few edges to make it connected).

> **Comments:**
> **username_0**: Thank you @username_1, especially for the referenced paper you provided.  

---

