6
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\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, 2013 at 17:16
  • 1
    $\begingroup$ Do you mean $G_2(32)$ instead of $G_{32}(2)$? $\endgroup$
    – verret
    Jan 16, 2013 at 17:49
  • $\begingroup$ @verret: Yes, of course! Thanks for spotting the error. I corrected the question. $\endgroup$
    – Felix Goldberg
    Jan 16, 2013 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, 2013 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, 2013 at 14:11

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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