Expansion properties of a random regular graph after random vertex deletions

Catherine Greenhill, Fred B. Holt, Nicholas Wormald

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^{-a…