Super Connectivity of Erdős–Rényi Graphs

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
20 Downloads (Pure)


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.
Original languageEnglish
Article number267
Number of pages5
Issue number3
Publication statusPublished - 15 Mar 2019


Dive into the research topics of 'Super Connectivity of Erdős–Rényi Graphs'. Together they form a unique fingerprint.

Cite this