# Hamiltonian cycles in power-graphs

I've stumbled across a short note from 1993 where a nice question was asked: Suppose you take a graph with vertices $\{1,2,\ldots,n\}$ and connect $i,j$ by an edge if and only if $i+j$ is a $k$th power of some number. Call this graph $G_{k}(n)$. The authors of the note found that $G_{2}(32)$ is Hamiltonian (and that $32$ is the first $n$ for which $G_{2}(n)$ is Hamiltonian). They conjectured that $G_{2}(n)$ is Hamiltonian for all $n \geq 32$.

I found no citations of this paper so I wonder if someone has attacked this question since.

UPDT: There is some discussion of the $k=3$ case here, from an "elementary" point of view.

-
It seems reasonable that G2(n) is Hamiltonian would imply G2(n+2) also is. I don't know how else to attack it. Gerhard "Ask Me About System Design" Paseman, 2013.01.16 – Gerhard Paseman Jan 16 '13 at 17:16
Do you mean $G_2(32)$ instead of $G_{32}(2)$? – verret Jan 16 '13 at 17:49
@verret: Yes, of course! Thanks for spotting the error. I corrected the question. – Felix Goldberg Jan 16 '13 at 22:01
Dear Gerhard, Can you explain why you think this implication is reasonable? I don't see it myself (but I don't know much about the topic). Moreover, the data in the linked note show that there exists values of $n$ such that G2(n+2) has less hamiltonian cycles than G2(n). – Olivier Jan 17 '13 at 9:40
One must wonder if this has to do with Paley graphs: Paley graph is defined similarly, but over a finite field, and there is a edge iff the difference is a square in the field. They are known to be Hamiltonian. – Ami Paz Jan 17 '13 at 14:11