Super Connectivity of Erdős-Rényi Graphs

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.

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.