On tree census and the giant component in sparse random graphs

Publisher Website
Google Scholar
Abstract
For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define tn(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[tn(k) ‐ nh(k)]n−1/2} is shown to be Gaussian in the limit n →∞, with h(k) = kk−2ck−1e−kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 − T)−2(1 − 2Tθ)θ(1 − θ) for the first model and n(1 − T)−2θ(1 − θ) for the second model. Here Te−T = ce−c, TT/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc−1(β + β2/2) and variance n[c−1(β + β2/2) −c−2(c + 1)β2], where βeβ = c. It is also proven that almost surely the giant component consists of a giant two‐connected core of size about n(1 − T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.

This publication has 20 references indexed in Scilit: