Is graph Isomorphism distributive on Cartesian Product of graphs?

Question

We know that $G \mathbin\square H$ = $H \mathbin\square G.$ My question is that if $\mathbin\pi(G) \mathbin \square \mathbin\pi(H)$ same as $G \mathbin\square H$? How do I approach this problem. I haven't got a clue.

Answer 1

Below $\pi$ and $\kappa$ are bijective maps with domains $V(G)$ and $V(H)$, respectively.

---

By definition of a Cartesian product graph, $\pi(G) \Box \kappa(H)$ is the graph with:

• vertex set $V(\pi(G)) \times V(\kappa(H))$, and
• edges between distinct $(\pi(g),\kappa(h))$ and $(\pi(g'),\kappa(h'))$ if and only if $\pi(g)=\pi(g')$ or $\kappa(h)=\kappa(h')$.

To see this is isomorphic to $G \Box H$, we apply an isomorphism to $G \Box H$: $$(g,h) \mapsto (\pi(g),\kappa(h)) \tag{*}.$$ After this transformation, the graph has the vertex set $V(\pi(G)) \times V(\kappa(H))$, and adjacency is defined between distinct vertices $(\pi(g),\kappa(h))$ and $(\pi(g'),\kappa(h'))$ if and only if $\pi(g)=\pi(g')$ or $\kappa(h)=\kappa(h')$.

Thus $(^*)$ is an isomorphism from $G \Box H$ to $\pi(G) \Box \kappa(H)$.