Let $G$ be a Hamiltonian graph and $K_n$ the complete graph on $n$ vertices. Are there results about that the graph $G\times K_n$ is Hamiltonian or not? Thanks.
Asked
Active
Viewed 23 times
0
-
Remind me ... a graph is Hamiltonian if it has a Hamiltonian path or cycle. If $n$ is even then it is easy. But maybe you could tell us what you know so far ? – Donald Splutterwit Jan 30 '20 at 15:20
-
Yes, I consider a graph Hamiltonian if it has a Hamiltonian cycle. About Hamintonicity of a tensor product I have found this paper and it is only that I know about: https://core.ac.uk/download/pdf/82211350.pdf. Actually, I'm only interested in the case when n is a prime number. – MarY Jan 30 '20 at 15:56
-
In that paper, did you notice Lemma 2 on page 254? It would seem to cover everything you are interested in except for the case $n = 2$, which shouldn't be hard to figure out. – Paul Sinclair Jan 31 '20 at 00:27
-
@PaulSinclair, thanks, I was so stupid. – MarY Jan 31 '20 at 07:57
-
Don't be too hard on yourself - it's easy to miss the forest for all the trees. I said the $n=2$ case should be simple, but it seems to be more complicated than I expected. But the rest of the paper should allow you to answer it as well. – Paul Sinclair Jan 31 '20 at 16:09