Vertex-Neighbor-Scattering Number of Bipartite Graphs

Let G be a connected graph. A set of vertices $\text{S }\subseteq \text{ 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 $\text{VNS(G) = }\underset{\text{S}\subseteq \text{V(G)}}{\text{max}}\text{{}\omega \text{(G/S)}\text{-}\mathrm{|S|}\text{}}$, 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.