Vertex-neighbor-integrity of powers of cycles (Q2715960)

Let \(G\) be a graph. Consider a set \(S\) of vertices of \(G\). Delete the closed neighborhood of \(S\) from \(G\) and consider the sum of the size of \(S\) and the size of the largest connected component of the resulting graph. The minimum of these sums (as \(S\) ranges over all subsets of the vertex set of \(G\)) is called the vertex-neighbor-integrity of \(G\). The authors evaluate the vertex-neighborhood-integrity of powers of cycles, and they show that among the powers of the \(n\)-cycle, the maximum vertex-neighbor-integrity is \(\lceil 2\sqrt {n}\rceil -3\) and the minimum vertex-neighbor-integrity is \(\lceil n/(2\lfloor n/2\rfloor +1)\rceil \).