Optimal Rearrangeable Graphs
Fan Chung · Bell System Technical Journal · 1975
Many important properties of switching networks can be effectively studied in the more general context of graph theory. In particular, the various rearrangeability properties of a network fall into this category. If G is a graph with vertex set V = I ∪ Ω, we say G is rearrangeable if, for all choices of distinct vertices, i1, i2, …, i1in I and j1, j2, …, j1in Ω, there exist vertex disjoint paths between ikand jkfor all k. In this paper, we determine the minimum number of edges any rearrangeable graph may have for all choices of I and Ω. We also discuss generalizations in which V is strictly greater than I ∪ Ω and/or t is bounded by a predetermined value. The minimal rearrangeable graphs we construct can be used to form efficient rearrangeable (and nearly rearrangeable) switching networks of arbitrary size.