The giant k-core of a random graph with a specified degree sequence

The k-core of a graph is the maximal induced subgraph with minimum degree k. In this paper, we nd conditions under which the k-core of a random graph with a specied degree sequence almost surely contains a constant fraction of the graph's vertices. This problem has been studied earlier by Pittel, Spencer and Wormald [10] for the special case of a random graph drawn from G n;m The existence of a giant k-core in a random graph is related to the probability that the genealogy tree of a certain branching process contains a perfect innite (k 1)-ary tree. We provide solutions to both problems in terms of probability generating functions. Our results apply to random graphs with degree sequences that are smooth and sparse (terms that are de ned in the paper), and for which the maximum nonzero degree is o(n 1=3), where n is the number of vertices in the graph. We apply our main theorem to derive the following results