# Making a graph Hamiltonian by stacking it up

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.

• 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. – mlk Jun 13 '14 at 21:37
• Sorry I did not mention it, because though that it obvious, but the set of $n$ should depend on $G$. – 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.
• Nice ! The same argument should work for $K_{1, m}$, any $m \geq 3$. – Manuel Lafond Jun 14 '14 at 0:48