Expansion properties of a random regular graph after random vertex deletions

Greenhill, Catherine; Holt, Fred B.; Wormald, Nicholas

Expansion properties of a random regular graph after random vertex deletions

Authors

Greenhill, Catherine

Holt, Fred B.

Wormald, Nicholas

Description

We investigate the following vertex percolation process. Starting with a random regular graph of constant degree, delete each vertex independently with probability p, where p=n^{-alpha} and alpha=alpha(n) is bounded away from 0. We show that a.a.s. the resulting graph has a connected component of size n-o(n) which is an expander, and all other components are trees of bounded size. Sharper results are obtained with extra conditions on alpha. These results have an application to the cost of repairing a certain peer-to-peer network after random failures of nodes.
14 pages