## Abstract

For an integer (Formula presented.), the (Formula presented.) -connectivity (Formula presented.) of a graph (Formula presented.) is defined to be the minimum number of vertices of (Formula presented.) whose removal produces a disconnected graph with at least (Formula presented.) components or a graph with fewer than (Formula presented.) vertices. The (Formula presented.) -edge-connectivity (Formula presented.) of a graph (Formula presented.) is the minimum number of edges whose removal leaves a graph with at least (Formula presented.) components if (Formula presented.), and (Formula presented.) if (Formula presented.). Given integers (Formula presented.) and (Formula presented.), we investigate (Formula presented.) and (Formula presented.) when (Formula presented.). Furthermore, our arguments can be used to show that in the random graph process, the hitting times of minimum degree at least (Formula presented.) and of (Formula presented.) -connectivity (or (Formula presented.) -edge-connectivity) at least (Formula presented.) coincide with high probability. These results generalize the work of Bollobás and Thomason on classical connectivity.

Original language | English |
---|---|

Pages (from-to) | 5-28 |

Number of pages | 24 |

Journal | Journal of Graph Theory |

Volume | 101 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2022 |

## Keywords

- hitting time
- random graph
- threshold function
- ℓ-connectivity
- ℓ-edge-connectivity