Some Special Classes Of Graph Vulnerability Parameters

When designing computer and communication networks, the vulnerability of them must be considered in order to avoid and decrease the loss caused by communication diruptions. Therefore, one of the basic ideas in designing networks is that they do not easily get disrupted. These networks are often modeled by connected graphs, where the vertices represent the communication stations and edges represent the direct communication links. It is clear that the more vulnerable the corresponding graph is, the less stable the network is.Connectivity and edge-connectivity are two parameters often used to measure the vulnerability of graphs. It is well known that both of these two parameters of graphs can be computed in polynomial time. Recently, some new vulnerability parameters have been introduced, namely, toughness and edge-toughness, scattering number, integrity and edge-integrity, tenacity and edge-tenacity, neighbour-connectivity and edge-neighbour-connectivity, vertex-neighbour-integrity and edge-neighbour-integrity, vertex-neighbour-scattering number and edge-neighbour-scattering number. Unlike connectivity and edge-connectivity, these new parameters show not only the difficulty to damage the network but also how badly the network is damaged.It has been proved that computing most of these new vulnerability parameters are NP-hard. So, it is very important and interesting to study how to compute these parameters of special classes of graphs. In this thesis, we are mainly concerned with this issue for three classes of graphs: split graphs, thorn graphs and the Cartesian products of paths and cycles.In Chapter 1, we first give an introduction to various vulnerability parameters and provide a brief overview on these parameters of some specific classes of graphs (path, cycle, star graph, comet, complete k-partite graph et al.) Our main contributions in this thesis can also be found in this chapter.In Chapter 2, we study various vulnerability parameters of split graphs.In Chapter 3, we dicuss some vulnerability parameters of thorn graphs of specific graphs and corrected some mistakes appeared in a paper of of Kirlangic. An algorithm for computing of the scattering number of unicylic graphs is also presented.In Chapter 4, we study the rupture degree and tenacity of the Cartesian products of paths and cycles.We conclude the thesis with Chapter 5 by proposing some problems for further research on the vulnerability parameters of specific classes graphs.