Combinatorics, Probability and Computing

Table of Contents - 2008 - Volume 17, Issue 02  

Paper

Dismantling Sparse Random Graphs

SVANTE JANSONa1 and ANDREW THOMASONa2

a1 Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se, http://www.math.uu.se/~svante/)

a2 DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: a.g.thomason@dpmms.cam.ac.uk)

Abstract

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)