# Is graph Isomorphism distributive on Cartesian Product of graphs?

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.

• What do you mean by $\operatorname{Isomorph}(G)$? this isn't standard notation. (Also, "we know that $G \mathbin\square H$" makes about as much sense to me as "we know that $17$".) Apr 18, 2018 at 23:18
• Normally graph isomorphism indicates something a graph is isomorphic to. Apr 18, 2018 at 23:20
• Are you asking $G \simeq J \wedge H \simeq K \implies G \square H \simeq J \square K$? Apr 18, 2018 at 23:37
• Well, I consulted with my professor and notation is pi where pi is a permutation of vertices applied (which yield a bijection implying an isomorph). @Misha Lavrov Apr 21, 2018 at 8:47
• It took a while to understand your notation and yes, that's exactly what I am after @Q the platypus. Props for the name. Apr 21, 2018 at 8:47

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

• Is it possible to get pi or kappa given I know G, H pi(G), and kappa(H)? Or is it like integer factorization? Apr 22, 2018 at 9:17
• It depends on what "know G" and "know pi(G)" means. If you just have two isomorphic graphs, there may be distinct isomorphisms between them. (But if you have, say, G and pi(G) drawn identically with vertices relabelled, then you can easily deduce pi.) Apr 22, 2018 at 9:21
• I am considering an adjacency matrix representation of the graphs, unlabelled of course. Now, I have adj. matrix forms of G,H, pi(G) \mathbin\square kappa(H). Is it now possible to get unique pi and kappa? Is it possible to get pi(G) and kappa(H) from G,H, pi(G) \mathbin\square kappa(H) Apr 22, 2018 at 10:16
• If you don't mind me asking, how do I generate a graph with no automorphs at all and I am writing a paper and can I cite you as a reference? If so, how? Apr 22, 2018 at 10:31
• If $G \Box H$ has a unique isomorphism with $\pi(G) \Box \kappa(H)$, when we can compute it and deduce $\pi$ and $\kappa$. Otherwise, it might not be possible to deduce $\pi$ and $\kappa$; they might not even be unique (which would happen if $G$ or $H$ has an automorphism). Apr 22, 2018 at 10:31