Distance and connectivity measures in permutation graphs

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. © 2003 Elsevier B.V. All rights reserved.