Super Connectivity of Erdős-Rényi Graphs

Abstract

The super connectivity κ ′ ( 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 κ ′ ( 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.

Keywords

• super connectivity
• random graph
• interconnection network