The relationship between degree of vertex and size of dominating set

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?

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.

• How do you get that probability bound? ​ ​ – user6973 Feb 4 '16 at 11:38
• 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 Feb 4 '16 at 15:06
• Ah, yes. ​ However, it seems like \frac{n \ln n}{d} should be replaced with \left\lceil \hspace{-0.04 in}\frac{n\cdot (\hspace{.02 in}\ln n)}d\hspace{-0.04 in}\right\rceil. ​ ​ ​ ​ – user6973 Feb 4 '16 at 15:11
• Is there any reason to believe that the log n factor can be removed? I suspect that it may be necessary. – Chandra Chekuri Feb 4 '16 at 22:27
• 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 Feb 4 '16 at 22:41

1) 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 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, 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 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 daniello'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).

• Thank you @Florent Foucaud, especially for the referenced paper you provided. – MarsPlus Feb 9 '16 at 22:04