1
$\begingroup$

Sabidussi proved that if a finite graph $X$ is isomorphic to a Cartesian product of connected graphs $X_1,\ldots,X_m$ which are pairwise relatively prime with respect to Cartesian multiplication, then the automorphism group of $X$ is isomorphic to the direct product of the automorphism groups of $X_1,\ldots,X_m$.

My question is: is there a version of this theorem where one replaces the automorphism group of $X$ by the endomorphism monoid of $X$ (defined as the set of graph morphisms $X \mapsto X$ endowed with composition of maps) ?

Variation: let $\mathrm{hom}(X,Y)$ be the set of graph morphisms from the graph $X$ to the graph $Y$. Let $Z$ be a graph relatively prime to $X$ and $Y$; what is $\mathrm{hom}(X \times Z,Y \times Z)$ ?

$\endgroup$
2
  • 1
    $\begingroup$ Always a good idea to say what is meant by graph, product of graphs, and graph homomorphisms as such questions are sensitive to the various choices. $\endgroup$
    – YCor
    Commented Feb 22, 2019 at 14:51
  • $\begingroup$ @ChrisGodsil In this example, the factors are not relatively prime. $\endgroup$
    – verret
    Commented Mar 25, 2019 at 2:00

1 Answer 1

3
$\begingroup$

There is no such theorem for endomorphisms, assuming that by endomorphism you mean a map $f\colon V \to V$ such that $xy \in E \implies f(x)f(y) \in E$, and that by "version of this theorem" you mean something along the lines of "edges that come from a given factor must be mapped to edges coming from the same factor".

If all factors are bipartite, then so is the product. Any bipartite graph admits an endomorphism onto any of its edges (by mapping one part of the bipartition to one endpoint, and the other part to the other endpoint). This clearly maps some edges to an edge from a different factor (assuming that neither of the factors is trivial).

EDIT: I should also say that I am assuming that Cartesian product refers to the one described here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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