On the Local Resilience of Random Regular Graphs
Sonny Ben-Shimon, Michael Krivelevich, Benny Sudakov · arXiv (Cornell University) · 2009
For a graph property , the global resilience of a graph G with respect to is the minimal number of additions and removals of edges from G such that the resulting graph does not possess . For some graph properties this quantity does not seem to convey what one would expect from such a notion of “distance”. Consider now the local resilience of a graph G with respect to , where there is an additional constraint of a bounded number of editions done on edges incident to a single vertex. This notion, which was implicitly studied for some ad-hoc properties, was recently treated in a more systematic way in a recent paper by Sudakov and Vu. Most research conducted with respect to this distance notion was focused on the random graph model and some families of pseudo-random graphs with respect to several graph properties such as containing a perfect matching, containing long cycles (i.e. linear in the number of vertices), and being Hamiltonian to name a few. In this talk we continue to explore the local resilience notion, but turn our attention to random and pseudo-random regular graphs of constant degree. In particular we focus on the local resilience with respect to edge and vertex connectivity, containing a perfect matching, and being Hamiltonian.