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.