Distance and connectivity measures in permutation graphs Original Research Article

A permutation graph Gπ of a graph G (or generalized prism) is obtained by taking two disjoint copies of G and adding an arbitrary matching between the copies. For the parameters diameter, radius, average distance, connectivity and edge-connectivity, we compare the values of the parameter for Gπ and G. In particular, we show that if G has no isolates and is not 2Kk for k odd, then there exists a permutation graph of G with edge-connectivity equal to its minimum degree.