Routing permutations in the hypercube (Q4944978)

A routing request \(R\) for a directed graph \(D\) is directed multigraph with the same vertex set. \(R\) can be satisfied if there is a system of arc-disjoint paths in \(D\) representing the arcs of \(R\). \(D\) is \((h\)-\(k)\)-rearrangeable if every routing request with maximal outdegree \(h\) and maximal indegree \(k\) can be satisfied. The \(d\)-dimensional directed symmetric hypercube (with one arc in each direction between each pair of adjacent vertices) is not (2-1)-rearrangeable for all \(d \geq 3\) but (1-1)-rearrangeable for \(d \leq 4\). The latter result gives the answer to Szymanski's conjecture for dimension 4 [Proc. Internat. Conf. on Parallel Processing, vol. I, 103-110 (1989)]. For the entire collection see [Zbl 0929.00074].