On connectivity and robustness of random graphs with inhomogeneity

Shang, Yilun (2022) On connectivity and robustness of random graphs with inhomogeneity. Journal of Applied Probability. pp. 1-11. ISSN 0021-9002 (In Press)

[img]
Preview
Text
connectivityrobustness.pdf - Accepted Version

Download (149kB) | Preview
Official URL: https://doi.org/10.1017/jpr.2022.32

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.

Item Type: Article
Uncontrolled Keywords: random graph, connectivity, robustness, threshold
Subjects: G100 Mathematics
Department: Faculties > Engineering and Environment > Computer and Information Sciences
Depositing User: John Coen
Date Deposited: 17 Nov 2022 09:05
Last Modified: 17 Nov 2022 09:15
URI: https://nrl.northumbria.ac.uk/id/eprint/50675

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics