Puneet Varma (Editor)

Szymanski's conjecture

Updated on
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Covid-19

In mathematics, Szymanski's conjecture, named after Ted H. Szymanski (1989), 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 (Baudon, Fertin & Havel 2001). 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 (Lubiw 1990).

References

Szymanski's conjecture Wikipedia


Similar Topics
Mianne Bagger
David Fusitua
Frank Ryder
Topics
 
B
i
Link
H2
L