2-1 routing requests in the hypercube

Let H n be the directed symmetric n-dimensional hypercube. We consider in H n the so-called 2-1 routing requests, where any vertex of H n can be used twice as a source, but only once as a target. In order to disprove the Szymanskiʹs conjecture for a given dimension n, it is necessary to obtain 2-1 routing requests in H n − 1 that cannot be routed. Baudon, G. Fertin, and I. Havel, Routing permutations in the hypercube, Discrete Applied Mathematics 113 (1) (September 2001) 43–58], we showed that in H 3 there exists exactly two routing requests which cannot be routed, nonequivalent by automorphism. Moreover, we showed that for one of them, called g 3 , it is possible to extend it for any dimension n ≥ 3 in a 2-1 routing request g n that cannot be routed in H n . ering distances between sources and their respective target in g 4 , we have, using a computer, studying all the 2-1 routing requests of H 4 having similar properties on distances, in order to find more not routable 2-1 routing request in dimension 4 and higher. We have by this way obtained several (a dozen) non routable 2-1 rout- ing requests in H 4 . Some of them may be extended to higher dimensions, but not all.