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.