Szymanski's conjecture
Encyclopedia
In 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 . For n ≥ 5 there exist permutations that require the use of paths that are not shortest paths in order to be routed .
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
on the n-dimensional doubly directed
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
hypercube graph can be routed with edge-disjoint paths
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
. 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 . For n ≥ 5 there exist permutations that require the use of paths that are not shortest paths in order to be routed .