Vertex-Neighbor-Scattering Number of Bipartite Graphs

Let G be a connected graph. A set of vertices S V (G) is called subverted from G if each of the vertices in S and the neighbor of S in G are deleted from G. By G/S we denote the survival subgraph that remains after S is subverted from G. A vertex set S is called a cut-strategy of G if G/S is disconnected, a clique, or Ø. The vertex-neighbor-scattering number of G is defined by VNS(G) = {equation presented} , where S is any cut-strategy of G, and ω (G/S) is the number of components of G/S. It is known that this parameter can be used to measure the vulnerability of spy networks and the computing problem of the parameter is NP-complete. In this paper, we discuss the vertex-neighbor-scattering number of bipartite graphs. The NP-completeness of the computing problem of this parameter is proven, and some upper and lower bounds of the parameter are also given.