2012/09/14 by Roman Glebov, Anita Liebenau, Glebov, Roman +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO
paper · pdf · doi:10.48550/arxiv.1209.3115
openalex publication_date 2012/09/14 · arxiv created 2015/03/15 · arxiv updated 2015/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we study the behaviour of the domination number of the Erdős-Rényi 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 ≫ (ln2n)/(√(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 non-concentration 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 ≫ (ln2n)/(√(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.