On the Domination Number of a Random Graph

Document Type

Article

Publication Date

1-1-2001

Description

In this paper, we show that the domination number D of a random graph enjoys as sharp a concentration as does its chromatic number χ. We first prove this fact for the sequence of graphs {G(n, pn} n → ∞, where a two point concentration is obtained with high probability for pn = p (fixed) or for a sequence pn that approaches zero sufficiently slowly. We then consider the infinite graph G(ℤ+, p), where p is fixed, and prove a three point concentration for the domination number with probability one. The main results are proved using the second moment method together with the Borel Cantelli lemma.

Share

COinS