Color-avoiding percolation in edge-colored Erd\H{o}s-R\'enyi graphs

arXiv2208.12727MaRDI QIDQ6408939FDOQ6408939

Authors: Balázs Ráth, Kitti Varga, Panna Tímea Fekete, Roland Molontay 

Publication date: 26 August 2022

Abstract: We study a variant of the color-avoiding percolation model introduced by Krause et al., namely we investigate the color-avoiding bond percolation setup on (not necessarily properly) edge-colored ErdH{o}s-R'{e}nyi random graphs. We say that two vertices are color-avoiding connected in an edge-colored graph if after the removal of the edges of any color, they are in the same component in the remaining graph. The color-avoiding connected components of an edge-colored graph are maximal sets of vertices such that any two of them are color-avoiding connected. We consider the fraction of vertices contained in color-avoiding connected components of a given size as well as the fraction of vertices contained in the giant color-avoiding connected component. Under some mild assumptions on the color-densities, we prove that these quantities converge and the limits can be expressed in terms of probabilities associated to edge-colored branching process trees. We provide explicit formulas for the limit of the normalized size of the giant color-avoiding component, and in the two-colored case we also provide explicit formulas for the limit of the fraction of vertices contained in color-avoiding connected components of a given size.

This page was built for publication: Color-avoiding percolation in edge-colored Erd\H{o}s-R\'enyi graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408939)