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

[img]
Preview
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: https://www.mdpi.com/2227-7390/7/3/267/htm

Abstract

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
URI: http://nrl.northumbria.ac.uk/id/eprint/38413

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics