Rearrangeable graphs

Given a directed graph G = (V, E). where V = {1,2,...,n}, an n-permutation pi is said to be realizable on G if there exist n edge-disjoint paths in G that connect vertex i to vertex pi(i) (1 less than or equal to i less than or equal to n). G is said to be rearrangeable if all n! n-permutations are realizable on G. This paper shows that any rearrangeable graph G must satis fy m greater than or equal to 2(n - 1), where m is the number of edges in G . Moreover m greater than or equal to dn must be satisfied if G is rearrang eable and symmetric, where d is the diameter of G. To measure the rearrange ability of graph G, a parameter called rearrangeability number, psi (G), is introduced, which is the minimal multiplicity every edge needs to be dupli cated in order for G to become rearrangeable. (C) 1999 Elsevier Science B.V . All rights reserved.