El diámetro de un determinado gráfico sobre los enteros positivos

Question

Dejemos que $G(n)$ sea el gráfico cuyos vértices son los enteros positivos $1,2,3,4, \ldots, n$ dos de los cuales están unidos por una arista si su suma es un cuadrado. ¿Es el diámetro de este gráfico 4 para todo lo suficientemente grande $n$ ?

Answer 1

Tal vez esto funcione.

Dados enteros positivos a y b, elige c lo suficientemente grande como para que c^2 > a+b. Además, elige c de modo que c^2 -a -b sea impar y se factorice como (e+d)(e-d). Entonces a tiene una arista con c^2 - a, b tiene una arista con d^2 - b, y c^2 - a -b + d^2 = e^2. Así que elige también c para que c^2 - a sea distinto de a y de d^2 - b. Dejo la existencia de c a otros.

Answer 2

Probablemente esta idea puede confirmar la conjetura.

Hay muchas parejas $(a,b)$ tal que $a+b$ es impar, $a<b$ y $\mathrm{Dist}(a,b)\le 2$ . Podemos tratar de encontrar $x\le n$ tal que $$a+x=y^2\quad\text{ and }\quad b+x=(y+1)^2.$$ Así que $1$ está conectado (la longitud de la conexión es $2$ ) con $6$ , $8$ , $\ldots$ $2[\sqrt{n+1}]$ , $2$ está relacionado con $7$ , $9$ , $\ldots$ $2[\sqrt{n+2}]$ etc. Este primer paso da un componente altamente conectado $M$ dentro de $[1,2\sqrt n]$ . Un gran número $2\sqrt n<c\le n$ podemos intentar conectar con $M$ considerando el cuadrado más cercano $[\sqrt c]^2$ porque $|[\sqrt c]^2-c|<2\sqrt n+1.$ Así que necesitamos un paso para $M$ , dos pasos en el interior $M$ y a un paso de $M$ .

Answer 3

(No es una respuesta, sólo un comentario).

Es un gráfico algo enmarañado. Esta es una representación de $G(100)$ :

---

         

Se puede ver $50+71=121=11^2$ cerca de la esquina inferior derecha, $84+85=169=13^2$ cerca de la parte superior, $82+62=144=12^2$ cerca del fondo, etc.

Este $G(100)$ El gráfico tiene un diámetro $5$ . Pero $G(1000)$ tiene un diámetro $4$ .