0
$\begingroup$

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\}$?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Martin Rubey
    Commented Oct 30, 2023 at 11:50

1 Answer 1

Reset to default
3
$\begingroup$

If I understand it correctly, there is a counterexample on page 1518 of this paper. Then again, I might not have read it carefully enough.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ If I understand it correctly, the simplest counterexample is taking the product with a point (a graph with one vertex and no edges). This removes all edges from a graph and thus there cannot be a unique decomposition into irreducible factors. $\endgroup$
    – HenrikRüping
    Commented Oct 30, 2023 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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