On the concentration of the domination number of the random graph

Roman Glebov, Anita Liebenau, Tibor Szabo

Research output: Contribution to journalArticleResearchpeer-review

20 Citations (Scopus)


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
Original languageEnglish
Pages (from-to)1186-1206
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 2015
Externally publishedYes

Cite this