Publikace na Matematicko-fyzikální fakulta |
2017
Abstrakt
We study the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph $\Cay(M, B)$ to another Cayley graph $\Cay(M', B')$ then every graph with $(M,B)$-flow has $(M',B')$-flow. This conjecture was originally motivated by the flow-tension duality.
We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of oriented cycle double cover with a small number of cycles.