ROUTING PERMUTATIONS ON GRAPHS VIA MATCHINGS

A class of routing problems on connected graphs G is considered. Initi ally, each vertex upsilon of G is occupied by a ''pebble'' that has a unique destination pi(upsilon) in G (so that pi is a permutation of th e vertices of G). It is required that all the pebbles be routed to the ir respective destinations by performing a sequence of moves of the fo llowing type: A disjoint set of edges is selected, and the pebbles at each edge's endpoints are interchanged. The problem of interest is to minimize the number of steps required for any possible permutation pi. This paper investigates this routing problem for a variety of graphs G, including trees, complete graphs, hypercubes, Cartesian products of graphs, expander graphs, and Cayley graphs. In addition, this routing problem is related to certain network flow problems, and to several g raph invariants including diameter, eigenvalues, and expansion coeffic ients.