Expansion properties of a random regular graph after random vertex deletions

Simple item page
dc.creatorGreenhill, Catherine
dc.creatorHolt, Fred B.
dc.creatorWormald, Nicholas
dc.date2007-01-29
dc.date.accessioned2026-07-07T07:43:51Z
dc.date.available2026-07-07T07:43:51Z
dc.descriptionWe 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.
dc.description14 pages
dc.identifierhttps://arxiv.org/abs/math/0701863
dc.identifierhttp://arxiv.org/abs/math/0701863
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/122991
dc.subjectCombinatorics
dc.subjectProbability
dc.subject05C80
dc.titleExpansion properties of a random regular graph after random vertex deletions
dc.typetext

Files

Collections

arXiv