In mathematics, Szymanski's conjecture, named after , states that every

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

on the ''n''-dimensional doubly

directed Direct may refer to: Mathematics * Directed set, in order theory * Direct limit of (pre), sheaves * Direct sum of modules, a construction in abstract algebra which combines several vector spaces Computing * Direct access (disambiguation), a ...

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has ...

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 path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

s in order to be routed .

References

*. *. *. Conjectures Unsolved problems in graph theory Network topology {{topology-stub