×

Vertex-neighbor-integrity of magnifiers, expanders, and hypercubes. (English) Zbl 0957.05067

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.

MSC:

05C40 Connectivity
05C35 Extremal problems in graph theory
68Q25 Analysis of algorithms and problem complexity

Citations:

Zbl 0881.05064
PDFBibTeX XMLCite
Full Text: DOI