# Representing graphs by $\text{Hom}$-graphs

Let $$G, H$$ be simple, undirected graphs. A graph homomorphism from $$G$$ to $$H$$ is a map $$f:V(G)\to V(H)$$ such that whenever $$\{v,w\}\in E(G)$$ then $$\{f(v), f(w)\}\in E(H)$$. Let $$\text{Hom}(G,H)$$ be the set of graph homomorphisms from $$G$$ to $$H$$. Note that it is often the case that $$\text{Hom}(G,H)=\emptyset$$, for instance, when $$\chi(G) > \chi(H)$$.

There is a natural way to make $$\text{Hom}(G,H)$$ into a graph: we say $$f, g\in \text{Hom}(G,H)$$ form an edge if and only if $$\{f(v),g(v)\}\in E(H)$$ for all $$v\in V$$.

Question. Given a simple, undirected graph $$G$$, are there $$H_1, H_2$$ graphs with $$|V(H_1)|>1$$ and $$G \cong \text{Hom}(H_1,H_2)$$?

• Isn't the usual way to define edges between graph homomorphisms to require an edge between $\{f(v), g(v)\}$ for any $v$? Dec 9, 2022 at 15:10
• (For example, with your definition, $\operatorname{Hom}(*, G)$ for the point graph $*$ is not $G$, but the complete graph on the vertices of $G$.) Dec 9, 2022 at 15:14
• @AchimKrause Thank you - you are right, I will change this! Dec 10, 2022 at 9:57

Let $$V(G),E(G)$$ be the vertex set and edge set of $$G$$. Take $$n>|V(G)|$$, and let $$K_n$$ be the complete graph on $$n$$ vertices. We take $$H_1=K_n$$ and $$H_2=K_n\times G$$ (the Cartesian product of graph).
Lemma: Let $$A,B$$ be graphs with the vertex sets are $$\{a_1,a_2,...a_k\},\{b_1,b_2,...,b_k\}$$, respectively, and $$A\times B$$ be their Cartesian product, so its vertex set is $$V(A\times B)=\{(a_i,b_j)|1\leq i\leq k,1\leq j\leq l\}$$. Let $$S\subset V(A\times B)$$, assume the induced graph in $$A\times B$$ by $$S$$ is a complete graph. Then either the set $$S$$ has the form $$\{(a_i,b_j)|b_j\in D\subset B\}$$ for some $$1\leq i\leq k,D\subset B$$ or $$\{(a_i,b_j)|a_i\in C\subset A\}$$ for some $$1\leq j\leq l,C\subset A$$.
Proof: The case $$|S|=1$$ is trivial. Let $$(a_{i_1},b_{j_1}),(a_{i_2},b_{j_2})$$ be two different vertices in $$S$$. We have they are joined so either $$i_1=i_2$$ or $$j_1=j_2$$, not both because they are different vertices. Assume the first case then $$j_1\neq j_2$$, then consider the other vertex $$(a_i,b_j)$$ in $$S$$, because it is joined to $$(a_{i_1},b_{j_1}),(a_{i_2},b_{j_2})$$, the only case that happens is $$i=i_1=i_2$$, so $$S$$ has the first form. If $$j_1=j_2$$ then similar, $$S$$ has the second form.
By the choice of $$n$$, there is no graph homomorphism from $$K_n$$ to $$G$$, and by the lemma, all graph homomorphism $$f:K_n\rightarrow K_n\times G$$ have the form $$f_v(i)=(i,v)$$ for some $$v\in G$$, and it's easy to see that if $$v,w$$ are joind in $$G$$ if and only if $$f_v,f_w$$ are joined in $$\text{Hom}(K_n,K_n\times G)$$, so $$\text{Hom}(K_n,K_n\times G)\simeq G$$, as we want.