I've stumbled across a [short note from 1993][1] 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][2], from an "elementary" point of view.


  [1]: http://pefmath2.etf.rs/files/113/807.pdf
  [2]: http://www.primepuzzles.net/puzzles/puzz_311.htm