9
$\begingroup$

Let $G(n)$ be the graph whose vertices are the positive integers $1,2,3,4, \ldots, n$ two of which are joined by an edge if their sum is a square. Is the diameter of this graph 4 for all sufficiently large $n$?

$\endgroup$
  • 4
    $\begingroup$ Freddy Barrera has verified that G(194) is the first time G(n) has diameter 4. He conjectures that the diameter is 4 for all n > 328. $\endgroup$ – Bernardo Recamán Santos Apr 4 '15 at 2:08
  • 1
    $\begingroup$ Do you know any argument showing that the diameter can't be 3 for sufficiently large $n$? $\endgroup$ – Anthony Quas Apr 4 '15 at 6:50
  • 1
    $\begingroup$ For all n from 329 to 7000 the diameter is 4. Further, the eccentricity of vertex n in G(n) is 4 for all n from 243 to 7000. $\endgroup$ – user48028 Apr 4 '15 at 7:36
  • 1
    $\begingroup$ I wonder how large the clique number of this graph gets? The first K4 I see is at n=6724 (the vertices are 2, 167, 674, and 6722). There may be smaller ones. $\endgroup$ – user48028 Apr 4 '15 at 9:17
  • 1
    $\begingroup$ Finding such cliques is problem D15 in Richard Guy´s Unsolved Problems in Number Theory (3rd edition). Many examples are known of K4. Stan Wagon apparently found examples of K5. $\endgroup$ – Bernardo Recamán Santos Apr 4 '15 at 13:36
4
$\begingroup$

Maybe this will work.

Given positive integers a and b, choose c large enough so that c^2 > a+b. also, choose c so that c^2 -a -b is odd and factors as (e+d)(e-d). Then a has an edge with c^2 - a, b has an edge with d^2 - b, and c^2 - a -b + d^2 = e^2. So choose c also so that c^2 - a is distinct from a and from d^2 - b. I leave the existence of c to others.

$\endgroup$
  • $\begingroup$ Wouldn't this prove that the diameter is $3$ when it works? $\endgroup$ – Christian Remling Apr 4 '15 at 15:24
  • $\begingroup$ I count diameter as length of a path from end-to-end, counted by vertices. But I am not a graph theorist. Also, this just shows small diameter for a small initial section of the graph. However, one more step from b may reach the rest of the graph. $\endgroup$ – The Masked Avenger Apr 4 '15 at 15:30
4
$\begingroup$

Probably this idea can confirm the conjecture.

There are a lot of couples $(a,b)$ such that $a+b$ is odd, $a<b$ and $\mathrm{Dist}(a,b)\le 2$. We can try to find $x\le n$ such that $$a+x=y^2\quad\text{ and }\quad b+x=(y+1)^2.$$ So $1$ is connected (connection length is $2$) with $6$, $8$, $\ldots$ $2[\sqrt{n+1}]$, $2$ is connected with $7$, $9$, $\ldots$ $2[\sqrt{n+2}]$, etc. This first step gives highly connected component $M$ inside $[1,2\sqrt n]$. A big number $2\sqrt n<c\le n$ we can try to connect with $M$ considering the nearest square $[\sqrt c]^2$ because $|[\sqrt c]^2-c|<2\sqrt n+1.$ So we need one step to $M$, two steps inside $M$, and one step from $M$.

$\endgroup$
  • $\begingroup$ Pitifully, $a$ and $a+1$ are never at distance 2. $\endgroup$ – Ilya Bogdanov Apr 5 '15 at 10:22
  • $\begingroup$ @Ilya Bogdanov Because we work with positive integers. $\endgroup$ – Alexey Ustinov Apr 5 '15 at 10:24
3
$\begingroup$

(Not an answer; just a comment.)

It is a somewhat tangled graph. Here is a representation of $G(100)$:


          SqGraph100
One can see $50+71=121=11^2$ near the lower-right corner, $84+85=169=13^2$ near the top, $82+62=144=12^2$, near the bottom, etc.

This $G(100)$ graph has diameter $5$. But $G(1000)$ has diameter $4$.

$\endgroup$

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.