# When is the direct product of two graph cores itself a core?

A graph homomorphism $f$ is a function $f : V(X) \to V(Y)$ such that if $uv \in E(X)$, then $f(u)f(v) \in E(Y)$. If such an $f$ exists, write $X \to Y$. $X$ and $Y$ are hom-equivalent if $X \to Y$ and $Y \to X$—write $\def\fromto{\leftrightarrow} X \fromto Y$. $X$ and $Y$ are hom-incomparable if $X \not\to Y$ and $Y \not\to X$.

The direct product $X \times Y$ of two graphs $X$ and $Y$ is defined by $V(X \times Y) = V(X) \times V(Y)$ and $(x,y) \sim (x',y')$ iff $x \sim x'$ and $y \sim y'$. The poset of hom-equivalence classes of graphs (under the ordering $\to$) forms a lattice with disjoint union $+$ as the join and $\times$ as the meet.

The hom-equivalence classes of (finite) graphs each have unique-up-to-isomorphism representatives called cores. Among other characterizations, $X$ is a core iff every endomorphism is an automorphism.

If $X$ and $Y$ are cores and $X \to Y$, then $X + Y \fromto Y$ and $X \times Y \fromto X$, so neither can be a core. However, if $X$ and $Y$ are connected hom-incomparable cores, it is easy to show $X + Y$ is also a core. More generally, if $X$ and $Y$ are (possibly disconnected) cores, $X+Y$ will be a core if each component of $X$ is hom-incomparable with each component of $Y$—equivalently, $X+Y$ is a core if $X$ and $Y$ are hom-incomparable cores that are "$+$-coprime".

If $X$ and $Y$ are cores, when is $X \times Y$ also a core? Is the condition that $X$ and $Y$ be hom-incomparable and $\times$-coprime sufficient?

As a related but more open-ended question, we have unique prime factorization on connected bipartite graphs in the graphs-with-loops (according to the Handbook of Product Graphs by Hammack, Imrich, and Klavžar, section 8.5) so we also have it for the connected cores; can this be extended to all cores, and do we require loops?

The motivation is to see how nicely the lattice structure of the hom-equivalence classes plays with cores. I have been unable to find references to this question anywhere.

I originally posted this question on math.SE, but brought it here upon the advice of a professor.

• Perhaps references  and  mentioned beneath $\bf S_n$ on page 92 of Duffus and Sauer, "Chromatic numbers and products," might be useful (as well as references  and  in that paper). – Tri Apr 20 '15 at 4:47
• Refined the hypothesis, as coprimality is not implied by hom-incomparability alone, but is necessary for preventing cases like $(A \times B) \times (A \times C) \leftrightarrow A \times B \times C$. This now raises questions about the factorizability of cores. – algorithmshark Apr 24 '15 at 9:36

Let $G$ and $H$ be hom-incomparable cores and let $f$ be an endomorphism of the product $G\times H$. Then $f$ cannot "mix" the two factors. Formally, $f$ cannot be of the form $f=(\varphi,\psi)$ where $\varphi: G\rightarrow G$ and $\psi:G\rightarrow H$ (or any of the other obvious ways to mix the morphisms up) since $G$ and $H$ are hom-incomparable. Thus $f$ must preserve adjacency "pointwise" in the sense that $f=(f_G, f_H)$ where $f_G :G\rightarrow G$ and $f_H :H\rightarrow H$ are morphisms of the factor cores. Since $G$ and $H$ are cores, both of these morphisms are automorphisms. Hence $f$ is an automorphism of $G\times H$ with inverse $f^{-1} = (f_G^{-1}, f_H^{-1})$, so $G\times H$ is a core.
• Can you be more precise with what you mean by "the form $f = (\varphi,\psi)$ where $\varphi : G \to G$ and $\psi : G \to H$"? Specifically, which part of $V(G) \times V(H)$ is the domain for each "part" of the map? – algorithmshark Apr 19 '15 at 17:58
• By this example I meant something like this: if $(g,h)\in V(G\times H)$ then $f((g,h)) = (\varphi(g), \psi(g))$. In this sense $f$ takes pairs in $V(G\times H)$ to other pairs in $V(G\times H)$, but only really sees the first coordinate. There are other possibilities e.g. if you had morphisms $\alpha:G\leftrightarrows H:\beta$ then you could define $f((g,h)) = (\beta(h), \alpha(g))$... The point is since your cores are incomparable you cannot ever mix up your maps like this, so every endomorphism of the product must look like a product of endomorphisms of the factors. Does this help? – Alex Saad Apr 19 '15 at 18:22
• This does not seem exhaustive. Each endomorphism of $G \times H$ is of the form $(g,h) \mapsto (\varphi(g,h),\psi(g,h))$, and I don't immediately see why there isn't a nontrivial way to combine $g$ and $h$. – algorithmshark Apr 19 '15 at 19:01
• In addition to the comment by @Tri above, you may find the following n-Category Cafe post useful: golem.ph.utexas.edu/category/2014/12/… Endomorphisms of $G\times H$ correspond bijectively to morphisms $G\rightarrow (G\times H)^H$ (and symmetrically to morphisms $H\rightarrow (G\times H)^G$) into graphs $(G\times H)^H$ which are exponential objects in the category of graphs (although you will have to relax your notion of graph slightly to allow some graphs to have loops - the post discusses this). continued... – Alex Saad Apr 20 '15 at 9:25