5
$\begingroup$

For simple, undirected graphs $G, H$, let $G\times H$ denote the categorical product, or tensor product, of $G$ and $H$.

Let us call a graph $G = (V,E)$ (product-)reducible if there are graphs $G_i = (V_i, E_i)$ with $|V_i| > 1$ for $i = 1,2$ and $G \cong G_1 \times G_2$. We call $G=(V,E)$ properly irreducible if $|V|> 1$ and $G$ is not reducible.

Question. Are there connected properly irreducible graphs $G_i, H_i$ (possibly infinite) for $i=1,2$ such that $G_1\times G_2 \cong H_1\times H_2$, but $G_i \not\cong H_j$ for all $i,j\in\{1,2\}$?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ An infinite number of isolated vertices is a tensor product in infinitely many different ways. I guess you want to exclude this example? $\endgroup$
    – Tony Huynh
    Commented Jul 4, 2022 at 14:28
  • $\begingroup$ Right - thanks - will do! $\endgroup$
    – Dominic van der Zypen
    Commented Jul 4, 2022 at 22:08
  • 1
    $\begingroup$ $K_{2!\omega}\times K_{3!c}\cong K_{3!\omega}\times K_{2!c}$ where $c$ is a continuum. Do you want your graphs to be at most countable? $\endgroup$
    – Ilya Bogdanov
    Commented Jul 16, 2022 at 17:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .