7
$\begingroup$

Given two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$, the tensor product of $G$ and $H$ is the graph $G \times H = (V,E)$, where $V=V_1 \times V_2$ is the Cartesian product of the $V_i$ and $ (u,v) \ E \ (u',v') \Leftrightarrow u E_1 u' \wedge v E_2 v'$.

Is anyone aware of a characterization of which $G,H$ give rise to a planar tensor product $G \times H$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you mean $(u,v) \ E \ (u',v') \Leftrightarrow u E_1 u' \wedge v E_2 v'$ (or, equivalently, $v$ and $u$ in $(u,v) \ E \ (u',v') \Leftrightarrow u E_1 u' \wedge v E_2 v'$)? $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 26, 2015 at 5:05
  • $\begingroup$ Yes, excuse the sloppiness. Fixed. $\endgroup$
    – Charlene McAllistar
    Commented Feb 26, 2015 at 5:11
  • 2
    $\begingroup$ I'm no graph theorist. And probably you already know this, but Exercises 5.15-5.17 on pages 59 and 60 of the Handbook of Product Graphs (2nd edition) seem to characterize such $G$ and $H$ for some special cases. $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 26, 2015 at 5:18
  • 1
    $\begingroup$ Also, because a recent paper published in 2009 (hal.archives-ouvertes.fr/hal-00387303/document) that deals with this question has only 3 citations on google scalar (none of which seem to solve this problem), and also because the handbook published in 2011 doesn't have a complete solution to this seemingly natural question, it's likely still open, although you should ask a graph theorist to be sure. $\endgroup$
    – Yuichiro Fujiwara
    Commented Feb 26, 2015 at 5:32

1 Answer 1

Reset to default
6
$\begingroup$

Yuichiro Fujiwara's comments seem to answer the question in full so I am making it an answer. I quote below from Kronecker products and local joins of graphs by M. Farzan and D. A. Waller, Can. J. Math. 29 (1977), 255–269.

By a 1-contraction of $G$ we mean the removal from $G$ of each vertex of degree 1 (and its incident edge).

5.3 THEOREM. Let $G_1$ and $G_2$ be connected graphs with more than four vertices. Then $G_1\times G_2$ is planar if and only if either

(i) one of the graphs is a path and the other one is 1-contractible to a path or a circuit, or

(ii) one of them is a circuit and the other is 1-contractible to a path.

This leaves open only the case in which at least one of the graphs has fewer than five vertices. Proposition 5.4, which I won't bother reproducing here, covers some of these cases. Beaudou et al. addresses the case $G=K_2$. A complete solution appears to be still an open problem.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .