2
$\begingroup$

Let $H, K$ be simple, undirected graphs, and let $\text{Hom}(H,K)$ the collection of graph homomorphisms $f: H\to K$. (Note that $\text{Hom}(H,K)$ might be empty.) For $f,g\in \text{Hom}(H,K)$ we say that they form an edge if $\{f(v),g(v)\}\in E(K)$ for all $v\in V(H)$ (which implies $f\neq g$ if $V(H) \neq \emptyset$). With this construction, we make $\text{Hom}(H,K)$ into a simple, undirected graph.

Given any simple, undirected graph $G$, are there simple, undirected graphs $H, K$ such that $|V(H)|>1$ and $G$ is isomorphic to an induced subgraph of $\text{Hom}(H,K)$?

Improve this question
$\endgroup$
3
  • $\begingroup$ Let H be a Cartesian product of G and K. I would think G would be a subgraph of the homomorphism graph. Gerhard "Turn Each Map Into Vertex" Paseman, 2019.12.09. $\endgroup$
    – Gerhard Paseman
    Commented Dec 9, 2019 at 15:57
  • 2
    $\begingroup$ I assume the requirement $|V(H)|>1$ is to rule out choosing $H=K_1$ and $K=G$. But instead one could let $H=K_2$ and $K$ be the join $G+G$ of two disjoint copies of $G$. $\endgroup$
    – Gabe Conant
    Commented Dec 9, 2019 at 17:20
  • $\begingroup$ Thanks for your comments! If one of you can post their comment as an answer, we can close this thread $\endgroup$
    – Dominic van der Zypen
    Commented Dec 10, 2019 at 4:05

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .