Random Graphs and L-Connectivities

For an integer l ≥ 2, the l-connectivity κl(G) of a graph G is defined to be the minimum number of vertices of G whose removal produces a disconnected graph with at least l components or a graph with fewer than l vertices. The l-edge-connectivity λl(G) of a graph G is the minimum number of edges whose removal leaves a graph with at least ` components if |V (G)| ≥ l, and λl(G) = |E(G)| if |V (G)| < l. In this paper, we establish sharp threshold functions for the l-connectivity and l-edge-connectivity of random graphs, which generalize the result of Erdos and Renyi, and Stepanov. In fact, further strengthening our results, we show that in the random graph process, with high probability the hitting times of minimum degree at least k and of l-connectivity (or l-edge-connectivity) at least k(l − 1) coincide. This can be seen as a generalization of the results of Bollobas and Thomassen.