Vertex-neighbor-integrity of composition graphs of paths

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-neighbor-integrity of G is defined to be VNI(G) = min{|X| + τ(G/X) : X ⊆ V(G)}, 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 problem of computing the vertex-neighbor-integrity of a graph is NP-complete. In this paper we evaluate the vertex-neighbor-integrity of the composition graph of two paths.