Skip to main content
Presentation
Random Graphs and L-Connectivities
Spring Southeastern Sectional Meeting of the American Mathematical Society (AMS)
  • Ran Gu, Hohai University
  • Xiaofeng Gu, University of West Georgia
  • Yongtang Shi, Nankai University
  • Hua Wang, Georgia Southern University
Document Type
Presentation
Presentation Date
3-11-2017
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 ` 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
Charleston, SC
Citation Information
Ran Gu, Xiaofeng Gu, Yongtang Shi and Hua Wang. "Random Graphs and L-Connectivities" Spring Southeastern Sectional Meeting of the American Mathematical Society (AMS) (2017)
Available at: http://works.bepress.com/hua_wang/133/