The domination number of a random graph

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)315-328
Number of pages14
JournalUtilitas Mathematica
Volume94
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'The domination number of a random graph'. Together they form a unique fingerprint.

Cite this