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