Let us call a simple undirected graph $G$ non-traceable if there is no Hamiltonian path in $G$.
Are there connected non-traceable graphs $G, H$ such that the Cartesian product $G{\scriptsize\square} H$ has a Hamiltonian path?
$\begingroup$
$\endgroup$
2
asked Sep 8, 2017 at 8:57
-
$\begingroup$ @bof thank you for providing the terminology! $\endgroup$– Dominic van der ZypenCommented Sep 8, 2017 at 11:58
-
$\begingroup$ Very nice @bof - if it checks out, can you put it in an answer? $\endgroup$– Dominic van der ZypenCommented Sep 8, 2017 at 13:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, this is possible and one of the smallest counterexamples is on 6 vertices.
Let $G$ be the graph with edges
[(0, 1), (0, 2), (0, 'A'), (1, 2), (1, 'B'), (2, 'C')]
This is essentially $K_3$ with 3 new vertices adjacent to each of the vertices of the $K_3$. The cartesian square $G\square G$ has hamiltonian path and even hamiltonian cycle.
