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 |
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 |
Downloads
Downloads per month over past year
