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 de- fined 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 \emptyset. The neighbor-scattering number of G, S(G), is defined as S(G) = max{w(G/X) - |X|: X is a cut-stragey of G w(G/X) \ge 1}, where w(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.
Citation:
Fengwei Li, Xueliang Li, "Computational complexity and bounds for neighbor-scattering number of graphs," ispan, pp.478-483, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005