M-Restricted Edge-connected Graphs With Circumference K And Girth K

In the study of communication networks, the interconnection network topology of the multiprocessor system is often modeled by a graph. The property of network topology is measured by the properties and parameters of graphs. The edge connectivity is one classical parameter to measure the reliability of networks. But the edge connectivity has an obvious deficiency. Based on this consideration, as a generalization of the edge connectivity, the concept of m-restricted edge-connectivity is given.Let G be an undirected, simple and connected graph and let F be an edge cut of G. If each connected component of G-F contains at least m vertices, then F is called an m-restricted edge cut of G. The m-restricted edge connectivity of G is the cardinality of a minimum m-restricted edge cut. A graph G is an m-restricted edge-connected graph if G contains an m-restricted edge cut. A connected graph G with order v(G)> 2m is called a flower, if it contains a vertex s such that every component of G-s consists of at most m-1 vertices, where m is an integer and m≥2.Recently, the m-restricted edge-connected graphs have drawn considerable research attention. In 2009, Wang and Zhu characterized m-restricted edge-connected graphs with circumference 3. In 2011, they also characterized m-restricted edge-connected graphs with circumference 4 and 3-cycle free. Following their works, this thesis characterizes m-restricted edge-connected graphs with circumference k and girth k, where k=5 or 6.This thesis consists of three chapters.In chapter 1, after a brief introduction to the application background and the devel-opments of m-restricted edge connected of graphs, the used basic concepts and notations on graphs are given.In chapter 2, we study the m-restricted edge connected of graphs with circumference 5 and girth 5, and we obtain the following result:let G be a connected graph with order v(G)≥2m, circumference 5 and girth 5, then G contains an m-restricted edge cut if and only if G is not a flower and does not belong to a special class of graphs.In chapter 3, we study the m-restricted edge connected of graphs with circumference 6 and girth 6, and we obtain the following result:let G be a connected graph with order v(G)≥2m, circumference 6 and girth 6, then G contains an m-restricted edge cut if and only if G is not a flower and does not belong to two special classes of graphs.