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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .