CONNECTIVITY PROPERTIES IN RANDOM REGULAR GRAPHS WITH EDGE FAULTS
Sotiris Nikoletseas, Krishna V. Palem, Paul G. Spirakis, Moti M. Yung · International Journal of Foundations of Computer Science · 2000
We introduce a new model of random graphs, that of random regular graphs with edge faults (which we denote by [Formula: see text]), obtained by selecting the edges of a random member of the set of all regular graphs of degree r independently and with probability p. We can thus represent a communication network in which the links fail independently and with probability f =1-p. In order to deal with this new model, we extend the notion of configurations and the translation lemma between configurations and random regular graphs provided by B. Bollobás, by introducing the concept of random configurations, to account for edge faults, and by providing an extended translation lemma between random configurations and [Formula: see text] graphs. We investigate important connectivity properties of [Formula: see text] by estimating the ranges of r, f for which, with high probability, [Formula: see text] graphs a) are highly connected b) become disconnected and c) admit a giant connected component of small diameter.