Szymanski's conjecture
{{unsolved|mathematics|Can every permutation on the n-dimensional doubly directed hypercube graph be routed with edge-disjoint paths?}}
In mathematics, Szymanski's conjecture, named after {{harvs|first=Ted H.|last=Szymanski|year=1989|txt}}, 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 {{harv|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 {{harv|Lubiw|1990}}.
References
- {{citation
| last1 = Baudon | first1 = Olivier
| last2 = Fertin | first2 = Guillaume
| last3 = Havel | first3 = Ivan
| doi = 10.1016/S0166-218X(00)00386-3
| issue = 1
| journal = Discrete Applied Mathematics
| pages = 43–58
| title = Routing permutations and 2-1 routing requests in the hypercube
| volume = 113
| year = 2001| doi-access =
}}.
- {{citation
| last = Lubiw | first = Anna | authorlink = Anna Lubiw
| doi = 10.1016/0020-0190(90)90106-8
| issue = 2
| journal = Information Processing Letters
| pages = 57–61
| title = Counterexample to a conjecture of Szymanski on hypercube routing
| volume = 35
| year = 1990}}.
- {{citation
| last = Szymanski | first = Ted H.
| contribution = On the Permutation Capability of a Circuit-Switched Hypercube
| location = Silver Spring, MD
| pages = 103–110
| publisher = IEEE Computer Society Press
| title = Proc. Internat. Conf. on Parallel Processing
| volume = 1
| year = 1989}}.
Category:Unsolved problems in graph theory
{{graph-stub}}
{{topology-stub}}