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.
 A: This is meant to address the comments in response to my comment.  It also contains some
"shoot from the lip" analysis, so may help in forming an answer, even if I get some of it wrong.
It is not an answer however.  I am focusing purely on the case k=2 so that the sum of the
indices is a square implies an edge between the corresponding vertices.
The degree of vertex j is roughly sqrt(m+j) - sqrt(j), where m is the number of vertices.  Adding
vertices 33 and 34 adds two vertices of degree 3 to a graph that is (by assertion in the original
post) Hamiltonian, so I envision a big cycle of 32 vertices with two additional degree 3 vertices hanging from
it.  Further, the vertices are attached at vertices in the big cycle which are "neighboring" in the canonical ordering;
if enough of these points of attachment are neighboring in the cycle as well, then a larger cycle can be made from the existing cycle by removing two edges from the big cycle and grafting on the two vertices in a fashion
I won't describe here but is easily pictured by people experienced with this kind of problem.
For small m, one can't guarantee that the two pairs of edges always exist, but as m grows, one
may be able to give a guarantee of such a graft of two vertices: find integers a and b less than m such that
m+a+1 and m+b+1 are squares and 2a-1 and 2b-1 are also squares, and then one can graft m+1 and
m+2 on to the cycle for m vertices.
Gerhard "Circling The Squares? Not Impossible" Paseman, 2013.01.17
