Mixed connectivity properties of random graphs and some special graphs

For positive integers k and \(\lambda \), a graph G is \((k,\lambda )\)-connected if it satisfies the following two conditions: (1) \(|V(G)|\ge k+1\), and (2) for any subset \(S\subseteq V(G)\) and any subset \(L\subseteq E(G)\) with \(\lambda |S|+|L|<k\lambda \), \(G-(S\cup L)\) is connected. For positive integers k and \(\ell \), a graph G with \(|V(G)|\ge k+\ell +1\) is said to be \((k,\ell )\)-mixed-connected if for any subset \(S\subseteq V(G)\) and any subset \(L\subseteq E(G)\) with \(|S|\le k, |L|\le \ell \) and \(|S|+|L|<k+\ell \), \(G-(S\cup L)\) is connected. In this paper, we investigate the \((k,\lambda )\)-connectivity and \((k,\ell )\)-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 \(\tilde{G} = \left( {{G_t}} \right) _0^N \), \(N=\left( {\begin{array}{c}n\\ 2\end{array}}\right) \), 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+\ell \) and of \(G_t\) being \((k,\ell )\)-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,\lambda )\)-connectivity and \((k,\ell )\)-mixed-connectivity of the complete graphs and complete bipartite graphs, and characterize the minimally \((k,\ell )\)-mixed-connected graphs.