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$?
$\begingroup$
$\endgroup$
5
asked Apr 4, 2015 at 1:52
-
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 SantosCommented 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$– Anthony QuasCommented 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$– user48028Commented 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$– user48028Commented 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$– Bernardo Recamán SantosCommented Apr 4, 2015 at 13:36
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
answered Apr 4, 2015 at 5:44
-
$\begingroup$ Wouldn't this prove that the diameter is $3$ when it works? $\endgroup$ Commented 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$ Commented Apr 4, 2015 at 15:30
$\begingroup$
$\endgroup$
2
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$.
answered Apr 4, 2015 at 6:12
-
$\begingroup$ Pitifully, $a$ and $a+1$ are never at distance 2. $\endgroup$ Commented Apr 5, 2015 at 10:22
-
$\begingroup$ @Ilya Bogdanov Because we work with positive integers. $\endgroup$ Commented Apr 5, 2015 at 10:24
$\begingroup$
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.
$\endgroup$
0
(Not an answer; just a comment.)
It is a somewhat tangled graph. Here is a representation of $G(100)$:
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$.
answered Apr 4, 2015 at 2:56