Dismantling sparse random graphs
2008 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, Vol. 17, no 02, 259-264 p.Article in journal (Refereed) Published
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 -> infinity, then the number in question is essentially the same for all values of k that satisfy both k -> infinity and k = o(n).
Place, publisher, year, edition, pages
2008. Vol. 17, no 02, 259-264 p.
IdentifiersURN: urn:nbn:se:uu:diva-106271DOI: 10.1017/S0963548307008802ISI: 000254483900005OAI: oai:DiVA.org:uu-106271DiVA: diva2:224367