ALCOMFT-TR-01-63

Sotiris Nikoletseas, Krishna Palem, Paul Spirakis and Moti Yung
Connectivity Properties in Random Regular Graphs with Edge Faults
Patras. Work packages 2 and 4. May 2001.

Abstract: We introduce a new model of random graphs, that of random regular graphs with edge faults (which we denote by G_n,p^r), 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\'as, by introducing the concept of random configurations, to account for edge faults, and by providing an extended translation lemma between random configurations and G_n,p^r graphs.

We investigate important connectivity properties of G_n,p^r by estimating the ranges of r, f for which, with high probability, G_n,p^r graphs a) are highly connected b) become disconnected and c) admit a giant connected component of small diameter.

Postscript file: ALCOMFT-TR-01-63.ps.gz (110 kb).