Problems on routing bounded distance assignments in hypercubes

The problem of whether an assignment in the hypercube H_n, where the distance from the source to the destination is bounded, can be routed with minimum distance and bounded congestion is considered. It is shown that this is so, if assignments of given “type” can be so routed. Of particular interest is whether for distance 3 and fixed type, minimum distance and congestion 1 can be obtained. This is shown for n⩽6; on the other hand the method suggests possible counter examples. Also, it is shown that distance 2 permutations in H₄ have congestion 1 routings