Vertex-Neighbor-Integrity of Trees

Abstract

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$, $\mathrm{V}\mathrm{N}\mathrm{I}(G)$, is defined to be $\mathrm{V}\mathrm{N}\mathrm{I}(G)={\displaystyle \underset{S\subseteq V(G)}{min}\{|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 show the minimum and the maximum vertex-neighbor-integrity among all trees with any fixed order, and also show that for any integer $l$ between the extreme values there is a tree with the vertex-neighbor-integrity $l$.