On the 3-restricted edge connectivity of permutation graphs

An edge cut WW of a connected graph GG is a kk-restricted edge cut if G−WG−W is disconnected, and every component of G−WG−W has at least kk vertices. The kk-restricted edge connectivity is defined as the minimum cardinality over all kk-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The kk-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum kk-edge degree. In this paper some sufficient conditions guaranteeing optimal kk-restricted edge connectivity and super kk-restricted edge connectivity for permutation graphs are presented for k=2,3k=2,3.