A Study On Vertex-Neighbor-Isolated Scattering Number Of Graphs

In the real world,networks often suffer from destructive events from the inside or outside.The consequences of these damages are not only in themselves,but also in chain reactions or secondary disasters.For example,the renegade of spies,the spread of high-risk viruses in the crowd,the threat of computer viruses to information networks,etc.The invulnerability of these special networks must be considered in the neighbor case Therefore,the research on neighbor invulnerability of networks has important theoretical and practical significance.In this paper,we studied some problems about vertex-neighbor-isolated scattering number which is an important parameter to describe the neighbor invulnerability of networks.Firstly,the definition of the vertex-neighbor-isolated scattering number proposed by Ersin Aslan in 2015 is modified.Because the parameter does not calculate all the components remaining after the neighbor vertex cut is removed,nor does it make all components isolated vertices or cliques,the definition is not reasonable.For a connected graph G,the vertex-neighbor-isolated scattering number is redefined as NIS(G)=max{i(G/S)-|S|:i(G/S)>1},where S is the neighbor vertex cut of G such that each cmponent of G/S is an isolated vertice or a clique,and i(G/S)is the component number of G/S.Secondly,the problem of calculating the vertex-neighbor-isolated scattering number for several important graph classes are studied,and the calculation formulas of the vertex-neighbor-isolated scattering number of some basic graphs,generalized Petersen graphs,line graphs,power graph,complement graphs of paths and cycles,and sequential joined graphs are given.By studying some bounds of the vertex-neighbor-isolated scattering number of the general graphs and the relationship with other important parameters such as vertex-neighbor-scattering number,neighbour connectivity,neighbour integrity,the relationship between the vertex-neighbor-isolated scattering number and the network structure is preliminarily explored.Finally,by a constructive method,an instance of the vertex domination number of a bipartite graph is reduced into an instance of vertex-neighbor-isolated scattering number of a bipartite graph in poiynomial time,thereby,the NP completeness of the vertex-neighbor-isolated scattering number of bipartite graphs is proved.By adding edges on a complete graph,a path and a cycle,the maximum and the minimum networks are constructed in the conditions of given order and vertex-neighbor-isolated scattering numbe,respectively.This paper solves some basic problems of the vertex-neighbor-isolated scattering number,which play an important basic role for the subsequent in-depth study.