Let \(G=(V,E)\) be a graph. For a vertex \(u\) of \(V(G)\), its closed neighborhood, \(N[S]\), is defined as \(N[u]=\{u\}\cup\{v|v\in V(G), v\neq u, u\) and \(v\) are adjacent in \(G \}\). A vertex subset \(S\) of \(V(G)\) is called a subversion strategy of \(G\) if each of the vertices in \(N[S]\) is deleted from \(G\). By \(G/S\) we denote the survival subgraph \(G-N[S]\). A subversion strategy \(S\) is called a cut strategy of \(G\) if \(G/S\) is disconnected, or is a clique, or is empty. In this paper, we revise the definition of neighbor-isolated scattering number, which was introduced by Aslan, as \(NIS(G)=\max\{i(G/S)-|S|\}\), where \(S\) represents a cut strategy of \(G\) such that every component of \(G/S\) is an isolated vertex or a clique, and \(i(G/S)\) represents the number of the components of \(G/S\). We discuss the relationship between this parameter and the structure of graphs. Some tight bounds and extremal graphs with given order and neighbor-isolated scattering number are determined.
We use Bondy and Murty [2] for terminology and notation not defined here and consider only finite simple graphs.
In 1978, Gunther and Hartnell [5] introduced the idea of modeling a spy network by a graph whose vertices represent the stations and whose edges represent lines of communication. If a station is destroyed, the adjacent stations will become useless to network as a whole. Therefore, considering the question of not only removing some vertices but also of removing all of their adjacent vertices, Cozzens and Wu introduced vertex-neighbor connectivity [8] and vertex-neighbor integrity [4] to measure the invulnerability of a spy network. In recent years, Wei et al. [7] introduced vertex-neighbor scattering number VNS and vertex-neighbor toughness VNT. These parameters consider not only the amount of work done to damage the network but also how badly the network is damaged.
Let \(G=(V,E)\) be a graph and \(S\subset V(G)\). The open neighborhood of \(S\), \(N(S)\), is defined as \(\{u|uv\in E(G),v\in S\) and \(u\not\in S\}\), and the closed neighborhood of \(S\), \(N[S]\), is \(N(S)\bigcup S\). A vertex \(v\) of \(G\) is said to be subverted when \(N[v]\) is deleted from \(G\). A vertex set \(S\) is called a subversion strategy of \(G\) if each of the vertex in \(S\) has been subverted from \(G\). The survival subgraph is denoted by \(G/S\). We call \(S\) a cut strategy of \(G\) if \(G/S\) is disconnected, or is a clique, or is \(\phi\). The vertex neighbor connectivity of \(G\) \((VNC)\), \(K(G)\), is the minimal number of vertices whose subversion results in a disconnected graph or results in the trivial graph \(K_{1}\). A graph \(G\) is called \(k\)-vertex neighbor connected if \(K(G)\geq k\).
Let \(G\) be a connected noncomplete graph. The vertex-neighbor scattering number of \(G\) is defined \(VNS(G)=\max\{\omega(G/S)-|S|: \omega(G/S)\geq1\}\), where the maximal is taken over all \(S\), the cut-strategy of \(G\), and \(\omega(G/S)\) is the number of components of \(G/S\). A cut-strategy of \(G\), \(S^*\), is called a \(VNS-\)set of \(G\) if \(VNS(G)=\omega(G/S^*)-|S^*|\).
In 2015, Aslan declared that his work refine the concept of VNS [1]. He defined a new parameter, called neighbor-isolated scattering number, as \(NIS(G)=max\{i(G/S)-|S|: i(G/S)\geq 1\)}, where the maximal is taken over all \(S\), the cut strategy of \(G\), and \(i(G/S)\) is the number of components which are isolated vertices of \(G/S\). In fact, it is only a slight modify of VNS. This parameter does not count the whole components of \(G/S\), nor does it require each component of \(G/S\) must be a clique. Therefore, it lacks rationality, let alone refinement.
Let \(G\) be a connected non-complete graph. The neighbor-isolated scattering numberNIS of \(G\) should be defined \(NIS(G)=max\{i(G/S)-|S|: i(G/S)\geq 1\)}, where \(S\) is a cut strategy of \(G\) such that every component of \(G/S\) is a clique, and \(i(G/S)\) is the component number of \(G/S\). If \(i(G/S^{*})-|S^{*}|=NIS(G)\), then \(S^{*}\) is a neighbor-isolated scattering set, denoted \(NIS\)-set.
It is well known that the role of a clique in a neighbor situation is equivalent to a vertex in a non-neighbor situation. In this definition, a \(NIS\)-set represents one of the most thorough damage strategy for a network in neighbor sense. That is, there are no other types of component except cliques(include isolated vertices) in the survival subgraph.
The rationality of our definition can also be illustrated by the following example. In Figure 1, \(NIS(G_1)=2, NIS(G_2)=1\). This shows that NIS can distinguish their structural differences. However, the parameter defined by Aslan cannot do this.
In this paper, based on an investigation of the relationship between \(NIS\) and other invulnerability parameters, some maximal and minimal \(0\)-neighbor-isolate scattered graphs with prospected order and \(NIS\) are given. We use \(\lfloor x\rfloor\) for the largest integer not greater than \(x\) and \(\lceil x\rceil\) for the smallest integer not smaller than \(x\), and consider only simple undirected graphs.
In this section, we discuss the relationship between \(NIS\) and the structure of graphs by lower and upper bounds of \(NIS\).
By the definitions, a vulnerable graph has high \(VNS\) or \(NIS\), and vice versa. A complete graph is very vulnerable to attack, since subverting any one vertex will betray the entire graph. So, define \(VNS(K_n)=1\) and \(NIS(K_n)=1\). It is easy to know that \(NIS(G)\leq VNS(G)\) for any graph \(G\). At the same time, there are many graphs such that \(NIS<VNS\). For example, the VNS of the wheel graph \(W_{1,11}\)(see [5]) is 2, but its NIS is 1. More similar examples can be found in paths and cycles, such as \(P_8, C_{11}, C_{12}\), etc.
Theorem 2.1. Let \(G\) be a non-complete connected graph of order \(n(\geq4)\). Then \(NIS(G)\leq n-3\), and \(NIS(G)=n-3\) if and only if \(G\) is a star.
Proof. Let \(S\) be a \(NIS\)-set of \(G\). Since \(G\) is non-complete and connected, \(|S|\geq1\) and \(i(G/S)\leq n-2\). Therefore, \(NIS(G)\leq (n-2)-1=n-3\). The second result is trivial. ◻
Definition 2.2. [6]Let \(G\) be a non-complete connected graph. The vertex-neighbor toughness of \(G\) is defined as \(t_{VN}(G)= min \{ \frac{|S|}{\omega (G/S)}\}\), where the minimal is taken over all \(S\), the cut-strategy of \(G\), \(\omega(G/S)\) stands for the number of components of \(G/S\). A cut-strategy \(S^*\) is called a \(t_{VN}\)-set of \(G\) if \(t_{VN}(G)= \frac{|S^*|}{\omega (G/S^*)}\). Specially, for the complete graph and empty graph \(G\), define \(t_{VN}(G)=0\).
Definition 2.3. [3] Let \(G\) be a non-complete connected graph. The vertex-neighbor integrity of \(G\) is defined \(VNI(G)= min \{|S|+m(G/S):S \subseteq V(G)\}\), where the minimal is taken over all subversion strategy of \(G\), and \(m(G/S)\) stands for the order of a maximal component of \(G/S\). A subversion strategy \(S^{*}\) is said to be a \(VNI\)-set of \(G\), if \(VNI(G)=|S^{*}|+m(G/S^{*})\).
Theorem 2.4. Let \(G\) be a non-complete connected graph of order \(n\), \(NIS(G)=s, t_{VN}(G)=t(\leq 1)\). Then \(s\leq \frac {(n-1)(1-t)}{1+t}\).
Proof. Let \(S\) be a \(NIS\)-set of \(G\). Then \(S\) is a cut strategy of \(G\), and \(\omega (G/S)+|S|\leq n-1\). By the definition of vertex-neighbor toughness, \(|S|\geq t\omega(G/S)\). So, we have \(\omega(G/S)\leq \frac {n-1}{1+t}\). Therefore, \[\begin{aligned} s &=i(G/S)-|S| \leq \omega (G/S)-|S|\\ &\leq \omega (G/S)-t\omega (G/S)\\ &\leq \frac {(n-1)(1-t)}{1+t}. \end{aligned}\]
The proof is completed. ◻
Remark 2.5. The star graphs achieve the upper bound of Theorem 2.4, so it is the best possible.
Theorem 2.6. Let \(G\) be a non-complete connected graph of order \(n\), \(NIS(G)=s, VNI(G)=I\). Then \(s\leq n-I-1\).
Proof.Let \(S\) be a cut strategy of \(G\). By the definition of vertex-neighbor integrity, \(|S|+m(G/S)\geq I\). Then we have \[\begin{aligned} i(G/S) \leq \omega (G/S) &\leq n-|S|-m(G/S)\\ &=n-(|S|+m(G/S))\\ &\leq n-I. \end{aligned}\]
Furthermore, since \(|S| \geq 1\), we have \(i(G/S)-|S| \leq n-I-1\). By the definition of neighbor-isolated scattering number, we have \(NIS(G)=s \leq n-I-1\).
The proof is completed. ◻
Remark 2.7. The upper bound in Theorem 2.6 is tight. This can be shown by the star graphs.
Definition 2.8. [7]Let \(n\) be an integer at least \(3\). Construct a class of graphs with order \(n\), denoted by \(\mathscr{G}_n\), as follows.
(1) If \({\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil\), decompose \(n=n_1+n_2+…+n_{\lfloor n\rfloor}\) such that \(|n_i-n_j|\leq 1\) for \(i\neq j\). Replace each vertex of the complete graph \(K_{\lfloor \sqrt{n} \rfloor}\) by a clique \(K_{n_1},K_{n_2},…,K_{n_{\lfloor \sqrt{n} \rfloor}}\), respectively, then add edges such that
(a) \(K_{n_i}~and~K_{n_j}\)(\(i\neq j\)) are joined by an edge exactly.
(b) Each vertex in \(K_{n_i}\) is incident to, at most, one edge not entirely contained in \(K_{n_i},i=1,2,…,\lfloor \sqrt{n} \rfloor\).
(2) If \({\lfloor n\rfloor \lceil n\rceil \leq n <\lceil n\rceil}^2\), decompose \(n=n_1+n_2+…+n_{\lceil n \rceil}\) such that \(|n_i-n_j|\leq 1\) for \(i\neq j\). Replace each vertex of the complete graph \(K_{\lceil \sqrt{n} \rceil}\) by a clique \(K_{n_1},K_{n_2},…,K_{n_{\lceil \sqrt{n} \rceil}}\), respectively, then add edges as in (1) (a) and (b).
For example, when \(n=13\), we decompose \(13=3+3+3+4\). A graph in \(\mathscr{G}_{13}\) is shown in Figure 2.
Theorem 2.9. Let \(G\) be a graph in \(\mathscr{G}_n\). Then \[NIS(G)= \left\{ \begin{array}{ll} 2-\lfloor \sqrt{n} \rfloor, & if {\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil;\\ 2-\lceil \sqrt{n} \rceil, & if \lfloor n\rfloor \lceil n\rceil \leq n <{\lceil n\rceil}^2. \end{array} \right.\\ \]
Proof. Similar to the proof of Theorem 8 in [5], we have \[K(G)= \left\{ \begin{array}{ll} \lfloor \sqrt{n} \rfloor-1, & if {\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil;\\ \lceil \sqrt{n} \rceil-1, & if \lfloor n\rfloor \lceil n\rceil \leq n <{\lceil n\rceil}^2, \end{array} \right.\\ \] and for any cut strategy \(S\) of \(G\), \(|S|\geq K(G)\), \(i(G/S)\leq 1\). Then \(NIS(G)\leq 1-K(G)\).
On the other hand, it is easy to find a cut strategy \(S\) in \(G\) such that \(|S|=K(G)\) and \(G/S\) is a clique. Therefore, \[NIS(G)=1-K(G)= \left\{ \begin{array}{ll} 2-\lfloor \sqrt{n} \rfloor, & if {\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil;\\ 2-\lceil \sqrt{n} \rceil, & if \lfloor n\rfloor \lceil n\rceil \leq n <{\lceil n\rceil}^2. \end{array} \right.\]
The proof is complete. ◻
Conjecture 2.10. Let \(G\) be a non-complete connected graph of order \(n\). Then \[NIS(G)\geq \left\{ \begin{array}{ll} 2-\lfloor \sqrt{n} \rfloor, & if {\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil;\\ 2-\lceil \sqrt{n} \rceil, & if \lfloor n\rfloor \lceil n\rceil \leq n <{\lceil n\rceil}^2. \end{array} \right.\]
The upper bounds of VNS are upper bounds of NIS, and the lower bounds of NIS are also the lower bounds of VNS. Theoretically, there are graphs that reach an upper bound of VNS, but their NIS are relatively small, and graphs that reach a lower bound of NIS, but their VNS is relatively large. It is interesting to construct such graphs, but it seems difficult.
In this section, we investigate some maximally \(s\)-neighbor-isolate scattered graphs, that is, given order and neighbor-isolated scattering number, construct a class of graphs with maximal number of edges.
Definition 3.1. A graph \(G\) is maximally \(s\)-neighbor-isolate scattered, if \(NIS(G)=s\) and there does not exist a super spanning graph \(H\) of \(G\) with \(NIS(H)=s\).
In other words, adding any edge to a maximally \(s\)-neighbor-isolate scattered graph, the NIS of the resulting graph will be no longer \(s\).
Let \(n, s\) be two given integers. We construct a class of graphs with order \(n(\geq 3)\), denote \(\mathscr{G}(n,s)\), such that for any graph \(G\in \mathscr{G}(n,s)\), \(NIS(G)=s\).
\((1)\) When \(s \geq 0\), the graph is \(K_{n-s-2}\vee \bar{K}_{s+2}\).
\((2)\) When \(s\leq-1\), \((i)\) divide \(n\) into \(2-s\) integers such that \(n_1=n_2=\cdots=n_{1-s}=1-s, n_{2-s}=n-(1-s)^2\), construct a graph \(G^{*}\) as that in Definition 2.8. \((ii)\) Add edges to \(G^{*}\). When \(n_{2-s}>1-s\), denote the vertices of clique \(C_i\) as \(v_{ij}\), where \(i, j=1,2,\cdots, 1-s\), and the vertices of clique \(C_{2-s}\) as \(u_{2-s,j}\), where \(j=1,2,\cdots, n-(1-s)^2\). Let the two end-vertices of the edge joining clique \(C_i\) and clique \(C_{2-s}\) be \(v_{i1}\) and \(u_{2-s,i}\), where \(i=1,2,\cdots, 1-s\). Join \(u_{2-s,k}\) to \(v_{i1}\), where \(u_{2-s,k}\in C_{2-s}\) and \(k\geq 2-s\), \(i=1,2,\cdots, 1-s\). When \(n_{2-s}=1-s\), that is \(n={2-s}(1-s)\), add no edges to \(G^{*}\).
Two examples are shown as follows (Figures 3 and 4).
Theorem 3.2. Let \(G\) be a graph in \(\mathscr{G}(n,s)\). Then \(G\) is a maximally \(s\)-neighbor-isolate scattered graph with order \(n(\geq 3)\), and size is \[\left\{ \begin{array}{lll} {\frac{1}{2}}(n^{2}-n-s^{2}-3s)-1, &\mbox{if\ \ $s\geq 0$};\\ \frac{1}{2}(s^4-3s^3+(2-2n)s^2+2ns+n^2-n), &\mbox{if\ \ $s\leq -1$}. \end{array} \right.\\ \]
Proof. Let \(n(\geq 3)\) and \(s\) be two given integers. We distinguish two cases on the value of NIS.
Case 1. \(s\geq 0\).
Let \(G\) be a maximally graph with order \(n\) and \(NIS(G)=s\). Suppose that \(S\) is a NIS-set of \(G\), the components of \(G/S\) are cliques \(C_{1}, C_{2}, \cdots, C_{p}\), and the order of \(C_{j}\) is \(n_{j}, j=1,2,\cdots, p\). Let \(|S|=x\), \(|N(S)|=y\). Then \(x\) and \(y\) are positive integers, we have \[\begin{aligned} \label{1} \sum\limits_{j=1}^{p}n_j=n-x-y, \end{aligned} \tag{1}\] and \[\begin{aligned} \label{2} s=p-x. \end{aligned} \tag{2}\]
It is not difficulty to know that, the size of \(G\) is \[\begin{aligned} \label{3} |E(G)|=max\left\{{x\choose 2}+{y\choose 2}+x(y-x)+x+ \sum\limits_{j=1}^{p}{n_j\choose 2}+ y\sum\limits_{j=1}^{p}n_j\right\}. \end{aligned} \tag{3}\]
If there exists some cliques, say \(C_k\), such that \(n_k\geq 2\), then move any vertex from \(C_k\) to \(N(S)\), the size of the resulting graph increases \(x+\sum\limits_{j=1}^{p}n_j-n_k\), contradicting that \(G\) is maximal. Therefore, \(G/S\) is \(p\) isolated vertices, and \(\sum\limits_{j=1}^{p}{n_j\choose 2}=0, \sum\limits_{j=1}^{p}n_j=p\). By \((1), (2)\) and \((3)\), we have
\[\begin{aligned} |E(G)|=max\left\{-{\frac{5}{2}}x^{2}+\left({\frac{3}{2}-2s}\right)x\right\}+{\frac{1}{2}}n(n-1) -{\frac{1}{2}}s^{2}+{\frac{1}{2}}s. \end{aligned}\]
Let \(f(x)=-{\frac{5}{2}}x^{2}+({\frac{3}{2}-2s})x\), \(x\in Z_+\). It is easy to know that \(f(x)\) reaches its maximal value at \(x=1\). Therefore, the size of \(G\) is \(f(1)+{\frac{1}{2}}n(n-1)-{\frac{1}{2}}s^{2}+{\frac{1}{2}}s={\frac{1}{2}}n^{2}-{\frac{1}{2}}n-{\frac{1}{2}}s^{2}-{\frac{3}{2}}s-1\), and \(G=K_{n-s-2}\vee \bar{K}_{s+2}\). It is easy to know that \(K_{n-s-2}\vee \bar{K}_{s+2}\) is a maximally \(s\)-neighbor-isolate scattered graph of order \(n\).
Case 2. \(s\leq -1\).
Let \(G\) be a graph with order \(n\) and \(NIS(G)=s\). Let \(S\) be a NIS-set of \(G\). By the definition of NIS and Conjecture 2.10, \(n\geq 6\) and \(|S|\geq 2\). Since the structure of a maximal graph is different from that in the case 1, our method will be based on Definition 2.8 and Theorem 2.9. According to Conjecture 2.10, we only consider \(s\geq2-\lfloor \sqrt{n}\rfloor\) when \({\lfloor \sqrt{n}\rfloor}^2 \leq n < \lfloor \sqrt{n}\rfloor \lceil \sqrt{n}\rceil\); or \(s\geq2-\lceil \sqrt{n}\rceil\) when \(\lfloor \sqrt{n}\rfloor \lceil \sqrt{n}\rceil \leq n <{\lceil \sqrt{n}\rceil}^2\).
To finding a maximal graph \(G\), our work will be carried out in the following two steps.
\({(1)}\) Divide \(n\) as \(n_1=n_2=\cdots=n_{1-s}=1-s, n_{2-s}=n-(1-s)^2\), construct a graph as that in Definition 2.8. Let \(G^{*}\) be a graph constructed above. By the proof of Theorem 2.9, we are easy to know that its NIS is \(s\). The size of \(G^{*}\) is \(\epsilon_1=-\frac{1}{2}s(1-s)^2+\frac{1}{2}n_{2-s}(n_{2-s}-1)+\frac{1}{2}(2-s)(1-s)\).
If \(n_{2-s}>2-s\), we move a vertex from the biggest clique(with order \(n_{2-s}\)) to any other clique, the size of the resulting graph is \(\epsilon{'}=\frac{1}{2}s^2(1-s)+\frac{1}{2}(n_{2-s}-1)(n_{2-s}-2)+\frac{1}{2}(2-s)(1-s)\).
Since \(\epsilon_1-\epsilon{'}=-\frac{1}{2}s(1-s)+n_{2-s}-\frac{3}{2}>0\), replace \(n_{2-s}\) by \(n-(1-s)^2\) in \(\epsilon_1\), the size of \(G^{*}\) is \[\begin{aligned} \label{4} \epsilon_1=\frac{1}{2}(1-s)(2-2s+s^2)+\frac{1}{2}(n^2-n-(2n-1)(1-s)^2+(1-s)^4). \end{aligned} \tag{4}\]
\({(2)}\) Add edges to \(G^{*}\).
Without loss of generality, assume \(n_{2-s}>1-s\). Denote the vertices of clique \(C_i\) as \(v_{ij}\), where \(i, j=1,2,\cdots, 1-s\), and the vertices of clique \(C_{2-s}\) as \(u_{2-s,j}\), where \(j=1,2,\cdots, n-(1-s)^2\). Let the two end-vertices of the edge joining clique \(C_i\) and clique \(C_{2-s}\) are \(v_{i1}\) and \(u_{2-s,i}\), where \(i=1,2,\cdots, 1-s\). Join \(u_{2-s,k}\) to \(v_{i1}\), where \(u_{2-s,k}\in C_{2-s}\) and \(k\geq 2-s\), \(i=1,2,\cdots, 1-s\).
It is easy to know that the number of the added edges is \[\begin{aligned} \label{5} \epsilon_2=(n_{2-s}-(1-s))(1-s)=(n-(1-s)^2-1+s)(1-s)=s^3-4s^2+(5-n)s+n-2. \end{aligned} \tag{5}\]
The size of the final graph, denoted by \(G\), is
\[\begin{aligned} \label{6} \epsilon=\epsilon_1+\epsilon_2=\frac{1}{2}(s^4-3s^3+(-2n+2)s^2+2ns+n^2-n). \end{aligned} \tag{6}\]
Now, we prove \(G\) is maximally \(s\)-neighbor-isolate scattered.
Let \(v\) be a vertex of \(G\). Since \(G/ \{v\}\) and \(G\) have the same structure, and \((i)\) \(G/ \{v\}\) has \(1-s\) cliques, \((ii)\) the order of the smallest clique is not less than \(-s\), \((iii)\) the degree of any vertex is not less than \(-s\), we have \(NIS(G)=s\).
On the other hand, if add any edge to \(G\), at least one of the following situations will occur, resulting in an increase in NIS.
(a) A vertex \(v(\in C_i)\) and \(j\) such that \(|V(C_j)|-|N_{C_j}(v)|<-s\), where \(i\not=j\), \(V(C_j)\) is the order of clique \(C_j\), \(N_{C_j}(v)\) is the neighborhood of \(v\) in clique \(C_j\);
(b) Two vertices \(u(\in C_i)\) and \(v(\in C_j)\) such that \(d_{G/\{v\}}(u)<-s\);
(c) A vertex \(u\) such that there exist no edges between some two cliques in \(G/\{u\}\).
Let’s take Figure 3 as an example. If join \(v_{11}\) to \(v_{42}\) or \(v_{43}\), then the degree of \(v_{43}\) or \(v_{42}\) in \(G/\{v_{11}\}\) is \(1\), (a) and (b) occur; if join \(v_{13}\) to \(v_{41}\), then the degree of \(v_{12}\) in \(G/\{v_{41}\}\) is \(1\), (a) and (b) occur; if join \(v_{32}\) to \(v_{42}\), then the degree of \(v_{31}\) in \(G/\{v_{42}\}\) is \(1\), (a) and (b) occur, or there exist no edges between \(C_2\) and \(C_4\) in \(G/\{v_{32}\}\), (c) occur. Similarly, other cases are not difficult to verify.
When \(n_{2-s}=1-s\), \(n=(1-s)(2-s)\), \(G^{*}\) is \((1-s)\)-regular, \((1-s)\)-neighbor connected, adding any edge will increase its NIS. Replace \(n\) by \((1-s)(2-s)\) in \((4)\), we have \(\epsilon=\epsilon_1=\frac{1}{2}(1-s)(s^2-3s+2)\). This result is consistent with the formula \((6)\).
Therefore, \(G\) is a maximally \(s\)-neighbor-isolate scattered graph. The proof is completed. ◻
In this section, we investigate the minimally \(s\)-neighbor-isolate scattered graphs, that is, given order and neighbor-isolated scattering number, construct the graphs with minimal number of edges.
Definition 4.1. A comet, denote \(C_{n,k}\), is a graph obtained by identifying one end of a path \(P_{n-k}\) with the center of a star \(S_{1,k}(k\geq 2)\). The center of \(S_{1,k}\) is called the center of \(C_{n,k}\).
Definition 4.2. A graph \(G\) is minimally \(s\)-neighbor-isolate scattered, if \(NIS(G)=s\) and there does not exist a proper spanning subgraph \(H\) of \(G\) with \(NIS(H)=s\).
In other words, deleting any edge of a minimally \(s\)-neighbor-isolate scattered graph, the NIS of the resulting graph will be no longer \(s\).
Let \(n, s\) be two given integers. We construct a class of graphs with order \(n(\geq 3)\), denote \(\mathscr{H}(n,s)\), such that for any graph \(H\in \mathscr{H}(n,s)\), \(NIS(H)=s\). We distinguish 5 cases on the value of NIS.
(1) \(s\leq -1\). This means \(n\geq 6\). If \(s=-1\) and \(n=7,11\), then \(H=C_n\). Otherwise, let \(\lfloor\frac{n}{2-s}\rfloor=k\), and \(n=(2-s)k+r\), where \(0\leq r<2-s\). Divide \(n\) into \(2-s\) integers, i.e., \(n=k(2-s-r)+(k+1)r\), construct graph \(H\) as that in Definition 2.8.
(2) \(s=0\).
(i) \(n=3, 4, 8\). \(H=P_{n}\).
(ii) \(n=6\). Let \(V(H)=\{v_{0},v_{1},…,v_{5}\}\), \(E(H)=\{v_{0}v_{2}, v_{3}v_{5}, v_{i}v_{i+1}: i=0,1,2,3,4\}\).
(iii) \(n=7\). Let \(V(H)=\{v_{0},v_{1},…,v_{6}\}\), \(E(H)=\{v_{0}v_{3}, v_{1}v_{3}, v_{i}v_{i+1}: i=0,1,2,3,4,5\}\).
(iv) \(n=11\). The graph \(H\) is constructed by add an edge between any two vertices with distance 2 to the cycle \(C_{11}\).
(v) \(n\neq 3,4,6,7,8,11\). Let \(H=C_n\).
(3) \(s=1\). This means \(n\geq 4\).
(i) \(n=4\). Let \(H=S_{1,3}\).
(ii) \(n=8\). Let \(H=C_{8,2}\).
(iii) \(n\neq 4,8\). Let \(H=P_{n}\).
(4) \(2\leq s\leq n-4\).
(i) \(n-s=3,4,8\). Let \(P_{n-s}\) be a path of order \(n-s\) and \(S\) be a NIS-set of \(P_{n-s}\). Add \(s\) 1-paths to an adjacent vertex of one arbitrary vertex in \(S\), this is the graph \(H\).
(ii) \(n-s\neq3, 4, 8\). Let \(P_{n-s}\) be a path of order \(n-s\) and \(S\) be a NIS-set of \(P_{n-s}\). Add \((s-2)\) 1-paths and one 2-path to an adjacent vertex of one arbitrary vertex in \(S\), this is the graph \(H\).
(5) \(s=n-3\). Let \(H\) be the star \(K_{1,n-1}\).
Theorem 4.3. Let \(H\) be a graph in \(\mathscr{H}(n,s)\). Then \(H\) is a minimally \(s\)-neighbor-isolate scattered graph with order \(n(\geq 3)\), and its size is \[\left\{ \begin{array}{lllllll} {\frac{1}{2}(n(k-1)+r(k+1)+(2-s)(1-s))}, &\mbox{if $s=-1$ and $n\not=7,11$, or $s\leq -2$};\\ n-1, &\mbox{if $n=3,4,8$, $s=0$, or $1\leq s\leq n-3$};\\ n, &\mbox{if $n=7,11$, $s=-1$, or $n\neq3,4,6,7,8,11$, $s=0$};\\ n+1, &\mbox{if $n=6,7,11$, $s=0$},\\ \end{array} \right.\] where \(k=\lfloor\frac{n}{2-s}\rfloor\), \(r=n-(2-s)k\).
Proof. By Conjecture 2.10, \(s\geq 2-\lfloor\sqrt{n}\rfloor\) when \({\lfloor n\rfloor}^2 \leq n < \lfloor n\rfloor \lceil n\rceil\), and \(s\geq 2-\lceil \sqrt{n} \rceil\) when \(\lfloor n\rfloor \lceil n\rceil \leq n <{\lceil n\rceil}^2\). We distinguish the following 5 cases to prove \(H\) is minimally \(s\)-neighbor-isolate scattered(abbreviated as minimally \(s\)–NIS below), and then obtain their size.
Case 1. The case \(s=-1\) and \(n=7,11\) is trivial. If \(s=-1\) and \(n\not=7,11\), or \(s\leq -2\), then \(n\geq 12\).
By the proof of Theorem 2.9, \(NIS(H)=s\). Although the amount of calculation increases with \(n\), it is not difficult to verify that \(H\) is minimally \(s\)-neighbor-isolate scattered. The size of \(H\) is \[{k\choose 2}(2-s-r)+{{k+1}\choose 2}r+{2-s\choose 2}=\frac{1}{2}(n(k-1)+r(k+1)+(2-s)(1-s)).\]
Case 2. \(s=0\).
Case 2.1. \(n=3, 4, 8\).
\(H=P_{n}\) is a tree. So it is minimally \(0\)–NIS, and the size is \(n-1\).
Case 2.2. \(n=6, 7, 11\).
It is easy to know that \(NIS(H)=0\), the size of \(H\) is \(n+1\), and deleting any edge will increase NIS of the resulting graph. Therefore, \(H\) is minimally \(0\)–NIS.
Case 2.3. \(n\neq3,4,6,7,8,11\).
Then it is easy to know that the cycle \(C_n\) is minimally \(0\)–NIS, and the size is \(n\).
Case 3. \(s=1\).
This means \(n\geq 4\). When \(n=4\) or \(8\), \(H\) is the star \(S_{1,3}\) or the comet \(C_{8,2}\); when \(n\neq 4,8\), \(H\) is path \(P_{n}\). It is easy to know that they are minimally \(0\)–NIS, and the size is \(n-1\).
Case 4. \(2\leq s\leq n-4\).
Since \(H\) are trees and \(NIS(H)=s\), the graphs are minimally \(s\)–NIS, and the size is \(n-1\).
Case 5. \(s=n-3\).
Obviously, \(K_{1,n-1}\) is the unique minimally \(s\)–NIS graph, and the size is \(n-1\). ◻
As discussed in Section 1, our definition of neighbor-isolated scattering number is well. Firstly, it can distinguish structural differences of some graphs in the neighbor case. Secondly, it shows that the definition and the name are consistent. Thirdly, it really refines the concept of vertex-neighbor scattering number.
There are still many issues worthy of further investigation regarding this parameter. We list some issues as follows. \((1)\) Consider the proof of Conjecture 2.10 proposed in Section 2. \((2)\) Construct connected simple graphs reaching an upper bound of VNS such that \(NIS<VNS\). \((3)\) Construct connected simple graphs reaching a lower bound of NIS such that \(NIS<VNS\).
This work was supported by NSFC (No. 61902304).