Vertex-neighbor-integrity of composition graph P_m[G]
Meijuan Zhai · Basic Sciences Journal of Textile Universities · 2007
A vertex subversion strategy of a graph G is a set of vertices X(?)V (G) whose closed neighborhood is deleted from G.The survival subgraph is denoted by G/X.The vertex-neigh- bor-integrity of G is defined to be VNI(G)=(?){|X|+τ(G/X)} ,whereτ(G/X) is the order of a largest component in G/X.This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks.It was proved by Gambrell that the decision prob- lem of computing the vertex-neighbor-integrity of a graph is NP-complete.In this paper,the vertex-neighbor-integrity of the composition graphs of a path and any graph is evaluated.