Skip to main content
Presentation
l-Connectivity and l-Edge-Connectivity of Random Graphs
Midwestern Conference on Combinatorics and Combinatorial Computing (MCCCC)
  • Ran Gu, Hohai University
  • Xiaofeng Gu, University of West Georgia
  • Yongtang Shi, Nankai University
  • Hua Wang, Georgia Southern University
Document Type
Presentation
Presentation Date
10-14-2016
Abstract or Description

For an integer l ≥ 2, the l-connectivity κl(G) of a graph G is defined to be the minimum number of vertices of G whose removal produces a disconnected graph with at least l components or a graph with fewer than l vertices. The l-edge-connectivity λl(G) of a graph G is the minimum number of edges whose removal leaves a graph with at least l components if |V (G)| ≥ l, and λl(G) = |E(G)| if |V (G)| < l. In this paper, we establish sharp threshold functions for the l-connectivity and l-edge-connectivity of random graphs, which generalize the result of Erdos and Renyi, and Stepanov. In fact, further strengthening our results, we show that in the random graph process, with high probability the hitting times of minimum degree at least k and of l-connectivity (or l-edge-connectivity) at least k(l − 1) coincide. This can be seen as a generalization of the results of Bollobas and Thomassen.

Location
Normal, IL
Citation Information
Ran Gu, Xiaofeng Gu, Yongtang Shi and Hua Wang. "l-Connectivity and l-Edge-Connectivity of Random Graphs" Midwestern Conference on Combinatorics and Combinatorial Computing (MCCCC) (2016)
Available at: http://works.bepress.com/hua_wang/132/