Study Of Graph Vulnerability Parameters

In order to avoid and minimize the loss caused by communication disruptions, the stability of them must be considered during designing computer and communication networks. Therefore, one of the basic ideas in designing networks is that they should be not easily destroyed by outside attacks, and easy to be recovered even if they are disrupted. A computer or communication network is often modeled by a connected graph, where the vertices represent the communication stations and the edges represent the direct communication links. For a network, its stability is commonly described by the vulnerability parameters of the corresponding graph.Early researches on the vulnerability parameters of graphs mainly encompassed connectivity and edge-connectivity. These two parameters are widely used to measure the vulnerability of graphs, and it was proved that both of them could be computed in polynomial time. Due to the limitation of the above two parameters when they are used to measure the vulnerability of graphs, recently, people began to bring in some other new vulnerability parameters, such as toughness and edge-toughness, scattering number, integrity and edge-integrity, tenacity and edge-tenacity, rupture degree, neighbor-connectivity and edge-neighbor-connectivity, vertex-neighbor-integrity and edge-neighbor-integrity, vertex-neighbor-scattering number and edge-neighbor-scattering number. Unlike connectivity and edge-connectivity, these new parameters not only consider the difficulty to disrupt the networks, but also consider how the networks get disrupted.This thesis is mainly focused on the vulnerability parameters of vertex (edge)-neighbor-scattering number, rupture degree, integrity and weak-integrity and so on.In Chapter 1, we first give a brief introduction of the definitions of these various vulnerability parameters and provide the research background and current development of them. At the same time, we give the main results of this thesis...