No CrossRef data available.
Article contents
Dismantling Sparse Random Graphs
Published online by Cambridge University Press: 01 March 2008
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
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).
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2007
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
You have
Access
- 17
- Cited by