Szymanski's conjecture
Introduction Routing a permutation of the doubly-directed cube graphIn mathematics, '''Szymanski's conjecture''', named after , states that every permutation on the ''n''-dimensional doubly directed hypercube graph can be routed with edge-disjoint paths. That is, if the permutation σ matches each vertex ''v'' to another vertex σ(''v''), then for each ''v'' there exists a path in the hypercube graph from ''v'' to σ(''v'') such that no two paths for two different vertices ''u'' and ''v'' use the same edge in the same direction.Through computer experiments it has been verified that the conjecture is true for ''n'' ≤ 4 . Although the conjecture remains open for ''n'' ≥ 5, in this case there exist permutations that require the use of paths that are not shortest paths in order to be routed .
References *.*. *.