Optimality Of Minimally Restricted Edge Connected Graphs And Fault Tolerance Of Super Edge Connected Graphs

With the rapid development of information networks, reliability of networks draws more and more attention of researchers. The classic measure of network reliability is edge connectivityλ(G).For further study, many variations have been introduced, which are known as higher order connectedness, such as m-restricted edge connectivityλ_m(G),λ_m-optimal, super-λ_m,etc.A graph G is minimally m-restricted k-edge connected ifλ_m(G) = k andλ_m(G- e) < k for any e∈E(G). We show that every minimally 2-restricted k-edge connected graph isλ₂-optimal. As a consequence, such a graph has an edge with degree k. This leads us to consider the enumeration problem of edges with degree k. We prove that every minimally 2-restricted k-edge connected graph has at least three edges of degree k, and if furthermore k≠4, then there are at least four. Examples show that the lower bounds are best possible. We also prove that except for the 3-cube, each minimally 3-restricted k-edge connected graph isλ₃-optimal. In the last part of the thesis, we define a new graph parameter: edge fault tolerance of super edge connectivity of graphs. A super-λgraph G is called m-super-λif for any edge set S (?) E with |S|≤m, G-S is still super-λ. The maximum integer of such m is called the edge fault tolerance of super edge connectivity of G, denoted by S_λ(G). We prove that min{λ₂(G) -δ(G) - 1,δ(G) - 1}≤S_λ(G)≤δ(G) -1. More refined bounds are given for regular graphs and Cartesian product graphs. In addition, exact value of S_λ(G) for edge transitive graph G is obtained.