ON THE CONCENTRATION OF THE DOMINATION NUMBER OF THE RANDOM GRAPH

In this paper we study the behavior of the domination number of the Erdos-Renyi random graph G(n, p). Extending a result of Wieland and Godbole we show that the domination number of G(n, p) is equal to one of two values asymptotically almost surely whenever p >> ln(2)n/root n. The explicit values are exactly at the first moment threshold, that is, where the expected number of dominating sets starts to tend to infinity. For small p we also provide various nonconcentration results which indicate why some sort of lower bound on the probability p is necessary in our first theorem. Concentration, though not on a constant length interval, is proven for every p >> 1/n. These results show that unlike in the case of p >> ln(2)n/root n, where concentration of the domination number happens around the first moment threshold, for p = O(ln n/n) it does so around the median. In particular, in this range the two are far apart from each other.