Gambrell, Marci J. Vertex-neighbor-integrity of magnifiers, expanders, and hypercubes. (English) Zbl 0957.05067 Discrete Math. 216, No. 1-3, 257-266 (2000). 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 M. B. Cozzens and 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\). M. B. Cozzens and 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. Reviewer: R.C.Entringer (Albuquerque) Cited in 1 ReviewCited in 1 Document MSC: 05C40 Connectivity 05C35 Extremal problems in graph theory 68Q25 Analysis of algorithms and problem complexity Keywords:magnifiers; expanders; vertex-neighbor-integrity; hypercubes Citations:Zbl 0881.05064 PDFBibTeX XMLCite \textit{M. J. Gambrell}, Discrete Math. 216, No. 1--3, 257--266 (2000; Zbl 0957.05067) Full Text: DOI