3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.