Portal de Periódicos da CAPES

Local resilience of graphs

2008; Wiley; Volume: 33; Issue: 4 Linguagem: Inglês

10.1002/rsa.20235

1098-2418

Benny Sudakov, Van H. Vu,

Graph theory and applications

Abstract In this article, we initiate a systematic study of graph resilience. The (local) resilience of a graph G with respect to a property $\cal {P}$ measures how much one has to change G (locally) to destroy $\cal {P}$ . Estimating the resilience leads to many new and challenging problems. Here we focus on random and pseudorandom graphs and prove several sharp results. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008