Optimal Rearrangeable Graphs

Let G be a finite graph with vertex set V(G) and edge set E(G).* Let I and ft be nonempty subsets of V(G) (not necessarily disjoint) and let S denote the set v(G)(i u a ) = {»e y«7)i»$/uo}. We use the following terminology: (i) A request is an ordered pair (x, y) with i G J , y £ 12, and x y. (ii) A set of requests is called an assignment if each vertex in the set occurs once at most. (Hi) An assignment A is called realizable in G (or we say G satisfies A) if we can find a set of vertex-disjoint paths connecting x and y for each pair (x, y) in A. (iv) A graph G is said to be rearrangeable if G satisfies any assignment. The problem we consider, first suggested by F. Iv. Hwang, 2 is to find * I.e., E(G) consists of a prescribed set of unordered pairs of distinct elements of some finite set V(G). Generally, we follow the terminology of Harary. 1 1647 rearrangeable graphs with given I and with ft having the least possible number of edges. In this paper, we derive lower bounds on the minimum number of edges that a rearrangeable graph can have (see Theorem 1 in Section II). In addition, we also construct rearrangeable graphs which meet these bounds so that these graphs are optimal by this measure. Finally, we consider a generalization of rearrangeability, called /c-rearrangeability, and we solve the corresponding problems in this case as well. This study was motivated by questions of rearrangeability in switching networks (see Ref. 3). The sets I and ft correspond to the sets of inlets and outlets, respectively; an edge {x, y} of G corresponds to a crosspoint between x and y.