Vertex-Neighbor-Integrity of Composition Graphs of Paths

Abstract

A vertex subversion strategy of a graph $G$ is a set of vertices $X\subseteq 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|+r(G/X):X\subseteq V(G)\},$ where $r(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.