Computing the Edge-Neighbour-Scattering Number of Graphs

A set of edges X is subverted from a graph G by removing the closed neighbourhood N[X] from G. We denote the survival subgraph by G/X. An edge-subversion strategy X is called an edge-cut strategy of G if G/X is disconnected, a single vertex, or empty. The edge-neighbour-scattering number of a graph G is defined as ENS(G) = max{w(G/X) – |X| : X is an edge-cut strategy of G}, where w (G/X) is the number of components of G/X. This parameter can be used to measure the vulnerability of networks when some edges are failed, especially spy networks and virus-infected networks. In this paper, we prove that the problem of computing the edge-neighbour-scattering number of a graph is NP-complete and give some upper and lower bounds for this parameter.