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

Question

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)$?

Answer 1

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.