# Product decomposition for finite graphs

We say that a finite, simple, undirected graph $$G = (V,E)$$ is (product-)irreducible if it is connected and there are no graphs $$A,B$$ such that $$G\cong A\times B$$ (where $$\times$$ denotes the categorical product of graphs).

Suppose that $$G_i, H_j$$ are irreducible graphs, where $$i \in \{1,\ldots,n\}$$ and $$j\in\{1,\ldots,m\}$$ for some positive integers $$m,n\in\mathbb{N}$$, and suppose that $$\prod_{i=1}^nG_i \cong \prod_{j=1}^m H_j.$$

Questions. Do we have $$m=n$$? And if yes, is there a bijection $$\varphi:\{1,\ldots,n\}\to\{1,\ldots,n\}$$ such that $$G_i \cong H_{\varphi(i)}$$ for all $$i\in \{1,\ldots,n\}$$?

• Doesn't "If a graph can be represented as a tensor product, then there may be multiple different representations (tensor products do not satisfy unique factorization) but each representation has the same number of irreducible factors. Imrich (1998) gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph." answer your question? Commented Oct 30, 2023 at 11:50