Rainbow connectivity and rainbow index of inhomogeneous random graphs

Research output: Contribution to journalArticlepeer-review

24 Downloads (Pure)

Abstract

We investigate the rainbow k-connectivity rck and (t,k)-rainbow index rxt,k of the in homogeneous random graph G(n,p), where any two vertices i and j are joined by an edge eij with probability p(eij) independently of all other edges, and p={p(eij)}. We show that the known threshold functions for the monotone properties rck(G(n,p))≤r and rxt,k(G(n,p))≤t for integers k, r and t in the Erdős–Rényi random graph G(n,p) can be extended to ‘threshold landscapes’ in terms of G(n,p). In contrast to the traditional plain thresholds characterized as a watershed, our threshold landscapes have two surfaces that are inherently interwoven with each other. This sheds some light on the network connectivity as appropriate trade-offs are allowed and is potentially applicable in network science where connections are not always equal.
Original languageEnglish
Article number103778
JournalEuropean Journal of Combinatorics
Volume115
Early online date1 Aug 2023
DOIs
Publication statusPublished - 1 Jan 2024

Cite this