Mixed Connectivity of Random Graphs

For positive integers k and lambda, a graph G is (k, lambda)-connected if it satisfies the following two conditions: (1) vertical bar V (G)vertical bar >= k+ 1, and (2) for any subset S subset of V (G) and any subset L subset of E(G) with lambda vertical bar S vertical bar + vertical bar L vertical bar < k lambda, G - (S boolean OR L) is connected. For positive integers k and l, a graph G with vertical bar V (G)vertical bar >= k + l + 1 is said to be (k, l)-mixed-connected if for any subset S subset of V (G) and any subset L subset of E(G) with vertical bar S vertical bar <= k, vertical bar L vertical bar <= l and vertical bar S vertical bar+vertical bar L vertical bar < k+l, G-(S boolean OR L) is connected. In this paper, we investigate the (k, lambda)-connectivity and (k, l)-mixed-connectivity of random graphs, and generalize the results of Erdos and Renyi (1959), and Stepanov (1970). Furthermore, our argument can show that in the random graph process G = (G(t))(0)(N), N = [GRAPHICS] , the hitting times of minimum degree at least k lambda and of G(t) being (k, lambda)-connected coincide with high probability, and also the hitting times of minimum degree at least k + l and of G(t) being (k, l)-mixed-connected coincide with high probability. These results are analogous to the work of Bollobas and Thomassen (1986) on classic connectivity.