Multiplicativity of acyclic digraphs Original Research Article

A homomorphism of a digraph to another digraph is an edge preserving vertex mapping. A digraph W is said to be multiplicative if the set of digraphs which cannot be homomorphically mapped to W is closed under categorical product. We discuss the necessary conditions for a digraph to be multiplicative. Our main result is that almost all acyclic digraphs which have a Hamiltonian path are nonmultiplicative. We conjecture that almost all digraphs are nonmultiplicative.