"On the Domination Number of a Random Graph" by Ben Wieland and Anant P. Godbole
 

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.

Plum Print visual indicator of research metrics
PlumX Metrics
  • Citations
    • Citation Indexes: 48
  • Usage
    • Abstract Views: 6
  • Captures
    • Readers: 3
see details

Share

COinS