Multiplicative graphs and semi-lattice endomorphisms in the category of graphs (Q2573651)

The categorical product of graphs \(G\) and \(H\) is a graph \(G\times H\) where \(V(G\times H)=\{(u,v)\mid u\in V(G),\,v\in V(H) \}\) and \(E(G\times H)=\{\{(u,v),(t,w)\}\mid \{u,t\}\in E(G),\,\{v,w\}\in E(H)\}\). A graph \(K\) is called multiplicative if a homomorphism from \(G\times H\) to \(K\) for graphs \(G\) and \(H\) implies the existence of a homomorphism from \(G\) to \(K\) or from \(H\) to \(K\). For a rational \(r=\frac kd\geq 2\) where \(k\geq 2\) and \(d\geq 1\) are relatively prime, the circulant graph \(K_r\) is the graph such that \(V(K_r)=\mathbb Z_k\) and \(E(K_r)=\{\{i,j\}\mid i,j\in \mathbb Z_k,\,d\leq | j-i| \leq k-d\}\). The main result says that a circulant graph \(K_r\) is multiplicative whenever \(2\leq r<4\). The proof is based on operators \(\mathbb P_3\) and \(\mathbb P_3^{-1}\) where for a graph \(G\), \( \mathbb P_3(G)\) is a graph such that \(V(\mathbb P_3(G))=V(G)\) and \(E(\mathbb P_3(G))=\{\{u,v\}\mid\) there exist \(x,y\in V(G)\text{ \;with } \{u,x\},\{x,y\},\{y,v\}\in E(G)\}\). It is proved that a graph \(G\) is multiplicative if and only if \(\mathbb P_3^{-1}(G)\) is multiplicative.