Induced subgraphs of $\text{Exp}(G, K_2)$

Question

If $G, H$ are simple, undirected graphs, we define the exponential graph $\text{Exp}(G,H)$ to be the following graph:

• the vertex set is the set of all maps $f:V(G)\to V(H)$
• two maps $f\neq g: V(G)\to V(H)$ form an edge if and only if whenever $\{v,w\}\in E(G)$ then $\{f(v), g(w)\}\in E(H)$.

If $G$ is any simple, undirected graph, finite or infinite, is there a graph $G'$ such that $G$ is isomorphic to an induced subgraph of $\text{Exp}(G', K_2)$?

Answer 1

In the sequel we allow $\mathrm{Exp}(\cdot, \cdot)$ to have loops, then the only induced subgraphs of $\mathrm{Exp}(G', K_2)$ are disjoint unions of isolated vertices, complete graphs with a loop on each vertex (denote such a graph $\overline{K_n})$ and complete bipartite graphs.

First, consider a non-empty connected simple graph $G'$. For $G'$ with a single vertex we have $\mathrm{Exp}(G', K_2) = \overline{K_2}$. For $G'$ with at least two vertices we must have that each vertex of $\mathrm{Exp}(G', K_2)$ has degree at most one; indeed, consider $f, g, h: V(G') \to V(K_2)$ such that $g, h$ are neighbours of $f$ in $\mathrm{Exp}(G', K_2)$. For any $v \in V(G')$ consider an adjacent edge $vu$, we must have $g(v) \neq f(u) \neq h(v)$, hence $g = h$. Thus, $\mathrm{Exp}(G', K_2)$ consists of isolated vertices, disjoint loops and edges.

For an arbitrary $G'$, $\mathrm{Exp}(G', K_2)$ is the tensor product of $\mathrm{Exp}(\cdot, K_2)$ of connected components of $G'$. A tensor product of (disjoint unions of) isolated vertices, loops and edges still consists of isolated vertices, disjoint loops and edges. A tensor product of several copies of $\overline{K_2}$ is $\overline{K_{2^n}}$. Finally, a tensor product of $\overline{K_n}$ with $K_2$ is $K_{n, n}$. It follows that all connected components of $\mathrm{Exp}(G, K_2)$ are isolated vertices, $\overline{K_n}$ or $K_{n, n}$.