Computing the scattering number of graphs

The scattering number of a noncomplete connected graph G is defined by s(G) = max{ω(G-X)-|X|: X⊂V(G), ω(G-X)≥2}, where ω(G-X) denotes the number of components of G-X. This parameter can be used to measure the vulnerability of networks. It shows not only the difficulty to break down the network but also the damage that has been caused. In this paper, we prove that the problem of computing the scattering number of a graph is NP-complete. At the same time, the scattering numbers of grids and those of Cartesian products of two complete graphs are determined.