On The Bounded Fragmentation Graphs And The Edge Bounded Fragmentation Graphs

Connectivity and edge connectivity are the basic parameters of graphs which can be used to measure the reliability of the communication networks. But the two parameters are rough, they can not distinguish between some graphs which are connected differently. So some new parameters are presented: the toughness, the integrity, the coritivity and the tenacity. These parameters are more delicate than connectivity and edge connectivity, because they concern not only the difficulty of destroying a networks but also the state of the networks which have been destroyed. But there are conflicts between these parameters and the connectivity(the edge connectivity). For some graphs, the result of connection measured with these parameters is conflict with that measured with the connectivity(the edge connectivity). Bounded fragmentation and edge bounded fragmentation presented in this paper can be considered as a generalization of connectivity and edge connectivity. They are more delicate than connectivity and edge connectivity, and there are no conflicts between them.In this paper, we first put forward some basic problems of bounded fragmentation: the existence of bounded fragmentation graphs, the order of the graph, the decision problem of the bounded fragmentation graphs, and we try to present some sufficient conditions of bounded fragmentation graphs. Then referred to the definition of bounded fragmentation, we define edge bounded fragmentation, discuss the existence of edge bounded fragmentation graphs, establish the connection between edge connectivity and edge bounded fragmentation, and present some possible application of edge bounded fragmentation in designing reliable networks. At the end of this paper, we present some open problems that can be considered as possible extensions of our work.