Vertex-neighbor-integrity of magnifiers, expanders, and hypercubes (Q1567283)

A set of vertices is subverted from a graph \(G\) by removing the closed neighborhood \(N(S)\) from \(G\). The subgraph remaining is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), introduced by \textit{M. B. Cozzens} and \textit{S.-S. Y. Wu} [Ars Comb. 43, 169-180 (1996; Zbl 0881.05064)], is defined by \(\text{VNI}(G)= \min_{S\subseteq V(G)}\{|S|+ \omega(G/S)\}\) where \(\omega(H)\) is the order of a largest component of \(H\). \textit{M. B. Cozzens} and \textit{S.-S. Y. Wu} [Ars Comb. 48, 257-270 (1998)] showed that the VNI of paths and powers of cycles of order \(n\) is generally not more than \(2\sqrt n\). In contrast, the author shows that the VNI of a certain family of magnifier graphs is of order \(\alpha|V(G)|\) where \(\alpha\) depends on the parameters of the family but conjectures that \(\text{VNI}(G)= \lceil n/3\rceil\) for every connected graph \(G\) of order \(n\). After bounding the VNI of hypercubes the author shows that the decision problem related to finding the VNI of a graph is NP-complete.