On Optimizing m-Restricted Edge Connectivity of Graphs

It is known that networks with greater m-restricted edge connectivity are locally more reliable for all m≤4. This work studies the optimization of m-restricted edge connectivity of graphs in the case when m=4. Let G be a connected graph of order at least 8 and Ore(G)= min{d(u)+d(v): u and v are two non-adjacent vertices of graph G }. It is proved in this work that graph G is maximally 4-restricted edge connected if Ore(G) ( |G|+5. This lower bound can be decreased to |G|-1 when G is triangle-free. A class of graphs is presented to exemplify the sharpness of the lower bound.