Hostname: page-component-848d4c4894-4hhp2 Total loading time: 0 Render date: 2024-06-05T00:17:22.540Z Has data issue: false hasContentIssue false
  • English
  • Français

Dismantling Sparse Random Graphs

Published online by Cambridge University Press:  01 March 2008

SVANTE JANSON  and
ANDREW THOMASON
SVANTE JANSON
Affiliation:
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/)
ANDREW THOMASON
Affiliation:
DPMMS, Centre for Mathematical Sciences, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: a.g.thomason@dpmms.cam.ac.uk)
Get access Rights & Permissions [Opens in a new window]

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).

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 2 , March 2008 , pp. 259 - 264
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bau, S., Wormald, N. C. and Zhou, S. (2002) Decycling numbers of random regular graphs. Random Struct. Alg. 21 397–413.CrossRefGoogle Scholar
[2]Bollobás, B. (2001) Random Graphs, 2nd edn, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
[3]Bollobás, B., Janson, S. and Riordan, O. (2007) The phase transition in inhomogeneous random graphs. Random Struct. Alg. 31 3–122.CrossRefGoogle Scholar
[4]Britton, T., Janson, S. and Martin-Löf, A. (2007) Graphs with specified degree distributions, simple epidemics and local vaccination strategies. Preprint: arXiv:math/0702021v1Google Scholar
[5]Edwards, K. and Farr, G. (2001) Fragmentability of graphs. J. Combin. Theory Ser. B 82 30–37.CrossRefGoogle Scholar
[6]Edwards, K. and Farr, G. (2003) Research problems from the 18th British Combinatorial Conference. Discrete Math. 266 441–451.Google Scholar
[7]Edwards, K. and Farr, G. (2007) Planarization and fragmentability of some classes of graphs. Discrete Math., to appear.Google Scholar
[8]Edwards, K. and McDiarmid, C. (1994) New upper bounds on harmonious colorings. J. Graph Theory 18 257–267.CrossRefGoogle Scholar
[9]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 17–61.Google Scholar
[10]Frieze, A. M. (1990) On the independence number of random graphs. Discrete Math. 81 171–175.Google Scholar
[11]Frieze, A. M. and Łuczak, T. (1992) On the independence and chromatic numbers of random regular graphs. J. Combin. Theory Ser. B 54 123–132.CrossRefGoogle Scholar
[12]Garmanik, D., Nowicki, T. and Swirszcz, G. (2006) Maximum weight independent sets and matchings in sparse random graphs: Exact results using the local weak convergence method. Random Struct. Alg. 28 76–106.CrossRefGoogle Scholar
[13]Haxell, P., Pikhurko, O. and Thomason, A. Maximum acyclic and fragmented sets in regular graphs. J. Graph Theory, to appear.Google Scholar
[14]Hoppen, C. and Wormald, N. C. (2007) Induced forests in regular graphs with large girth. Preprint: arXiv:0709.3126v1Google Scholar
[15]Janson, S. and Luczak, M. (2007) A simple solution to the k-core problem. Random Struct. Alg. 30 50–62.CrossRefGoogle Scholar
[16]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley, New York.CrossRefGoogle Scholar
[17]Karp, R. M. (1972) Reducibility among combinatorial problems. In Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, 1972), Plenum, New York, pp. 85–103.Google Scholar
[18]Lipton, R. J. and Tarjan, R. E. (1979) A separator theorem for planar graphs. SIAM J. Appl. Math. 36 177–189.Google Scholar
[19]Luczak, M. and McDiarmid, C. (2001) Bisecting sparse random graphs. Random Struct. Alg. 18 31–38.3.0.CO;2-1>CrossRefGoogle Scholar
[20]McDiarmid, C. (2002) Concentration for independent permutations. Combin. Prob. Comput. 11 163–178.Google Scholar
[21]Talagrand, M. (1995) Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73–205.Google Scholar