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$
5
  • 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$ Apr 4, 2015 at 2:08
  • 1
    $\begingroup$ Do you know any argument showing that the diameter can't be 3 for sufficiently large $n$? $\endgroup$ Apr 4, 2015 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, 2015 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, 2015 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$ Apr 4, 2015 at 13:36

3 Answers 3

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$
2
  • $\begingroup$ Wouldn't this prove that the diameter is $3$ when it works? $\endgroup$ Apr 4, 2015 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$ Apr 4, 2015 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$
2
  • $\begingroup$ Pitifully, $a$ and $a+1$ are never at distance 2. $\endgroup$ Apr 5, 2015 at 10:22
  • $\begingroup$ @Ilya Bogdanov Because we work with positive integers. $\endgroup$ Apr 5, 2015 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$
0

Your Answer

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

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