Gráfico con mayor valor propio "casi" $\pi$

Question

Haciendo garabatos hace poco descubrí que el mayor valor propio de la matriz de adyacencia del siguiente grafo no dirigido (ignorar las direcciones de las aristas en la imagen) es "casi" $\pi$ . Según la octava, su mayor valor propio es 3,1413. FWIW, su respuesta exacta es 1+2 $w$ donde $w$ es la raíz mayor de $4w^3+4w^2-7w-2=0$ que WolframAlpha evalúa como 3,141336114.

Así que mi pregunta es, ¿existe un gráfico cuyo mayor valor propio de su AM esté más cerca de -- pero no sea igual a -- $\pi$ ?

Muchas gracias.

Answer 1

Una posibilidad es empezar con un gran $3$ -grafo regular $G_{2n}$ con $2n$ vértices entonces uniendo parejas de vértices con grado $3$ (el grado de cualquier vértice en tal pareja va de $3$ à $4$ ) con un borde. Cada vez que añadimos una arista, el valor propio dominante aumenta lentamente, pasando de $3$ à $4$ (si añadimos $n$ aristas, obtenemos un $4$ -regular). Dado que $n$ es arbitraria, existe una clase de grafos con el valor propio dominante arbitrariamente próximo a $\pi$ como quieras.

El gráfico representado es, de hecho, un casi $3$ -Gráfico regular: sólo un vértice de $9$ tiene grado $4$ por lo que cabe esperar que el valor propio dominante esté próximo a $3+\frac{1}{9}=3.111\ldots\approx\pi.$

Por la misma razón, el siguiente gráfico es otro buen candidato:

Creo que un problema realmente interesante es exhibir un grafo infinito con valor propio dominante exactamente igual a $\pi$ Creo que no es demasiado difícil demostrar, mediante un argumento de compacidad combinatoria, que ese grafo debe existir, pero quizá también tenga una estructura "bonita".