Mutiplicativity of oriented cycles (Q1322018): Difference between revisions

A homomorphism from a digraph \(G\) to a digraph \(H\) is a mapping \(f: V(G)\to V(H)\) such that \(gg'\in E(G)\) implies \(f(g)f(g')\in E(H)\); where such a homomorphism exists one writes \(G\to H\), otherwise \(G\not\to H\). The categorical product of digraphs \(G\) and \(H\), denoted by \(G\times H\), has vertex set \(V(G)\times V(H)\), and edge set \(\{(g,h)(g',h'): gg'\in E(G)\), \(hh'\in E(H)\}\). A digraph \(D\) is multiplicative if, for any digraphs \(G\), \(H\), \(G\times H\not\to D\) whenever both \(G\not\to D\) and \(H\not\to D\). The present paper continues a study begun by the second author [On the nonmultiplicativity of oriented cycles, SIAM J. Discrete Math. 5, No. 2, 207-218 (1992; Zbl 0773.05074)] concerned with a class of orientations of an \(n\)-cycle, here called \({\mathcal C}\)-cycles. ``In this paper, we shall\dots show\dots that all \({\mathcal C}\)-cycles are\dots multiplicative. Thus we achieve a classification of oriented cycles according to their being or not being multiplicative; this classification turns out to be surprisingly complex''.