Vulnerability of nearest neighbor graphs

We study several measures of vulnerability of nearest neighbor graphs. We obtain estimates on the toughness, the tenacity, the scattering number, and the rupture degree of nearest neighbor graphs. The method is to recursively apply a certain separator theorem an appropriate number of times, depending on the particular measure studied. We also apply these methods to obtain estimates of these measures for several other classes of graphs.