On The Neighbor-integrity Of Graphs

There are two entirely different approaches to measuring the susceptibility of a graph or a network to damage. One approach based on an entirely deterministic theory, is called (the) deterministic approach,and the other based on an probabilistic theory, is called (the) probabilistic approach.The deterministic approach uses graph invariants as measures of "vulnerability" of a graph or network, but for the study of "reliability" of a graph or network, we often use the probabilistic approach.The attempt to quantify the "vulnerability" of a graph or network began with connectivity and the theorems of Menger and Whitney. Nowadays, the problem of quantifying the "vulnerability" of a graph or network has received much attention, especially on the field of computer or communication networks.By stability studying, many graph theoretical parameters have been used in the past to described the "vulnerability" of graphs .Apart from many parameters in connectivity of graphs, for example, connectivity, line-connectivity, local connectivity, local line-connectivity, etc. There are other new parameters, including toughness, tenacity, scattering number and integrity.This paper was based on the works of forefathers, primarily studied a new measureof graph vulnerability......the vertex-neighbor-integrity of a graph. The concept of thevertex-neighbor-integrity of a graph was introduced by Margaret B.Cozzens and Shu_shih Y.Wu in1994.This new parameter in connectivity of a graph incorporates the concept of the integrity and the idea of the vertex-neighbor- connectivity.In this paper, we are primarily concerned with the neighbor-integrity of graphs.This paper is composed of four chapters, the main contents are showed as the following.Chapter one gives a brief introduction about the history and current situation of neighbor-integrity of graphs and points out the background and siginificance of this parameter.In chapter two, concept of vertex-neighbor-integrity of graphs is introduced firstly,and then some relationships between the vertex-neighbor-integrity and some other parameters of graphs are given, and then the relationship between the vertex-neighbor-integrity of the graph and it's subgraph is given. Secondly, the vertex-neighbor-integrity of the Cartesian product of graphs and the vertex-neighbor-integrity of the join of graphs are disussed. Thirdly, the relationship between the vertex-neighbor-integrity of the graph and the maximum edges number of the graph is studied.Edge-neighbor-integrity, as a generalization of vertex-neighbor-integrity, is studied mainly in chapter three. Apart from the problem we discussed in chapter two, here the edge-neighbor-integrity of cycles and the power of cycles was gived firstly, and the edge-neighbor-integrity of line graphs and total graphs was discussed. In the end, the relationship between the edge-neighbor-integrity of the graph and the maximum and minmum edges number of the graph is studied.Because edge-neighbor-integrity is a mixed concept-this may not seem verysatisfactory, this notivated me to introduce a new measure of vulnerability. This new measure of vulnerability involves edges only and thus is called pure-edge-neighbor-integrity. The bascic property of pure-edge-neighbor-integrity was discussed, then the upper and lower bounds of the pure-edge-neighbor-integrity are investigated, in the last, the pure-edge-neighbor-integrity of some classes of graphs was studied.