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).
Original language | English |
---|---|
Pages (from-to) | 315-328 |
Number of pages | 14 |
Journal | Utilitas Mathematica |
Volume | 94 |
Publication status | Published - Jul 2014 |
Keywords
- Diameter two
- Domination number
- Random graph
- Total domination number
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Applied Mathematics