On Optimizing \(m\)-Restricted Edge Connectivity of Generalized Permutation Graphs

Abstract

To construct a large graph from two smaller ones that have same order, one can add an arbitrary perfect matching between their vertex-sets. The topologies of many networks are special cases of these graphs. An interesting and important problem is how to persist or even improve their link reliability and link fault-tolerance. Traditionally, this may be done by optimizing the edge connectivity of their topologies, a more accurate method is to improve their \(m\)-restricted edge connectivity. This work presents schemes for optimizing \(m\)- restricted edge connectivity of these graphs, some well-known results are direct consequences of our observations.