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.

  • $\begingroup$ Perhaps references [10] and [11] mentioned beneath $\bf S_n$ on page 92 of Duffus and Sauer, "Chromatic numbers and products," might be useful (as well as references [5] and [6] in that paper). $\endgroup$ – Tri Apr 20 '15 at 4:47
  • $\begingroup$ 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. $\endgroup$ – algorithmshark Apr 24 '15 at 9:36

Nice question! I believe the following provides a proof that hom-incomparability is a sufficient condition for the product to be a core.

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.

  • $\begingroup$ 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? $\endgroup$ – algorithmshark Apr 19 '15 at 17:58
  • $\begingroup$ 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? $\endgroup$ – Alex Saad Apr 19 '15 at 18:22
  • $\begingroup$ 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$. $\endgroup$ – algorithmshark Apr 19 '15 at 19:01
  • $\begingroup$ Good point. I've thought hard and can't see how to fix this short of the vague idea that "nontrivial combinations" ought to correspond to a homomorphism between the cores, giving a contradiction. But I cannot find a way to define a hom that works. $\endgroup$ – Alex Saad Apr 20 '15 at 9:21
  • $\begingroup$ 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... $\endgroup$ – Alex Saad Apr 20 '15 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.