Super Connectivity of Erdős–Rényi Graphs

The super connectivity k'(G) of a graph G is the minimum cardinality of vertices, if any, whose deletion results in a disconnected graph that contains no isolated vertex. G is said to be r-super connected if k'(G) ≥ r. In this note, we establish some asymptotic almost sure results on r-super connectedness for classical Erdős–Rényi random graphs as the number of nodes tends to infinity. The known results for r-connectedness are extended to r-super connectedness by pairing off vertices and estimating the probability of disconnecting the graph that one gets by identifying the two vertices of each pair.