Computing the Scattering Number of Graphs

Author: Zhang Shenggui   Li Xueling   Han Xinglou  

Publisher: Taylor & Francis Ltd

ISSN: 0020-7160

Source: International Journal of Computer Mathematics, Vol.79, Iss.2, 2002-01, pp. : 179-187

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The scattering number of a noncomplete connected graph G is defined by s(G)= max{ω(GX)−∣X∣: XV(G), ω(GX)≥2}, where ω(GX) denotes the number of components of GX. 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.