## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 427-441 |

Number of pages | 15 |

Journal | Journal of Combinatorial Optimization |

Volume | 42 |

Issue number | 3 |

DOIs | |

State | Published - Oct 2021 |

Externally published | Yes |

## Keywords

- Connectivity
- Edge-connectivity
- Hitting time
- Mixed connectivity
- Random graph
- Threshold function

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics