Concentration of rainbow k-connectivity of a multiplex random graph

Yilun Shang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

Abstract

We consider a multiplex random graph G(n,m, p) with m independent color layers over a common vertex set V of order n. In each layer, the edges are independent following the Erd˝os-R´enyi model with edge probability p = c(ln n+ (k-1) ln ln n)/mn for some constant c > 1. A rainbow path in this context means a path with all edges from distinct layers. For a graph G G(n,m, p), let rck(G) be its rainbow k-connectivity, namely the smallest required number of layers so that any pair of vertices in G can be connected by k internally vertex disjoint rainbow paths. We show that with high probability, rck(G(n,m, p)) is concentrated on three consecutive numbers. These numbers are at distance Θ(ln n/(ln(ln n + (k-1)lnlnn))2) to the diameter of the graph.
Original languageEnglish
Article number113771
Pages (from-to)1-11
Number of pages11
JournalTheoretical Computer Science
Volume951
Early online date10 Feb 2023
DOIs
Publication statusPublished - 24 Mar 2023

Fingerprint

Dive into the research topics of 'Concentration of rainbow k-connectivity of a multiplex random graph'. Together they form a unique fingerprint.

Cite this