Random regular graphs with edge faults: Expansion through cores (Q5941563)

Let \(G\) be a given graph (modelling a communication network) which we assume suffers from static edge faults: That is we let each edge of \(G\) be present independently with probability \(p\) (or absent with fault probability \(f=1-p)\). In particular, we are interested in robustness results for the case that the graph \(G\) itself is a random member of the class of all regular graphs with given degree \(d.\) Here we deal with expansion properties of faulty random regular graphs and show: For fixed \(d\geqslant 42\) and \(p=\kappa/d,\kappa \geqslant 20\), a random regular graph with fault probability \(f= 1-p\) contains a linear-size subgraph which is an expander almost surely. This subgraph can be found by a simple linear-time algorithm.