3
$\begingroup$

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

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

1 Answer 1

1
$\begingroup$

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.

$\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.