a2 DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: firstname.lastname@example.org)
We consider the number of vertices that must be removed from a graph G in order that the remaining subgraph have no component with more than k vertices. Our principal observation is that, if G is a sparse random graph or a random regular graph on n vertices with n → ∞, then the number in question is essentially the same for all values of k that satisfy both k → ∞ and k =o(n).
(Received September 16 2007)
(Revised October 01 2007)