Super Connectivity of Erd?s-Rényi Graphs

Yilun Shang
Additional contact information
Yilun Shang: Department of Computer and Information Sciences, Faculty of Engineering and Environment, Northumbria University, Newcastle NE1 8ST, UK

Mathematics, 2019, vol. 7, issue 3, 1-5

Abstract: 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.

Keywords: super connectivity; random graph; interconnection network (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/3/267/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/3/267/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:3:p:267-:d:214257

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().