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

$\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$ Feb 26, 2015 at 5:05
  • $\begingroup$ Yes, excuse the sloppiness. Fixed. $\endgroup$ 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$ 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$ Feb 26, 2015 at 5:32

1 Answer 1

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.

$\endgroup$

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.