10
$\begingroup$

We say that a simple, undirected graph $G=(V,E)$ has the fixed point property (FPP) if for every graph homomorphism $f:G\to G$ there is a vertex $v\in V$ such that $f(v) = v$.

If $G$ has the FPP, does $G\times G$ have the FPP (where by $\times$ we denote the categorical product of graphs)?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ In a homomorphism do you allow two neighbors to be mapped to the same vertex? $\endgroup$
    – YCor
    Commented Oct 27, 2017 at 14:01
  • $\begingroup$ Btw you could ask whether when $G,H$ have FPP then so does $G\times H$. $\endgroup$
    – YCor
    Commented Oct 27, 2017 at 14:02
  • $\begingroup$ That's right, but that question is maybe even more difficult? But I might change the question, yours looks actually more natural because it is more general. It is the better question in fact. $\endgroup$
    – Dominic van der Zypen
    Commented Oct 27, 2017 at 17:46
  • 3
    $\begingroup$ The version with $G\times H$ is listed as an open question in "The Fixed Vertex Property for Graphs" by Schröder: link.springer.com/article/10.1007/s11083-014-9337-5. $\endgroup$
    – MTyson
    Commented Oct 27, 2017 at 18:25
  • $\begingroup$ It's more difficult if you expect a positive answer, but easier if you expect a counterexample. $\endgroup$
    – YCor
    Commented Oct 27, 2017 at 19:44

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .