Consider a graph $G$. As usual, denote a path graph of length $n$ as $P_{n}$, and $\times$ is for Cartesian product of graph. If $G$ is Hamiltonian (ie. have a Hamiltonian cycle) then it is easy to prove that $G\times P_{n}$ is always Hamiltonian. The question is about when $G$ is not Hamiltonian. What are the possible value of $n$ such that $G\times P_{n}$ is Hamiltonian.

My attempt so far: the set of possible $n$ is closed under addition.

  • $\begingroup$ Are you searching for general $n$ or do you want to find $n$ depending on $G$? Also I assume $G$ should be connected, otherwise this is trivial. $\endgroup$ – mlk Jun 13 '14 at 21:37
  • $\begingroup$ Sorry I did not mention it, because though that it obvious, but the set of $n$ should depend on $G$. $\endgroup$ – Gina Jun 14 '14 at 1:01

Okay, I doodled around and can show, that this will not work for arbitrary graphs. Take $G$ to be the three pointed star $K_{1,3}$ with center vertex $c$ and "points" $a_1,a_2,a_3$. And let $P_n$ be the path with vertices $p_1,...,p_n$. Then $G\times P_n$ is not hamiltonian for any n, since the three vertices $(a_i,p_1)$ are all of degree 2 and connected to $(c,p_1)$. So any Hamiltonian cycle would have to use all of the edges belonging to those nodes including $((a_i,p_1),(c,p_1))$, so there are three edges in the cycle that have $(c,p_1)$ as a node, which is a contradiction.

  • $\begingroup$ Nice ! The same argument should work for $K_{1, m}$, any $m \geq 3$. $\endgroup$ – Manuel Lafond Jun 14 '14 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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