On connectivity and robustness of random graphs with inhomogeneity

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

Abstract

The study of threshold functions has a long history in random graph theory. It is known that the thresholds for minimum degree k, k-connectivity, as well as k-robustness coincide for a binomial random graph. In this paper we consider an inhomogeneous random graph model, which is obtained by including each possible edge independently with an individual probability. Based on an intuitive concept of neighborhood density, we show two sufficient conditions guaranteeing k-connectivity and k-robustness, respectively, which are asymptotically equivalent. Our framework sheds some light on extending uniform threshold values in homogeneous random graphs to threshold landscapes in inhomogeneous random graphs.
Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalJournal of Applied Probability
Early online date5 Sep 2022
DOIs
Publication statusE-pub ahead of print - 5 Sep 2022

Fingerprint

Dive into the research topics of 'On connectivity and robustness of random graphs with inhomogeneity'. Together they form a unique fingerprint.

Cite this