Mixed connectivity properties of random graphs and some special graphs

For positive integers k and λ, a graph G is (k, λ) -connected if it satisfies the following two conditions: (1) | V(G) | ≥ k+ 1 , and (2) for any subset S⊆ V(G) and any subset L⊆ E(G) with λ| S| + | L| < kλ, G- (S∪ L) is connected. For positive integers k and ℓ, a graph G with | V(G) | ≥ k+ ℓ+ 1 is said to be (k, ℓ) -mixed-connected if for any subset S⊆ V(G) and any subset L⊆ E(G) with | S| ≤ k, | L| ≤ ℓ and | S| + | L| < k+ ℓ, G- (S∪ L) is connected. In this paper, we investigate the (k, λ) -connectivity and (k, ℓ) -mixed-connectivity of random graphs, and generalize the results of Erdős and Rényi (Publ Math Debrecen 6:290–297, 1959) and Stepanov (Theory Probab Appl 15:55–67, 1970). Furthermore, our argument show that in the random graph process G~=(Gt)0N, N=(n2), the hitting times of minimum degree at least kλ and of G_t being (k, λ) -connected coincide with high probability, and also the hitting times of minimum degree at least k+ ℓ and of G_t being (k, ℓ) -mixed-connected coincide with high probability. These results are analogous to the work of Bollobás and Thomassen (Ann Discrete Math 28:35–38, 1986a; Combinatorica 7:35–38, 1986b) on classic connectivity. Additionally, we obtain the (k, λ) -connectivity and (k, ℓ) -mixed-connectivity of the complete graphs and complete bipartite graphs, and characterize the minimally (k, ℓ) -mixed-connected graphs.