Domination Number of Random Graphs

Question

I am investigating the domination number of a random graph $G(n,1/2)$ on $n$ vertices. The edges are formed with probability $1/2$. I know that the domination number of a complete graph $K_n = 1$. I am thinking of two approaches to this investigation:

1. From a complete graph $K_n$ any random graph that has less amount of edges than $K_n$ will have a high domination number, this means we can imagine a complete graph and we remove edges randomly and this domination number will keep increasing. How much is not an easy question.

2. From the empty graph $E_n$ the domination number is $n$. Here we can think of forming a graph randomly putting edges. In this approach the domination number will keep decreasing and it must approach $1$ since the domination number of a complete graph is $1$

Is there any improvement that can be made from this?

Answer 1

Wieland and Godbole (On the domination number of a random graph) show that with high probability, the domination number of $G(n,1/2)$ is equal to one of $$ \lfloor \log_2 n - \log_2(\log_2 n \ln n)\rfloor + 1 \text{ or } \lfloor \log_2 n - \log_2(\log_2 n \ln n)\rfloor + 2. $$ In fact, a similar result, with $\log_2 n$ replaced by $\log_{1/(1-p)} n$, holds for all $p$ that do not approach $0$ too quickly.

---

If we don't need the exact result, we can do only slightly worse with a lot less effort. Here is a simple algorithm that, with high probability, will find a dominating set of order $\log_2 n + O(1)$ in $G(n,1/2)$:

1. Pick an arbitrary vertex $v$ and let $S = \{v\}$
2. Go through the neighbors of $v$ one at a time. For each one, check if it is adjacent to at least half of the vertices not dominated by $S$. If it is, add it to $S$.

After the first step, $S$ dominates $(\frac12 + o(1))n$ of the vertices in the graph. Every time we add a vertex to $S$ in step 2, the number of vertices not dominated by $S$ is cut in half, so we'll be done after step 2 succeeds about $\log_2 n$ times. (Maybe it's $1 + \log_2 n$? I don't know, logs are a headache.)

Of course, in an arbitrary graph, this algorithm could fail if it ran out of vertices in step 2. To see that it does not fail in $G(n,1/2)$, first notice that whenever we look at a vertex $w$ in step 2, the edges of $w$ to vertices not dominated by $S$ have not yet been exposed, so the number of them present in $G(n,1/2)$ is binomial. All we want in step 2 is for that binomial random variable to be at least its mean, which happens with probability greater than $\frac12$.

To get $\log_2 n$ successes, we need on average $2 \log_2 n$ trials. By the very simplest bound - Markov's inequality - the probability is less than $\frac{10 \log_2 n}{n}$ that we'll need to try more than $\frac15 n$ vertices, which comfortably guarantees that we won't run out of vertices to try.