Computational complexity and bounds for neighbor-scattering number of graphs

Let G=(V, E) be a graph. A vertex subversion strategy of G, X, is a set of vertices of G whose closed neighborhood is deleted from G. The survival-subgraph is defined by G/X. A vertex subversion strategy of G, X, is called a cut-strategy of G if the survival-subgraph is disconnected, or a clique, or Φ. The neighbor-scattering number of G, S(G), is defined as S(G)=max{ω(G/X)-|X|:X is a cut-strategy of G, ω(G/X)ges;1}, where ω(G/X) is the number of connected components in the graph G/X. As a new graphic parameter, neighbor-scattering number can be used to measure the vulnerability of spy networks. In this paper, we prove that the problem of computing the neighbor-scattering number of a graph is NP-complete and discuss the upper and lower bounds for the neighbor-scattering number via some other well-known graphic parameters. Finally, we give formulas for the neighbor-scattering numbers of the join and union of two disjoint graphs.