Edge Vulnerability Parameters Of Bisplit Graphs

A computer and a communication network can conveniently be described by means ofa connected graph consisting of a set of points (represent the communication stations) to-gether with liens (represent the direct communication links) joining certain pairs of thesepoints. There are several measures of the vulnerability of a network. When measuringthe vulnerability of a network, we consider its corresponding graph. The vulnerabil-ity parameters one generally encounters are connectivity and edge-connectivity, whichmeasure the vulnerability of a graph. These two parameters give the minimum cost todisrupt the network, but they do not take into account what remains after destruction.To measure the vulnerability of networks more properly, some vulnerability parametershave been introduced and studied. Among them are (edge-)toughness, (edge-)integrity,scattering number, (edge-)tenacity and several variants of (edge-)connectivity, each ofwhich measures not only the difficulty of breaking down the network but also the effectof the damage. In general, for most of the aforementioned parameters, the correspondingcomputing problem is NP-hard. So it is of interest to give formulae or algorithms forcomputing these parameters for special classes of graphs.In this thesis, we investigate edge vulnerability parameters for the spatial class ofgraphs, i.e., the class of bisplit graphs. A graph is called bisplit if its vertex set canbe partitioned into three stable sets I,Y and Z such that Y∪Z induces a completebipartite graph (a biclique). In Chapter 1, we first give a brief introduction to the defi-nitions of some edge vulnerability parameters and provide the research background andcurrent development on the issue. At the same time,we give the main results of thisthesis. Let G = (Y∪Z,I,E) be a connected noncomplete bisplit graph. In Chapter 2,we study edge vulnerability parameters of bisplit graph: in the first section, we show thatits edge-connectivity isδ(G); in the second section, we prove that if |Z|≥|Y |≥(2/3)δ(G),then its edge-toughness is min , we also give examples to show that thecondition |Z|≥|Y |≥(2/3)δ(G) can not be dropped out; in the last section, it is shown thatif |Y∪Z| < 2δ(G), then the edge-integrity of G equals |V (G)|, and examples are givento assert that our result is best possible.