Distance and connectivity measures in permutation graphs

A permutation graph G(pi) 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(pi) and G. In particular, we show that if G has no isolates and is not 2K(k) for k odd, then there exists a permutation graph of G with edge-connectivity equal to its minimum degree. (C) 2003 Elsevier B.V. All rights reserved.