Vertex-Neighbor-Integrity of Powers of Cycles

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(VNI(G)\), is defined as:

\(VNI(G) = \min_{|S|} {|S| + w(G/S)}\)

where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we evaluate the vertex-neighbor-integrity of the powers of cycles, and show that among the powers of the \(n\)-cycle, the maximum vertex-neighbor-integrity is \(\left\lceil{2}\sqrt{n}\right\rceil – 3\) and the minimum vertex-neighbor-integrity is \(\left\lceil\frac{n}{2\left\lfloor\frac{n}{2}\right\rfloor} + 1\right\rceil\).