Cancellation of digraphs over the direct product

In 1971 Lovász proved the following cancellation law concerning the direct product of digraphs. If A , B and C are digraphs, and C admits no homomorphism into a disjoint union of directed cycles, then A × C ≅ B × C implies A ≅ B . On the other hand, if such a homomorphism exists, then there are pairs A ⁄ ≅ B for which A × C ≅ B × C . This gives exact conditions on C that govern whether cancellation is guaranteed to hold or fail. nresolved was the question of what conditions on A (or B ) force A × C ≅ B × C ⟹ A ≅ B , or, more generally, what relationships between A and C (or B and C ) guarantee this. Even if C has a homomorphism into a collection of directed cycles, can there still be restrictions on A and C that guarantee cancellation? We characterize the exact conditions. a construction called the factorial A ! of a digraph A . Given digraphs A and C , the digraph A ! carries information that determines the complete set of solutions X to the digraph equation A × C ≅ X × C . We state the exact conditions under which there is only one solution X (namely X ≅ A ) and that is the situation in which cancellation holds.