Expansion properties of a random regular graph after random vertex deletions

Details Expansion properties of a random regular graph after random vertex deletions Expansion properties of a random regular graph after random vertex deletions

2007-01-29

arxiv.org/abs/math/0701863v1

Mathematics

Combinatorics

14 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Expansion properties of a random regular graph after random vertex deletions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Expansion properties of a random regular graph after random vertex deletions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expansion properties of a random regular graph after random vertex deletions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-470428