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.

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Jan 16 '13 at 17:16
  • 1
    $\begingroup$ Do you mean $G_2(32)$ instead of $G_{32}(2)$? $\endgroup$ – verret Jan 16 '13 at 17:49
  • $\begingroup$ @verret: Yes, of course! Thanks for spotting the error. I corrected the question. $\endgroup$ – Felix Goldberg Jan 16 '13 at 22:01
  • 1
    $\begingroup$ 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). $\endgroup$ – Olivier Jan 17 '13 at 9:40
  • 2
    $\begingroup$ 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. $\endgroup$ – Ami Paz Jan 17 '13 at 14:11

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.