On The Integrity Of Graphs

On the integrity of graphsLi feng weiAbstract The problem of quantifying the stability of graphs has received much attention nowadays, eapecially on the field of computer or communication networks. By stability studying, people know more and more characters of graphs. So many graph theoretical parameters have been used in the past to described the stability of graphs.Most notably, the parameters called connectivity and line-connectivity have been frequently used. The connectivity of a graph G is the least number of vertices of G whose removal disconnects G Similarly, the line-connectivity of G is the least number of G whose removal disconnects G the higher the connectivity(edge-connectivity) of G, the more stable it is considered to be. But the difficulty with these two parameters is that they do not take into account what remains after the graph is disconnected.In fact, on one hand, it is often found that two graphs with the same number of vertices (edges)and the same connectivity(edge-connectivity)) may result in entirely different forms after a minimum disconnecting set of vertices(edges) is removed, one may be totally disconnected while the other may consist of a few very stable components, and thus be much easier to reconstruct.On the other hand, we often face this question: how easily can we disrupt a system at the least cost, on the contrary, when we set up a system, especially a communication system, we try our best to make it as stable as possible that it can be reconstructed easily if it do get disrupted .For the two sides above, it is urgent for us to find new parameters to measure the stability of graphs. Consequently, a number of other parameters have recently been introduced in an attempt to cope with the difficulty which the connectivity and line-connectivity have, including toughness, edge-toughness, tenacity, edge-tenacity, scattering number and integrity. Unlike the connectivity measures, each of these parameters shows not only the difficulty to break down the network but also the damage that has been caused .In this paper, we are primarily concerned with the integrity of graphs.This paper is composed of six chapters, the main contents are showed as the following.Chapter one gives a brief introduction about the history and current situation of the integrity of graphs and points out the background and siginificance of this parameter .In chapter two, concepts of integrity, integral set and integral number are introduced firstly, and then some relationships between the integrity and some other parameters of graphs are given, then the upper and lower bounds of the integrity are investigated on the basis of integral number determined. The final result is the upper and lower bounds of integral number if the integrity is known.The third chapter focuses on the integrity of a special kind of graphs-permutation graphs, especially the cycle permutation graphs.In chapter four, firstly, the concepts of the maximum and minimum networks are introduced, and then we investigate the maximum and minimum networks on the basis of order and integrity are given, and we give a method to construct such a maximum network. At last we study the maximum network assumed that the order, integrity and connectivity are all known.Edge-integrity, as a generalization of integrity, is studied mainly in chapter five. The fifth chapter determines integrities of some special kinds of graphs such as grid, tori, line graph,composite graph and gives a relationship between the edge-integrity of a graph and integrity of its line graph, and then like the study of integrity, some relationships between the edge-integrity and some other parameters are given, then the maximum network is determined on the basis of order and edge-integrity are given. The last result gives the minimum network on the basis of order and size of graph are known .In chapter six, we investigate the possible maximum and minimum integrities of order and maximum degree given trees, in addition, an algorithm for comput...