Super Connectivity of Erdős–Rényi Graphs

Shang, Yilun (2019) Super Connectivity of Erdős–Rényi Graphs. Mathematics, 7 (3). ISSN 2227-7390

Text (Full text)
Shang - Super Connectivity of Erdős–Rényi Graphs OA.pdf - Published Version
Available under License Creative Commons Attribution 4.0.

Download (697kB) | Preview
Official URL:


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.

Item Type: Article
Uncontrolled Keywords: super connectivity, random graph, interconnection network
Subjects: G100 Mathematics
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: Paul Burns
Date Deposited: 15 Mar 2019 11:53
Last Modified: 01 Aug 2021 12:37

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics