The domination number of a random graph

Abstract

The domination number γ(G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex outside S is adjacent to a vertex in S, while its total domination number γ_t(G) is the minimum cardinality of a set S of vertices so that every vertex in the graph is adjacent to a vertex in S. Let G(n,p) be a random graph of n vertices where each edge is independently chosen with probability p. We show that for every 0 < ∈' < ∈ and p = (l+∈')√1/n(21nn), almost every graph G ∈ G{n>p) has diameter two and (1/2√2-∈)√n ln(n) < γ(G)≤γt(G)<(1/√2+∈)√n ln(n).