The Vulnerability of Complete Graphs to Localised Attacks

Classical measures of graph robustness are typically based on global vertex removal. However, such measures do not capture the effects of lo-calised failures, where damage is restricted to a neighbourhood of vertices. In this paper, we introduce a model of localised attacks on graphs defined by the removal of metric balls B(u, r), together with a notion of vulnera-bility based on the resulting loss of vertices and connectivity. Using this framework, we study the vulnerability of complete graphs and show that,despite their classical robustness, they are maximally vulnerable underlocalised attacks.