On the Nonmultiplicativity of Oriented Cycles
Huishan Zhou · SIAM Journal on Discrete Mathematics · 1992
Graph homomorphism is an edge-preserving mapping from the vertex set of a graph to the vertex set of another graph, which is the generalization of graph coloring. A graph is multiplicative if the product of two graphs cannot be homomorphically mapped to it whenever the two factor graphs also cannot. The research of multiplicativity can be traced back to the mid-1960s, and has become active again in the past five years. There are some partial results about the multiplicativity of oriented cycles. The so-called even-deleting operation is now explored to prove that after implementing an even-deleting operation to a core-oriented cycle, both the resulting cycle and the original cycle are nonmultiplicative if the resulting cycle is not a special type of basic cycle. Finally, this paper proves that almost all oriented cycles are nonmultiplicative.