K-Connectivity in Random Undirected Graphs

摘要

This paper concerns vertex connectivity in random graphs. We present results bounding the cardinality of the biggest k-block in random graphs of the G sub n,p model, for any constant value of k. These results generalize those of (Erdos, Renyi, 60) and (Karp, Tarjan, 80) for k = 1 and 2. We furthermore prove here that the cardinality of the biggest k-block is > or = n-logn with probability > or = 1/n-squared for p > or = c1(k)/n and c1(k) > k + 2. We also show that if p > or = c(k)(logn)/n with c(k) > 32 k-squared then the graph G sub n,p is k-connected with probability > or = 1-2n to the -d'(k) power, d'(k) > 1.