A Study Of Vertex Neighbor Toughness Of Graphs

In this information age,networks bring unprecedented convenience to people.At the same time,however,the human dependence on networks is also growing.In recent decades,serious accidents with huge loss caused by network interruption occurred one after another.One of the main reasons is that the network invulnerability is not strong.Therefore,many attentions have been paied to the problem of network invulnerability analysis and design.Usually,a network can be modeled by a connected graph.Its invulnerability refers to the ability to resist external damages.The method of network invulnerability research is to describe the "minimum" cost to interrupt the contact between some vertices and the state of the remaining part of the network quantitatively.The network invulnerability is divided into two branches,the(traditional)invulnerability and the neighbor invulnerability.The study of the later is against the chain reactions caused by network desruption,so it is relatively late and the results is not rich.The main neighbor invulnerability parameters are neighbor-connectivity,neighbor-integrity,neighbor-scattering number.Toughness is considered as the best invulnerability parameter.In this paper,combinating neighbor with this concept,a new parameter called vertex neighbor toughness is introduced as a supplement to the existed neighbor invulnerability parameters.The formulas of vertex neighbor toughness of several preliminary graphs are given firstly.Then the vertex neighbor toughness of the Cartesian products of paths and cycles and their relationships are studied emphatically.The results of this paper show that vertex neighbor toughness is usually better than other parameters in the measure of neighbor invulnerability of networks.This thesis consists of five chapters.The content is arranged as follows.In the first chapter,the concept of network invulnerability and its research situation is introduced.Chapter two summarizes the main contents and results of invulnerability parameters and neighbor invulnerability parameters.In the third chapter,the concept of vertex neighbor toughness is introduced,and the formulas of paths,cycles,stars etc.and composition graphs as well as the generalized Petersen graph are given.The fourth chapter is the main content of this thesis,in which the problem of vertex neighbor toughness of the Cartesian product of paths and cycles are solved completely.By comparing the parameter values,the differences of the neighbor invulnerability of these graphs are revealed.Chapter 5 summarizes this thesis and puts forward a number of questions worthy of further study.