On Super Restricted Edge Connectivity Of Graphs

Graphs are often as models for the multiprocessor interconnection networks. Let G be an undirected, simple and connected graph. A restricted edge-cut F of G is an edge cut such that G — F has no isolated vertex. The restricted edge-connectivity is the minimum cardinality over all restricted edge-cuts. The restricted edge connectivity, as a generalization of classical edge connectivity, is an important measure of fault-tolerance for interconnection networks than the restricted edge-connectivity. The super restricted edge connectivity provides a more accurate index of fault-tolerance of networks. G is called a super restricted edge connected graph if every minimum restricted edge cut separates exactly one edge. In this thesis, we mainly study the super restricted edge connectivity for several graph-classes.In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, we give in Section 1.2 some concepts and results on the super restricted edge connectivity.Chapter 2 deals with the super restricted edge connectivity for graphs of diameter 2. In Section 2.1 we provide several simple, but very useful facts and summarize the obtained results on connectivity of graphs of diameter 2. In Section 2.2, some sufficient conditions for super restricted edge connectivity in graphs of diameter 2 are given as follows.(l)Let G be a graph with \V(G)\ ≥ 4. If \N(u) n N(v)\ ≥ 3 for all pairs u,v of nonadjacent vertices such that neither u nor v lie on a triangle, and \N(u)∩N(v)\ ≥ 4 for all pairs u, v of nonadjacent vertices with the property that u or v are on a triangle, then G is a super restricted edge connected graph unless G belongs to an especial graph-class.(2)Let a graph G contain no cycle of length 3 and satisfy | V(G)| ≥ 9, δ(G) ≥ 3, D(G) = 2. Then G is a super restricted edge connected graph.(3)Let G be a graph with |V(G)| ≥ 10. If \N(x) ∩ N(y)\ ≤ 1 for any edge xy, and d(u) + d(v) ≥ \V(G)\ — 1 for all pairs u, v of nonadjacent vertices, then G is a super restricted edge connected graph.In Section 2.3, we first point out that the above results improve some results which have been given by others, and then present examples which show that the above results are independent each other.Kautz graph, the topology of Kautz network, is a class of important graphs, which has been widely used in the design and analysis of interconnection networks. In Chapter 3 we study the super restricted edge connectivity of Kautz undirected graphs. In Section 3.1 we introduce the definition of Kautz undirected graphs and results concerning the restricted edge connectivity of Kautz undirected graphs. Some useful results are obtained by introducing the concept of nomarl out walks in Section 3.2. Finally, we conclude that Kautz undirected graphs UK(d, n) is a super restricted edge connected graph for d ≥ 3, n ≥ 2. Combining this with other results, the super restricted edge connectivity of all Kautz undirected graphs are ascertained.