A Research On Neighbor Parameters Of Graphs

In the process of designing and maintaining transportation, computer or communication networks, the stability (vulnerability) of them is an important performance criterion. Therefore, one of the basic ideas to design networks is that they do not easily get disrupted under external attack and they are easily reconstructed if they do really get disrupted. A network system can be modeled by a connected graph, in which vertices represent modules and edges represent some special connection between the modules, then we can solve the problem through the graph theory. Under the mathematical model of netwoks, people began to put forward some parameters to measure the stability of networks. At the beginning, vertex-connectivity and edge-connectivity are two parameters often used for it. But the two parameters have some deficiencies, because they do not think of the survival-subgraph after removing the vertices or edges. In order to overcome the deficiencies, people have introduced some new parameters, such as toughness, scattering number, integrity, tenacity in the past decade. All of these parameters are more reasonable than vertex-connectivity and edge-connectivity, because they can measure not only the amount of work done to damage the network but also how badly the network is damaged.In 1990, Cozzens introduced the idea of modeling a spy network by a graph whose vertices represent the agents and whose edges represent lines of communication. Clearly, if a spy is discovered or arrested, the espionage agency can no longer trust any of the spies with whom he or she was in direct communication, and so the betrayed agents become effectively useless to the network as a whole. It is obvious that we can not measure the stability of spy network using the above parameters. With the background stated above, people introduced some new parameters, such as vertex-neighbor-connectivity, edge-neighbor-connectivity, vertex-neighbor-integrity, edge-neighbor-integrity, vertex-neighbor-scattering number, edge-neighbor-scattering number. But these neighbor parameters have some deficiencies to measure the stability of some networks.The main contents of this thesis are showed as follows:(1) We introduce the background and significance of the neighbor-connectivity parameters (vertex-neighbor-connectivity, edge-neighbor-connectivity, vertex-neighbor-integrity,...