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.
Citation Information
Wieland, Ben; and Godbole, Anant P.. 2001. On the Domination Number of a Random Graph. Electronic Journal of Combinatorics. Vol.8(1 R). 1-13. https://doi.org/10.37236/1581 ISSN: 1077-8926